Prove $n^2\leq 2^n+1$ for $n\geq 1$ using induction.
Proof. For $n=1, (1)^2\leq 2^1+1=3$. $\therefore 1\leq 3$ is true.
Assume $n=k$ is true so $k^2\leq 2^k+1$ or $k^2-1\leq 2^k$. Then prove for $n=k+1$.
Goal: $(k+1)^2\leq 2^{k+1}+1$
We have $$ 2^{k+1}+1=2\cdot 2^k+1\geq2\cdot(k^2-1)+1=2k^2-2+1=2k^2-1. $$ I've got to the $2k^2-1$ but from there I'm stuck. I can't see how I can show that the goal is true? Or is that all I need to show for the proof?
Joffan's comment alludes to using four base cases (up through $n=4$), and I think this is the way to go:
For $n\geq 1$, let $S(n)$ denote the statement $$ S(n) : n^2\leq 2^n+1. $$
Base step ($n=1,2,3,4$): Showing that $S(1), S(2), S(3)$, and $S(4)$ all give true statements is easy, but the reason for going up through $n=4$ will become apparent below.
Inductive step $S(k)\to S(k+1)$: Fix some $k\geq 4$ and assume that $$ S(k) : k^2\leq 2^k+1 $$ holds. To be shown (i.e., the "goal" as you put it) is that $$ S(k+1) : (k+1)^2\leq 2^{k+1}+1 $$ follows. Starting with the left-hand side of $S(k+1)$, \begin{align} (k+1)^2 &= k^2+2k+1\tag{expand}\\[0.5em] &\leq (2^k+1)+2k+1\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &\leq (2^k+1)+2^k\tag{since $k\geq 4$; see $(\dagger)$}\\[0.5em] &= 2\cdot 2^k+1\tag{group like terms}\\[0.5em] &= 2^{k+1}+1\tag{by definition} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.
By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$
$(\dagger)$: Why is it important to have $k\geq 4$ when we assert $$ (2^k+1)+2k+1\leq (2^k+1)+2^k\quad? $$ When simplified, this inequality clearly becomes $$ 2k+1\leq 2^k, $$ but we need $k\geq 4$ for this inequality to be true in general ($k=1,2,3$ all cause problems, but everything is smooth sailing for $k=4$ and beyond, that is, when $k\geq 4$).
You are left to prove:$$2k^2-1\ge(k+1)^2=k^2+2k+1$$This leads to proving:$$k^2\ge2(k+1)$$Which is true for $k\gt2$
Therefore you need to show the cases for $n=1$ and $n=2$ to be true and you are done.
