# Proof by induction

1. Nov 5, 2012

### mtayab1994

1. The problem statement, all variables and given/known data

Let $$U_{n}=\frac{n^{2}}{2^{n}}$$ for every n in N

1) For every n>0 let $$V_{n}=\frac{U_{n+1}}{U_{n}}$$

a) Prove that $$\lim V_{n}=\frac{1}{2}$$

b) For every n>0 prove that: $$V_{n}>\frac{1}{2}$$

c) First the smallest natural number N such that : $$n\geq N\Rightarrow V_{n}<\frac{3}{4}$$

d) Conclude that $$n\geq N\Rightarrow U_{n+1}<\frac{3}{4}U_{n}$$

2) We want to show that $$(S_{n})_{n\geq5}$$ is convergent such that:

Sn=U5+U6+U7+....+Un

a) Prove by induction that for every natural number greater than 5: $$U_{n}<(\frac{3}{4})^{n-5}U_{5}$$

b) Prove also by induction that for every natural number greater than 5:

Sn≤[1+(3/4)+(3/2)^2+....+(3/4)^(n-5)]U5

c) Conclude that Sn≤4U5 for every n≥5

3) Prove that $$(S_{n})_{n\geq5}$$ is monotone increasing and conclude that it is convergent.

3. The attempt at a solution

Solved 1) a and b and stuck on c and d.

For number 2-a I showed that U5≤U5 and I need to know how to show that Un+1≤(3/4)^n-4U5.

I have no idea on b and c and number 3.

Thanks for any help before hand.

2. Nov 5, 2012

### SammyS

Staff Emeritus
For C:

What is $\displaystyle V_{n}\ ?$

Do you see how to get the answer to D from the answer to C ?

3. Nov 5, 2012

### mtayab1994

Vn=(Un+1)/(Un) And I counted the difference Vn-(3/4) I got a polynomial of -n^2+4n+1 over 8n^2 and found that the answer N=5 is that correct??

Last edited: Nov 5, 2012
4. Nov 5, 2012

### SammyS

Staff Emeritus
Of course. How about the result after plugging in the specific expressions for Un and Un+1 ?

5. Nov 5, 2012

### mtayab1994

Well since Vn=(Un+1)/Un and we proved that Vn<3/4 then (Un+1)/Un<3/4 therefore:

Un+1<(3/4)Un. By the way in my previous quote i found N=5.

Last edited: Nov 5, 2012
6. Nov 5, 2012

### SammyS

Staff Emeritus
Yes, 5 is correct.

#2. (a) says:
Prove by induction that for every natural number greater than 5: $\displaystyle \ \ U_{n}<\left(\frac{3}{4}\right)^{n-5}U_{5}\ .$​
So show that it's true for n=6, not n=5 .

So, assume that $\displaystyle \ \ U_{k}<\left(\frac{3}{4}\right)^{k-5}U_{5}\$ is true for some k ≥ 6 . From that assumption, show that $\displaystyle \ \ U_{k+1}<\left(\frac{3}{4}\right)^{(k+1)-5}U_{5}\$ is true.

7. Nov 5, 2012

### mtayab1994

I'm sorry it is greater than or equal to 5. So for n=5 we get U5≤U5 and that's true.

So we assume Un≤(3/4)^(n-5)U5 and we show that Uk+1≤(3/4)^(k-4)U5 is true.

8. Nov 6, 2012

### mtayab1994

Ok this is what i got :

$$U_{k+1}-(\frac{3}{4})^{k-4}U_{5}=\frac{32(k+1)^{2}-((\frac{3}{4})^{k-4}(25\cdot2^{k+1})}{25\cdot2^{k+1}}$$ and i assume that that is negative because n^2≤2^n so therefore (n+1)^2≤2^(n+1) . So we get the numerator to be less than or equal to zero and the denominator is positive so the difference is negative. is that correct??

9. Nov 6, 2012

### SammyS

Staff Emeritus
Is that the result of using induction?

10. Nov 7, 2012

### mtayab1994

No it's not i did a different way i added the left side and the right side from k=5 to k=n-5 and then I added the results from the left hand side and the left hand side and i found that Uk+1≤(3/4)^(n-5)U5. I've also solved all of the other ones as well. Thanks for you help.

11. Nov 7, 2012

### SammyS

Staff Emeritus
The instructions were very clear regarding solving by induction.