Prove that $n^2 = O(2^n)$ by mathematical induction I have been having a hard time understanding mathematical inductions and can not finalize the proof for this statement. I am currently learning about algorithms asymptotic bounding and this is a problem given in the book I am reading. I have set my $n_0$ to $4$ since during the basis step we've proven that for $n_0 \ge 4$, $n^2 \le C(2^n)$.
During my induction step, I have
$(k+1)^2 \le C \cdot 2^{k+1} $
$k^2 + 2k + 1 \le C \cdot 2^k + 2$
I thought I could then do $2k+1\le 2$ after removing $k^2$ and $2^k$ from the previous inequality due to having proven that $n^2\le 2^n$ for all $n \ge n_0$. However, doing so would cause the inequality to be false. I'm missing that one key step that will cause all of it to make sense, any help would be greatly appreciated!
 A: The second inequality is wrong, you find instead :
$$(k+1)^2 \leq C \cdot 2^{k+1} \implies \frac{ k^2+2k+1}{2} \leq C \cdot 2^k $$
now find when $  \frac{ k^2+2k+1}{2}  \leq k^2 $ to conclude (if you solve this since you know that $ k^2 \leq C \cdot 2^k $ then you find that  $\frac{ k^2+2k+1}{2}  \leq k^2 \leq C \cdot 2^k  \implies (k+1)^2 \leq C \cdot 2^{k+1}$)
A: Let $C=2$. Checking $n=1-3$, $1\leq4$, $4\leq8$ and $9\leq16$ are indeed true.
Assume for $n=k$ that $k^2 \leq 2*2^k$. Then, consider $n=k+1$:
$k^2+2k+1 \leq 2*2^{k+1}$ -> $k^2+2k+1 \leq 2^k+3*2^k$
Since $k^2 \leq 2^k$(by assumption) and $2k+1 \leq k^2$ for $k\geq3$ (not very hard to prove), the above inequality for $n=k+1$ is true. Therefore, by induction, the inequality is true for all $k\geq3$. Thus, $n^2\leq2*2^n$ and so $n^2=O(2^n)$.
Update:
Here is a proof that $2n+1 \leq n^2$ for $n\geq3$.
Checking $n=3$, $7\leq9$ is indeed true.
Assume for $n=k$ that $2k+1 \leq k^2$. Then, consider $n=k+1$:
$2k+3\leq(k+1)^2$ -> $2k+3\leq k^2+2k+1$ -> $2\leq k^2$
Since $k^2\geq2$ is always true for $k\geq3$, the above inequality for $n=k+1$ is true. Therefore, by induction, the inequality is true for all $k\geq3$. Thus, $2n+1 \leq n^2$.
