Prove the following: For all $k\in\mathbb{N},4^k>k$.

Question

I will prove by induction the statement $P(k)$: "For all $k\in\mathbb{N},4^k>k$."

The base case $P(1)$ results in $4>1$ which is a true statement.

Thus, I assume $P(n)$ to be true and consider $P(n+1)$.

$$4^{n+1} = 4^n \cdot 4 > 4n$$

I know that I am then supposed to rewrite $4n$ as $3n+n$. However, I do not know where to proceed from after that. According to my professor, I am suppoed to wind up with $3n+n=n+1$. However, I do not know where this comes from. Any help would be appreciated.

Answer 1

You kind of just have to play with inequalities a bit.

$$ 4n = 3n + n \geq 1 + n $$

since $3n \geq 1$.

Answer 2

You can use the fact that: $$4^k=(1+3)^k\geq 1+3k> k$$

Answer 3

Your claim is false! You have to reformulate the inductive step in order to be able to apply the inductive hypothesis, I.e. $4^k > k$. This can be done rewriting the inductive step

$4^{k+1} =4 \cdot 4^k$

And now you know the right hand side of the equality is greater then $4 \cdot k$, that is obviously greater then $k+1$ for $ k \ge 1$ and then you win !

Answer 4

A stronger result, $2^k>k$, is the finite-set case of Cantor's theorem. So a proof without induction is also possible.