Prove $n^2 \leq 2^n + 1$ by induction Suppose $n \in \mathbb{N}$, prove the given inequality.
So far I have this:
Show that the above is true for $n=1$.
$$ 1 \leq 3 $$
Suppose that it holds for all $n$. Show that  it holds for $n+1$ 
$$ (n+1)^2 \leq 2^{n+1} + 1 $$
$$ \color{red}{n^2} + 2n + 1 \leq 2^n + \color{red}{2^n + 1} $$
So I have to use induction again. But here, when I try the case where $n=1$ it doesn't hold ... ?
i.e.
$$ 2n+1 \leq 2^n $$
Is not true for $n=1$. What do I do?

You can first look for what you need.
Assume $n^2\le 2^n+1$. Then
$$
(2^{n+1}+1)-(n+1)^2=2\cdot2^n-n^2-2n=2\bigl((2^n+1)-n^2\bigr)+(n^2-2n-2)
$$
which is surely $\ge0$ so long as $n^2-2n-2\ge0$.
This happens when $n\ge1+\sqrt{3}$, so for $n\ge3$.

Now you can give the proof.


*

*Case $n=0$: $0^2\le 2^0+1$, true

*Case $n=1$: $1^2\le 2^1+1$, true

*Case $n=2$: $2^2\le 2^2+1$, true

*Case $n=3$: $3^2\le 2^3+1$, true
Suppose $n\ge3$; then $n^2-2n-2\ge0$. If $n^2\le 2^n+1$, we have
$$
(2^{n+1}+1)-(n+1)^2=2\cdot2^n-n^2-2n=2\bigl((2^n+1)-n^2\bigr)+(n^2-2n-2)\ge0
$$
and therefore $(n+1)^2\le 2^{n+1}+1$.

Another strategy. Assume $n^2\le 2^n+1$. Then
$$
(2^{n+1}+1)-(n+1)^2=2\cdot 2^n-n^2-2n=(2^n-n^2)+(2^n-2n)
$$
which is $\ge0$ so long as $2^n-2n\ge0$. Well, this can be proved by induction as well. The inequality $2n\le2^n$ holds for $n=0$ and $n=1$. If $n\ge1$ and $2n\le 2^n$, then
$$
2(n+1)=2n+2\le2^n+2\le2^n+2^n=2^{n+1}
$$
So we can give the proof.
Lemma. For all $n$, $2n\le 2^n$.
Proof. (Repeat the above)
Proposition. For all $n$, $n^2\le 2^n+1$.
Proof. The inequality holds for $n=0$. Suppose it holds for $n$; then
\begin{align}
(n+1)^2 &= n^2+2n+1 \\
&\le 2^n+2n+1 &&\text{induction hypothesis} \\
&\le 2^n+2^n+1 &&\text{by the lemma} \\
&= 2^{n+1}+1
\end{align}
