$\forall n \geq 5$ prove $2^n > n^2$

Question

I am trying to prove the title using induction and here is my attempt:

Base Case: n = 1 : $2>1$ which is True

I.H. : $2^k > k^2$ for some $k$

Inductive Step:

$2^{k+1} = 2^k 2$

$2^{k+1} > 2k^2$ by I.H.

But I am not quite sure what to do next.

Try proving that $n^2 < 2^n$ instead of what you have. Sometimes reversing the inequality can make the inductive step seem more natural. — JavaMan, Aug 13 '19 at 15:54
Note that $2^4 \not> 4^2$, so your proof which starts with the base case $n=1$ had better not work! You picked the wrong base case. — Lee Mosher, Aug 13 '19 at 15:57

score 1 · Answer 1 · edited Aug 13 '19 at 16:25

1

Hint Using $k \geq 5$,

$$\begin{align} 2k^2&=k^2+k^2 \\ &\geq k^2+5k\\ &> k^2+2k+k\\ &> k^2+2k+1. \end{align}$$

edited Aug 13 '19 at 16:25

Shaun

answered Aug 13 '19 at 15:54

N. S.

1 Answers1