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.

How do you prove in induction that: $$\frac{(n+1)^2}{2^n}\le\frac{9}{4}$$

This is what I keep getting:

Checking for $n=1$ we get $2\le\frac{9}{4}$.

Assuming it's true for $n$ and checking for $n+1$ I get this: $$\frac{(n+2)^2}{2^{n+1}}=\frac{2(n+1)^2-n^2+2}{2\times2^n}\le\frac{9}{4}-\frac{n^2-2}{2\times2^n}\le\frac{9}{4}$$ Which is true only for $n>1$.

share|improve this question
1  
Your proof is correct, if your induction starts at $n=1$, then you only care about $n>=1$ anyway. –  Ricbit Nov 13 '12 at 10:55
1  
Isn't $\frac{9}{4}-$ a value that's positive for $n>1$ smaller than $\frac{9}{4}$? What's the problem? –  Kevin Carlson Nov 13 '12 at 10:55
    
I see now. Thank you. –  yuvalz Nov 13 '12 at 10:58
    
@Kevin: the inductive step does not prove the hypothesis for $n=2$, i.e. it does not work for $n=1$ or $n+1=2$, since it would attempt to say $\frac{9}{4}-\frac{1^2-2}{2\times2^n}\le\frac{9}{4}$ –  Henry Nov 13 '12 at 11:11
1  
Yuvalz: Because your statements fail to get from the hypothesis being true for $1$ to it being true for $2$. Asuming it is true for $n=1$ does not get you to it being true for $n+1=1+1$ this way. Your "proof" method of showing the hypothesis is true for $n=1$ and then showing that if true for $n \gt 1$ then also true for $n+1$ could also show $\frac{(n+1)^2}{2^n} \le 2$, which would be false for $n=2$. –  Henry Nov 13 '12 at 11:46
show 4 more comments

2 Answers

up vote 2 down vote accepted

The simple answer is to check $n=2$ too, where you have

$$\frac{(n+1)^2}{2^n}= \frac{(2+1)^2}{2^2} = \frac{9}{4} \le\frac{9}{4}$$ and then do the induction.

share|improve this answer
add comment

For another proof, you can see that $\displaystyle \frac{u_{n+1}}{u_n}= \frac{1}{2} \left( 1+ \frac{1}{n+1} \right)^2 \leq 1$ with $n\geq 2$ and $\displaystyle u_n= \frac{(n+1)^2}{2^n}$. So $(u_n)$ decreases for $n\geq 2$ whence $\displaystyle u_n \leq u_2=\frac{9}{4}$ for $n \geq 2$. Finally, you only have to check the case $n=1$.

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.