Prove $n^2 \leq 2^n + 1$ by induction

Question

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?

Answer 1

It is true for $n=1$. Assume that it is true for $n$ i.e. $n^2 \le 2^n + 1$. Now

$$ (n+1)^2 = n^2 + 2n + 1 \le 2^n + 2n + 1 \le 2^n + 2^n + 1 = 2^{n+1} + 1 $$

Hence proved.

Answer 2

To expand on Ox539's comment, there is no requirement to start with "the" base case in an inductive proof; it sometimes helps to check the first several cases, and then let induction take over. This is particularly true when the statement to be proved is an inequality.

For the problem at hand, we can check the first three cases:

$$\begin{align} 1^2=1&\le3=2^1+1\\ 2^2=4&\le5=2^2+1\\ 3^2=9&\le9=2^3+1 \end{align}$$

(The fact that the third cases is actually an equality helps explain why straightforward induction from $n=1$ runs into trouble.) The rest of the proof can be presented as follows:

$$\begin{align} n\ge3 &\implies3\le(n-1)^2\\ &\implies3\le n^2-2n+1\\ &\implies n^2+2n+1\le2n^2-1\\ &\implies(n+1)^2\le2(2^n+1)-1\quad\text{(by the inductive hypothesis)}\\ &\implies(n+1)^2\le2^{n+1}+1 \end{align}$$

Note, the first line could have been "strengthened" to say $n\ge3\implies 4\le(n-1)^2$ (since $n\ge3\implies n-1\ge2$), but weakening the $4$ to a $3$ gives a better "flow" to the subsequent steps.

Answer 3

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}