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? 

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.$$
