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

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.

• Why not learn how to use MathJax? It is cool to be able to write mathematical expressions as you wish ;). And as a reader, I don't really like the "4n+1=4$^n$*4" part :/ – Scientifica Mar 8 '17 at 0:04
• Ahh yes I am working on learning it! – agra94 Mar 8 '17 at 0:09
• Ah ok cool then :) – Scientifica Mar 8 '17 at 6:54

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

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

since $3n \geq 1$.

• Interesting. So with this type of problem, the goal isn't really trying to make 3n+n equal to n+1 but more about showing how because 3n+n > n+1, that the above inequality is still satisfied? So, because 4^n * 4 > 3n+1 > n+1, that 4^n*4 > n+1 and that, after simplification of 4^n*4, this completes our induction step? – agra94 Mar 8 '17 at 0:03
• Yes, that's right. You follow the chain of inequalities down, so finally we have $4^{n+1}>n+1$, as required. – Nathan H. Mar 8 '17 at 0:05

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

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 !

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