Take the 2-minute tour ×

I'm trying to solve a proof for this inequality. I already have the solution, but have a question about the solution. Here's what I have so far:
Prove $2^n > n^2$ for $n > 4$
Base Case $n=5$. $32 > 25$. True.
Inductive Case: Assume $2^n > n^2$ is true for $4 < n \leq k$. In particular, for $2^k > k^2$. Prove $2^{k+1} > (k+1)^2$.

$$2^{k+1} = 2 \cdot 2^k > k^2 + 2k + 1$$.

Here's where I get stuck. The solution says that $2 \cdot 2^k > 2 \cdot k^2$. Ok, makes sense. Then it says that that is equal to $k^2 + k^2 > k^2 + 2k + 1$.

Where did $k^2 + k^2$ come from?

share|improve this question
The solution said you have to prove the induction hypothesis is true at $n = k+1$, hence it suffices to show that $2^{k+1} > (k+1)^2$, while rewrite this inequality a little you will find that it suffices to show that $2 \cdot 2^k > k^2 + 2k + 1$, now use induction hypothesis at $n = k$, which says $2^k > k^2$, the left side is greater than $2 k^2$, hence if you could show $k^2 + k^2 > k^2 + 2k + 1$, then this implies $2 \cdot 2^k > k^2 + k^2 > k^2 + 2k +1$, hope this would help –  Shuhao Cao May 5 '11 at 19:19
Thanks makes perfect sense. Thank you. –  ShrimpCrackers May 5 '11 at 19:38
Please do not tag only with [homework]. Surely you know the mathematical topic of the question. –  Asaf Karagila May 5 '11 at 22:22

2 Answers 2

up vote 2 down vote accepted

$2k^2 = k^2 + k^2$, so:

$$k^2 + 2k + 1 < k^2 + k^2 = 2k^2 < 2 \cdot 2^k$$

It's easy to see that $2k^2 < 2 \cdot 2^k$ from the induction hypothesis, so you only need to prove $k^2 + 2k + 1 < k^2 + k^2$.

share|improve this answer

Previously posted answers have amply dealt with the question, but I think it is worth making some methodological remarks.

The approach that is being taken to the question "When is $2^n >n^2$?" is essentially subtractive. There is a better approach, that deals well with a range of similar problems. For this particular problem, it will seem more complicated, because division feels more complicated than subtraction.

Let $f(n)=n^2/2^n$. We want to show that $f(n)<1$ when $n >4$. Note that $$f(n+1)=\frac{(n+1)^2}{2^{n+1}}=\frac{n^2}{2^n}\frac{(n+1)^2}{n^2}\frac{1}{2}$$ Thus $$f(n+1)=f(n)\left(1+1/n\right)^2/2$$ But $(1+1/n)^2/2<1$ for any $n \ge 3$. Thus from $n=3$ on, $f(n)$ is decreasing. Since $f(4)=1$, we conclude that $f(n)<1$ for all $n \ge 5$.

Similarly, let us show that from some identified point on, $3^n >n^4$. Let $f(n)=n^4/3^n$. A calculation similar to the one above shows that $$f(n+1)=f(n)(1+1/n)^4/3$$ The term that $f(n)$ is multiplied by is less than $1$ when $n \ge 4$, so from $n=4$ on, $f(n)$ is decreasing. A little experimentation shows that $f(7)>1$ and $f(8)<1$. So $f(n)<1$ from $n=8$ on.

Note for purists: The word "induction" has not been mentioned. However, like in most problems about positive integers, induction is being used. In the $2^n > n^2$ problem, from the facts that $f(n+1)<f(n)$ for $n \ge 3$ and that $f(4)=1$, we are quietly concluding that $f(n)<1$ for all $n>4$. In principle this step requires mathematical induction. In practice we regard this step as obvious, and do not use the "i" word.

share|improve this answer

Your Answer


