I'm having a hard time rationalizing the proof that $2^n > n^2$ if $n >4$

Question

I'm not sure how to apply $n > 4$ in the proof, when I work it out I get that $n >2$...

Basis Step $P(5) = 2^5 > 5^2 = 32 > 25 $ which is True

Hypothesis assume $P(k) = 2^k > k^2$ is true. Prove that $P(k+1)$ is true.

Substituting $k+1$ into the hypothesis yields: $2^{k+1} > (k+1)^2$

$2 \bullet 2^k > k^2 +2k +1$

$2^k > \frac{k^2 +2k +1}{2}$

Since I assume $2^k > k^2$ I then try to find the conditions where $k^2 > \frac{k^2 +2k +1}{2}$

$2k^2 > k^2 +2k +1$

$k^2 -2k - 1 > 0$ which is true when $k > 4$ (and also $k >2$). Therefore the proof is true via mathematical induction?

Answer 1

You don't quite have right how the proof by induction should work.

You verified your base case of $n=5$. (Note, by the way, that the statement is clearly false for $n \leq 4$ by simple computation.)

Now assume the statement is true for $k: 2^k \gt k^2$.

Multiply both sides of this inequality by $2: 2^{k+1} \gt 2k^2$. Also, note that if $k \gt 5$, then $k^2 \gt 2k+1$. It follows that $2k^2 \gt k^2+2k+1=(k+1)^2$ so $2^{k+1} \gt (k+1)^2$ and our proof is complete.

But you needed to prove the base case in order to prove that your induction could get started in the first place -- if you had tried to start at $k=4$, your proof would have failed at the first step because when $k=4$ it's simply not true that $2^k \gt k^2$.

Answer 2

First of all, this is false when $n=3$. $2^3 = 8 < 9 = 3^2$. This becomes clear if you properly write out your inequality:

$$2^k > k^2 >\frac{k^2 + 2k + 1}{2}.$$

The right inequality holds for $k > 2$ but the left one only holds for $k =5$, and $k \geq 5$ once you prove the inequality. When you plug in $n=3$, you get

$$2^3 = 8 \ngeq 9 = 3^2 > \frac{4^2}{2} = 8.$$