Proof by induction on n So I aim to prove that $n^2 \leq 2^n + 1$ for all integers $n \geq 1$. We can see that this is true for $n=1$ since $1 \leq 3$. Now I suppose that this is true for an arbitrary $k$ such that $k \geq 1$. So $k^2 \leq 2^k +1$. From this, I want to reach a statement $(k+1)^2 \leq 2^{k+1} +1$ by algebraic manipulation. But it seems harder than I thought. For example, I expanded the "goal" statement so I get $k^2 + 2k +1 \leq 2^{k+1} +1$, which looks easier to get to from the original statement $k^2 \leq 2^k +1$. I tried a lot of algebraic manipulations and also tried the transitive property of order relation, but still cannot figure out how to get there. Any suggestions?

Suppose that for some $n\ge3$, we have $n^2\le 2^n+1$. Then
$$
\begin{align}
(n+1)^2
&=n^2+2n+1\tag{1}\\
&=2n^2-2-(n+1)(n-3)\tag{2}\\
&\le2n^2-2\tag{3}\\
&\le2^{n+1}\tag{4}\\
&\lt2^{n+1}+1\tag{5}
\end{align}
$$
Explanation:
$(1)$: expand the square
$(2)$: $n^2+2n+1=2n^2-2-(n^2-2n-3)$
$(3)$: since $(n+1)(n-3)\ge0$ for $n\ge3$
$(4)$: $2n^2-2\le2(2^n+1)-2=2^{n+1}$
$(5)$: $x\lt x+1$
All that is left is to verify that $n^2\le2^n+1$ for $0\le n\le3$.
