Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
2  
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
add comment

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
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.