I'm having a hard time rationalizing the proof that $2^n > n^2$ if $n >4$ 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? 
 A: 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.$$
A: 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$.
