Prove by mathematical induction $4^n > n+1$

Question

Prove the following by mathematical induction:

$4^n > n+1$, for all integers $n ≥ 1$

Step 1: $n=1$:

LHS $= 4^{(1)} = 4 $

RHS $= (1) + 1 = 2$

LHS > RHS. ∴ $P(1)$ is true.

Step 2: Assume $P(k)$ is true for some $k ≥ 1$

$P(k)$: $4^k > k+1$

Step 3: We must show $P(k+1)$ is true.

$n = k+1$: $4^{k+1} > (k+1)+1$

RHS = $(k+1)+1 < 4^k +1 < 4^k + 4^k = 2*4^k < 4*4^k = 4^{k+1}$ = LHS

Hence, $P(k+1)$ is true. Therefore, By Math. Induction $P(n)$ is true for all $n ≥ 1$

Can anyone check if my method is correct or there is a better way to do it. Thank you.

Answer 1

This looks all right. I think you could have been a little bit more neat when writing it down, perhaps laying your reasoning vertically as it is usually done, and with a little bit more info. Like this.

Our inductive hypothesis is $4^k>k+1$. We want to prove $4^{k+1}>(k+1)+1$.

Because of our inductive hypothesis,

$4^{k}+1>(k+1)+1$

From this follows

$4*4^k>4^k+1>(k+1)+1$

$4^{k+1}>(k+1)+1$

Yes it takes more time but it makes everything easier for anyone correcting your proof. Anyhow, congratulations! Your proof is correct.

Answer 2

Agreed, your proof's fine. If you want a "better" way to do it, I can only suggest something that's "better" in the sense of making the calculation shorter. Note the inductive hypothesis implies $4^{k+1}>4k+4>k+2$.

When dealing with integers, I often prefer to write $a>b$ as $a\ge b+1$. In this case, the theorem itself would be restated as $4^n\ge n+2$, with inductive step $4^k\ge k+2\implies 4^{k+1}\ge 4k+8\ge k+3$. But, as you can see, I'm really fishing for "improvements" at this point because it's basically fine as is.