1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by induction

  1. Nov 5, 2012 #1
    1. The problem statement, all variables and given/known data

    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.




    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. jcsd
  3. Nov 5, 2012 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    For C:

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

    Do you see how to get the answer to D from the answer to C ?
     
  4. Nov 5, 2012 #3
    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
  5. Nov 5, 2012 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Of course. How about the result after plugging in the specific expressions for Un and Un+1 ?
     
  6. Nov 5, 2012 #5
    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
  7. Nov 5, 2012 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  8. Nov 5, 2012 #7
    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.
     
  9. Nov 6, 2012 #8
    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??
     
  10. Nov 6, 2012 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Is that the result of using induction?
     
  11. Nov 7, 2012 #10
    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.
     
  12. Nov 7, 2012 #11

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    The instructions were very clear regarding solving by induction.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...