1

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$.

yuvalz
  • 577
  • 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
  • @Ricbit: you are in danger of falling into a "all horses are the same colour" trap, where it turns out $n=2$ is the difficult case – Henry Nov 13 '12 at 11:15
  • @Henry I don't get why it's not true. I've shown that the statement is true for $n=1$. Then, by assuming it's right for every $n$ and checking $n+1$ seen it's right for $n>1$. Adding these together I get that it's true for $n\ge1$. Please correct me if I'm wrong. – yuvalz Nov 13 '12 at 11:23
  • 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
  • OK, yeah, so you just have to use $2$ as your base case, as Henry has done below. – Kevin Carlson Nov 13 '12 at 11:51
  • @Henry, I see, you are right. In this case, the induction basis must be done for n=1 and n=2, and only then you should do the induction step. – Ricbit Nov 13 '12 at 11:51

2 Answers2

2

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.

Henry
  • 157,058
1

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$.

Seirios
  • 33,157