# Proof by induction

## Homework Statement

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.

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

SammyS
Staff Emeritus
Homework Helper
Gold Member

## Homework Statement

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

1) For every n>0 let $\displaystyle 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.

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

For C:

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

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

For C:

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

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

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:
SammyS
Staff Emeritus
Homework Helper
Gold Member
Vn=(Un+1)/(Un) should i count the difference of Vn-(3/4).
Of course. How about the result after plugging in the specific expressions for Un and Un+1 ?

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

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:
SammyS
Staff Emeritus
Homework Helper
Gold Member
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.
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.

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.

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.

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??

SammyS
Staff Emeritus
Homework Helper
Gold Member
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??
Is that the result of using induction?

Is that the result of using induction?

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.

SammyS
Staff Emeritus