Why is $2^n > n^2$ for $n \geq 5$ only? Because $n=1$ is also true but $n=2$ for example not. Let me choose $n=1$ for my induction basis: $2 > 1$, true.
Induction Step : $2^n > n^2 \rightarrow 2^{n+1} > (n+1)^2 $
$2^{n+1} > (n+1)^2 \iff$
$2\cdot 2^n > n^2 + 2n + 1 \iff$
$0 > n^2 + 1 + 2n - 2\cdot 2^n \iff$
$0 > n^2 -2^n + 1 + 2n - 2^n \iff$ IH: $0 > n^2 - 2^n$
$0 > 1 + 2n - 2^n > n^2 - 2^n + 1 + 2n - 2^n \iff$
$2^n > 1 + 2n > n^2$, which can be proved with induction for $n \geq 3$
$2^n > n^2$, true by assumption
I have showed that, based from the induction basis, I can conclude the general statement. But like I have said in the headline the identity is not fulfilled for $n=2$, so something must be wrong in the proof.    
 A: Obviously your inequality is not true for $n=4$ 
Thus you better start at $n\ge 5 $ which is proved the same way.  
A: You chose $n=1$ as induction base, but the induction step works only for $n\geq 3$, i.e. you showed that $2^n > n^2$ implies $2^{n+1}>(n+1)^2$ only when $n\geq3$. That's where the problem is. Then you might try to use $n=3$ as the base case, but unfortunately for $n=3$ the statement is not true. That's why you will have to use $n=5$ as a basis case, and the induction proof will be correct.
A: You have an error. You had $n^2-2^n+1+2n-2^n<0$, by in the induction hypothesis, you do know that $n^2-2^n<0$. But that does not mean that $1+2n-2^n<0$. It could be that $1+2n-2^n$ is positive, just not as positive as $n^2-2^n$ is negative so that their sum is still $<0$. The two will only always balance out for $n \geq 5$. But you assumed $n \geq 1$ in the proof. So go back and assume that $n \geq 5$, making your base case needing to check $n=5$, not $n=1$. This then makes the result the expected $2^n>n^2$ for $n\geq 5$.
A: You have assumed for the base case


*

*$n=1 \implies 2>1$
and it is not wrong, then for the induction step $P(n) \implies P(n+1)$ you have found that it works only for $n\ge 3$.
In that case what we need to complete the proof is to go back again to the base case and find a value $n\ge 3$ which works.
