Proof verification induction on sequence

I am doing problems that involve inequalities. My understanding is that you through a string of inequalities show that one is less than the other. Kind of like the transitive property. For example:

$2n+1 \lt 2^n$ for $n=3,4,...$

Assume this is true for P(k):

Base case $k = 3$

$LHS: 7 \space \space \space RHS: 8$

$LHS \space \space \lt \space \space RHS$

This holds true for $(k)$

Prove for P(k+1):

$2(n+1)+1 \lt 2^{n+1}$

my understanding is that if I can find something that is greater than $2(n+1)+1$ and obviously below $2^{n+1}$ then the inequality holds true

$2k+3 \lt 2^{k+1}$

$(2k + 1) + 2 \lt 2^k2$

$(2k+1) + 2 \lt 2^k + 2$ by our hypothesis on $k$

It is very obvious that $2^k + 2 \lt 2^k2$ and doesn't need explanation so its safe to assume

$2k+3 = (2k+1)+2 \lt 2^k + 2 \lt 2^k2$

Thus $(2k+3) \lt 2^k2$

This seems perfectly logical to me since we are dealing with integers. These inequalities would not hold for $\mathbb{R}$.

I am having a hard time find a string of inequalities that proves $n^2 \leq 2^n+1$

Assume this holds true for $k$. $P(k) = k^2 \leq 2^k+1$ for $n = 1,2...$

Base case $P(1):$ $LHS: 1 \space \space \space RHS: 3$

$LHS \space \space \leq \space \space RHS$

holds true for $P(k)$

$P(k+1)$:

$(k+1)^2 \leq 2^k + 1$

$k^2 + 2k + 1 \leq 2^k2+1$

$k^2 + 2k + 1 \leq 2^k +1 + 2k +1 \leq 2^k2+1$

$k^2 + 2k + 1 \leq 2^k + 2k + 2 \leq 22^k+1$ by our hypothesis on $k$

I do not know where to go from here

Answer

You assume that $k^2\leq 2^k+1$ for some $k\geq 1$, and you want to prove that $(k+1)^2\leq 2^{k+1}+1$. Starting from the left-hand-side, you can proceed as follows:

$$\begin{align*} (k+1)^2 &= k^2+2k+1\\ &\leq (2^k+1) + 2k + 1, \end{align*}$$
where the inequality follows from the induction hypothesis. If we can now show that

$$(2^k+1) + 2k + 1 \leq 2^{k+1},$$
then we we are done. By rearranging, this amounts to showing (for $k\geq 1$) that
$$2k+2\leq 2^{k+1} - 2^k,$$
or

$$2(k+1)\leq 2^k(2-1),$$

or

$$2(k+1)\leq 2^k,$$

or

$$k+1\leq 2^{k-1}.$$

Oops! This last inequality is not true for all $k\geq 1$ like I hoped it would be. Don't worry about this, it happens. It doesn't mean that the original statement is wrong.

The last inequality fails for $k=1$ and $k=2$. But it does hold for all $k\geq 3$. I can remedy the proof by checking the base cases $k=1$, $k=2$, and $k=3$ in $k^2\leq 2^k+1$ by hand. Then I assume the induction hypothesis $k^2\leq 2^k+1$ for some $k\geq 3$, and I can proceed as above.