How to end showing that a statement is true by using induction?

Question

I am practicing how to show true statements using induction. Since there are eventually different ways to show that a statement is true, I wanted to ask the following: When can you say that a true statement has been shown?

Example:

Prove that for any natural number n $\ge$ 2 we have $2^n > n+1$

Showing the base case is easy:

$$ 2^2 > 2+1 $$

But now we have the induction step and I wanted to ask whether it is okay to stop where I stopped.

$$ 2^{n+1} > (n+1)+1 $$ $$ 2^n * 2 > n+2 $$ $$ 2^n > \frac{n+2}{2}$$ $$ 2^n > \frac{n+2}{2}$$ $$ 2^n > \frac{n}{2} +1 $$

Can I know say that it is true because $n \in \mathbb{N}$ and $n \ge 2$? Or do I have to transform the equation in another way? I sometimes do not know when something has been shown and when the transformation is not enough to conclude that the statement is true.

Answer 1

Your proof is upside-down: you should start with something which is true and end up with what you want to prove

So instead say something like

• Given $2^n > n+1$ and $n \gt \frac n2$
• you have: $2^n > \frac n2 +1$
• and multiplying both sides by two: $2^{n+1}> n+2$
• and minor rearrangement: $2^{n+1} > (n+1)+1$
• and with the base case you can say by induction ...

Answer 2

The general method for induction is as follows:

1: Show that the $n$ case being true $\implies$ $n+1$ case is true.

2: Show that the "base case" is true, i.e, $n=1$ or $n=0$ or some other easy case.

3: $n=1$ case being true implies the $n=2$ case, which implies the $n=3$ case, then $n=4,5,...$ and so on.

Answer 3

So letting $a = 2^n$ and $b = n + 1$, you have an assumption of the form $$a > b$$ and you want to prove $$2a > b + 1$$

For this you almost always want to use the transitivity of $>$, that is $x > y \text { and } y > z \text{ then } x > z$. Since your goal is $2a > b+1$ that makes $x = 2a$ and $z = b+1$. So we need to find a suitable $y$ to establish 2 assumptions:

$$2a > y$$ $$y > b + 1$$

Since we already have $2a > 2b$ (the inductive assumption) that suggests using $y = 2b$, which means proving $2b > b + 1$ is enough. That is, just proving $2(n + 1) > (n + 1) + 1$ is enough to finish the inductive step of the problem.