Proving $n^2≤2^n+1$ for $n\geq 1$ by induction 
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?
 A: 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$).  
A: 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.
