# Find all natural numbers n such that n^2 < 2^n

Using induction proof, find all the natural numbers $n$ such that $n^2 < 2^n$.

I know that $n$ does not work for $2, 3$, and $4$ but it does work for $0$ and $1$ as well as any number greater than or equal to $5$, I am just not sure how to show this in a proof.

• Induction says that your statement holds for all $n$ greater than or equal to some $N$. Can $N$ be less than $5$ based on your observations? – Cameron Williams Sep 29 '14 at 0:55
• Yes if it is 0 or 1 but not if it is 2, 3 or 4 – Anon123 Sep 29 '14 at 1:00
• If $N=0$ or $1$, what mathematical induction would say is that for all $n\ge N$, your statement ($n^2 < 2^n$) is true. Is this the case? – Cameron Williams Sep 29 '14 at 1:07

Hint

You're on the right track. You can show by exhaustion that $n=0$ and $n=1$ are solutions, but $n\in \{2,3,4\}$ are not.

Next we test our base case $n=5$ and it is a solution.

Suppose for some $n=i$, it is the case that $n^2<2^n$. Hence $i^2<2^i$. We will show that $(i+1)^2<2^{i+1}$, which would complete the proof.

Note:

\begin{align} (i+1)^2 &= i^2+2i+1 \\ (i+1)^2 &<2^i+2i+1 \\ (i+1)^2 &<2^{i+1}-(2^i-2i+1) \end{align}

So it remains to show that $2^i\ge2i+1$ so long as $i\ge5$. This can also be proven with induction. Try doing it as an exercise.