2
$\begingroup$

So I am having trouble with an exercise about mathematical induction. I have the following sentence: $1^{n+1}$ < $2^n$ for every n ≥ 3

Now, what I would personally do is:

First prove that it is true for n = 3

$1^{3+1}$ = 1 < 8 = $2^3$

And assume that if the sentence is true for n, then it is also true for k. Then I would prove that the sentence is true for k+1 for every k ≥ 3.

Now the problem is that I have seen an answer to a question similar to this, where the person solving the problem proved that the sentence is true for k+1 for every k ≥ 4.

Even when that person changed k ≥ 3 to k ≥ 4, it didn't make any change to the overall proof. What I want to know is, which notation is the right one; k ≥ 3, or k ≥ 4?

$\endgroup$
1
  • 1
    $\begingroup$ IMHO, this exercise is quite meaningless, for there’s almost nothing to prove by induction here: in fact, $2^n > 2^0 = 1 = 1^{n+1}$ for every $n \in \mathbb{N} \setminus \{0\}$. $\endgroup$
    – Pacciu
    Commented Oct 12, 2019 at 10:18

2 Answers 2

Reset to default
3
$\begingroup$

It is a strange identity to prove by induction since it is trivially true!

Anyway for the induction step we assume true

$$1^{k+1} < 2^k$$

and we need to prove that

$$1^{k+2} < 2^{k+1}$$

which is true indeed

$$1^{k+2} = 1\cdot 1^{k+1}< 2^k <2^{k+1}$$

Since the base case has been proved for $n=3$, the last needs to be true for $k\ge 3$.

$\endgroup$
2
$\begingroup$

It should be $k\ge 3$. The other person's proof only works if you check $n=4$ as part of the base step. (It's a strange exercise, mind, because even starting at $n=0$ would work.)

$\endgroup$
2
  • $\begingroup$ Would it be right to check n=4 as part of the base step then? Shouldn't you always check for the statement in the original question (in this case n =< 3)? $\endgroup$
    – Setin
    Commented Oct 12, 2019 at 10:17
  • $\begingroup$ @Setin If you want a proof the result is true for $n\ge3$, but you only check going from $n=k$ to $n=k+1$ works for $k\ge4$, your base step needs to include $n=4$ as well as $n=3$. Ideally, one should note the inductive-step proof works for $k\ge0$, so as to prove the result for $n\ge0$ using only $n=0$ as the base step. $\endgroup$
    – J.G.
    Commented Oct 12, 2019 at 10:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .