# 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 could start the Induction at an $n = 3$, so $2n + 1 \leq 2^n$ is true, and prove the first inequality for $n=1$ and $n=2$ without induction. – Carlos Esparza Oct 24 '16 at 18:58
• Makes perfect sense, thanks! – Anthony P Oct 24 '16 at 18:59
• After checking the base cases up to $n=p$, you should suppose that the inequality holds for some $n\geq p$ then try to show that it holds for $n+1$. Alternatively, you can also suppose that the inequality holds for all $n\leq k$ for some $k\geq p$ and then try to show it for $n=k+1$. – yurnero Oct 24 '16 at 19:01
• See also: Proof that $n^2 < 2^n$ – Martin Sleziak Oct 27 '16 at 0:14

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.

• The step from $n^2+2n+1$ to $2^n+2n+1$ seems to assume $n^2\le2^n$ rather than $n^2\le2^n+1$, so this doesn't look like a valid induction to me. (Also, the step from $2^n+2n+1$ to $2^n+2^n+1$ seems to assume $2n\le2^n$, which really requires its own separate inductive proof.) – Barry Cipra Oct 27 '16 at 0:23
• yup, it uses $n^2 \le 2^n$, which is not true for $n=3$. – Dean C Wills Oct 27 '16 at 15:14

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.

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}