Proof by induction

  • Thread starter mtayab1994
  • Start date
  • #1
584
0

Homework Statement



Let [tex]U_{n}=\frac{n^{2}}{2^{n}}[/tex] for every n in N

1) For every n>0 let [tex]V_{n}=\frac{U_{n+1}}{U_{n}}[/tex]

a) Prove that [tex]\lim V_{n}=\frac{1}{2}[/tex]

b) For every n>0 prove that: [tex]V_{n}>\frac{1}{2}[/tex]

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

d) Conclude that [tex]n\geq N\Rightarrow U_{n+1}<\frac{3}{4}U_{n}[/tex]


2) We want to show that [tex](S_{n})_{n\geq5}[/tex] is convergent such that:

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

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


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 [tex](S_{n})_{n\geq5}[/tex] 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.
 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,365
1,033

Homework Statement



Let [itex]\displaystyle U_{n}=\frac{n^{2}}{2^{n}}[/itex] for every n in N

1) For every n>0 let [itex]\displaystyle V_{n}=\frac{U_{n+1}}{U_{n}}[/itex]

a) Prove that [itex]\lim V_{n}=\frac{1}{2}[/itex]

b) For every n>0 prove that: [itex]V_{n}>\frac{1}{2}[/itex]

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

d) Conclude that [itex]n\geq N\Rightarrow U_{n+1}<\frac{3}{4}U_{n}[/itex]


2) We want to show that [itex](S_{n})_{n\geq5}[/itex] is convergent such that:

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

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


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 [itex](S_{n})_{n\geq5}[/itex] 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 [itex]\displaystyle V_{n}\ ?[/itex]

Do you see how to get the answer to D from the answer to C ?
 
  • #3
584
0
For C:

What is [itex]\displaystyle V_{n}\ ?[/itex]

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:
  • #4
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,365
1,033
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 ?
 
  • #5
584
0
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:
  • #6
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,365
1,033
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: [itex]\displaystyle \ \ U_{n}<\left(\frac{3}{4}\right)^{n-5}U_{5}\ .[/itex]​
So show that it's true for n=6, not n=5 .

So, assume that [itex]\displaystyle \ \ U_{k}<\left(\frac{3}{4}\right)^{k-5}U_{5}\ [/itex] is true for some k ≥ 6 . From that assumption, show that [itex]\displaystyle \ \ U_{k+1}<\left(\frac{3}{4}\right)^{(k+1)-5}U_{5}\ [/itex] is true.
 
  • #7
584
0
Yes, 5 is correct.

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

So, assume that [itex]\displaystyle \ \ U_{k}<\left(\frac{3}{4}\right)^{k-5}U_{5}\ [/itex] is true for some k ≥ 6 . From that assumption, show that [itex]\displaystyle \ \ U_{k+1}<\left(\frac{3}{4}\right)^{(k+1)-5}U_{5}\ [/itex] 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.
 
  • #8
584
0
Ok this is what i got :

[tex]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}}[/tex] 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
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,365
1,033
Ok this is what i got :

[tex]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}}[/tex] 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?
 
  • #10
584
0
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.
 
  • #11
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,365
1,033
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.
The instructions were very clear regarding solving by induction.
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
859
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
870
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
940
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
846
Top