# Proof that $n^2 < 2^n$

How do I prove the following statement by induction?

$$n^2 \lt 2^n$$

$P(n)$ is the statement $n^2 \lt 2^n$

Claim: For all $n \gt k$, where $k$ is any integer, $P(n)$

(since $k$ is any integer, I assume I have to prove this for positive and negative integers)

So let base case be $P(1)$, and I have to prove $P(n)$ for $n \ge 1$ and $n \lt 1$

$P(1)$ is $1^2 \lt 2^1$ which is clearly true.

Induction hypothesis: $k^2 \lt 2^k$

Inductive step $(k+1)^2 \lt 2^{(k+1)}$

$(k+1)^2 = k^2 + 2k + 1$

$k^2 + 2k + 1 \lt 2^k + 2k + 1$ by inductive hypothesis

Not sure how to proceed. Is my previous intuition that I have to prove this for $n \ge 1$ and $n \lt 1$ correct?

-
One problem is that the claim is not true. $2^2 \not < 2^2$ –  Chris Eagle Mar 3 '13 at 22:46
Also, $3^2\not<2^3$, and $4^2\not<2^4$ but it holds for $n\ge 5$. –  Berci Mar 3 '13 at 22:55
This question has been asked here several times before. I always like to point out a nice combinatorial proof, for $n\ge 5$: $n^2=\binom{n}{1}+\binom{n}{2}+\binom{n}{n-2}<\sum_k\binom{n}{k}=2^n$. –  Andres Caicedo Mar 4 '13 at 0:43
–  Andres Caicedo Jul 9 '13 at 4:38

$$n^2<2^n\Longleftrightarrow 2\log n<n\log 2\Longleftrightarrow\frac{\log n}{n}<\frac{\log 2}{2}$$

But we know that $\,\displaystyle{\frac{\log n}{n}\xrightarrow[n\to\infty]{}0}\,$ , so the above inequality's definitely true from one definite index $\,n\,$ and on...but not for all the naturals!

-
Here you use a lot of math which isn't allowed when you have to prove such inequalities in classes. In my class we defined the logarithm several weeks after Induction. And you need the monoticity of the logarithm. And btw the Question is tagged with induction –  Dominic Michaelis Mar 3 '13 at 23:04
Here we define the exponential and logarithm roughly about the same time as induction in the 11th high school grade, and monotonicity of logarithm is trivial since its derivative is always positive...and this also is high school stuff. –  DonAntonio Mar 3 '13 at 23:06
i mean in university not in high school –  Dominic Michaelis Mar 4 '13 at 10:23

If you want to use induction, I assume you have checked the base case $n = 5$. To do the inductive step, assume that the statement holds for some $k$: $k^2 < 2^k$, and then under this assumption, you want to check that the statement holds for $k+1$: $(k+1)^2 < 2^{k+1}$. Well,

$$(k+1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1$$

by the inductive hypothesis. When is $2^k + k + 1 < 2^{k+1}$. Well,

\begin{align} 2^k + k + 1 < 2^{k+1} &\iff k+1 < 2^{k+1} - 2^k \\ &\iff k+1 < 2^k. \end{align}

It is sufficient to show that $k+1 < 2^k$ for all $k \geq 5$. One way to do this is by induction. You can easily show the base case $5 + 1 < 2^5$. Now, assume that it holds for some $j \geq 5$, and we want to show that it also holds for $j+1$. Thus, we want to show that if $j+1 < 2^j$, then $(j+1) + 1 < 2^{j+1}$. This follows almost immediately since

$$(j+1) + 1 < 2^j + 1 < 2^j + 2^j = 2^{j+1}$$ You should note that the inequality $1 < 2^j$ is not true in general, but it is true for $j > 1$ (and in particular for $j \geq 5$). Thus, we have shown that $k+1 < 2^k$ for all $k \geq 5$, and this was precisely what we needed for the inductive step of the original proof.

It should be noted that induction is indeed not the easiest way to prove this inequality, but if we want to strictly use induction, then something like this proof (and the consequent proof of the statement $k+1 < 2^{k}$ for $k \geq 5$) is the way to go.

As a final note, to show what I mean about the easiest proof, as it was noted above, we have $n^2 < 2^n$ if and only if $\frac{\log n}{n} < \frac{\log 2}{2}$. Now, $f(x) = \frac{\log(x)}{x} \implies f'(x) = \frac{1 - \log x}{x^2} < 0$ when $x > e$. Thus, the function is strictly decreasing for $x > e$. Coupled with the fact that $f(x) \to 0$ as $x \to \infty$, it then suffices to find the first integer $t$ such that $\frac{\log t}{t} < \frac{\log 2}{2}$. This happens to be $t = 5$.

Added: Thomas' hint is a bit nicer than my own answer, as it requires only check the values for which $n^2 > 2n +1$ which can be done with basic algebra.

-

Hint only: For $n \geq 3$ you have $n^2 > 2n + 1$ (this should not be hard to see) so if $n^2 < 2^n$ then consider $$2^{n+1} = 2\cdot2^n > 2n^2 > n^2 + 2n+1 = (n+1)^2.$$ Now this means that the induction step "works" when ever $n\geq 3$. However to start the induction you need something greater than three. By trial an error you can find the smallest $n(\geq0)$ such that $n^2 < 2^n$.

-
Thomas: Your method of working backwards sure trumps mine as you have reduced the proof to showing the inequality $n^2 > 2n +1$, which any algebra student should be able to do. –  JavaMan Mar 3 '13 at 23:39
This proof is very simple and uses induction properly. This answer should be on top. –  i.ozturk Feb 7 at 15:50

Your statement is only true for $n=0$, $n=1$ and $n \geq 5$.
Than start with $n=5$, this gives $5^2=25 < 2^5 = 32$

So Assume it is true for $n$. Than we know that $$2^{k+1}= 2 \cdot 2^k > 2 k^2>k^2+2k+1=(k+1)^2$$ (as $n^2>2n+1$ for all $n\geq 3$ and as we started with $n=5$ this is always true)

-

As a fun fact another way to see that this inequality is true eventually is to compare the sum of the numbers in the $n-1$ 'st row of pascal's triangle to the $n$'th triangular number, which appears in the $n+1$ 'st row and occurs along one of the diagonal's of pascal's triangle. See the link for more details, http://mathforum.org/workshops/usi/pascal/pascal_triangular.html. The fact presented on that page plus the fact the sum of the row of pascal's triangle is a power of two can be used to prove the desired inequality.

This amounts to proving that $\frac{n(n+1)}2 \lt 2^\left(n-1\right)$ which is stronger than the original inequality, since $n^2 \lt n(n+1)$ for $n \gt 0$ .

-