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!

More Induction

  1. Jun 9, 2008 #1
    1. The problem statement, all variables and given/known data

    Show that

    [tex]\sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n+2}{2^{n}}~; ~~~ \forall n \in \mathbb{N} \cup \{0\}[/tex]


    3. The attempt at a solution

    (1) Show that it is true for n = 0

    [tex]\frac{0}{2^{0}} = 2 - \frac{2}{2^{0}} = 0[/tex]

    (2) Show that if it is true for n = p, it is true for n = p + 1

    Assume that

    [tex]\sum_{k=0}^{p} \frac{k}{2^{k}} = 2 - \frac{p+2}{2^{p}}[/tex]

    Now,

    [tex]\sum_{k=0}^{p} \frac{k}{2^{k}} = \frac{1}{2} + \frac{2}{4} +\frac{3}{8} + \frac{4}{16} + ... + \frac{p}{2^{p}}[/tex]

    [tex]\sum_{k=0}^{p+1} \frac{k}{2^{k}} = \frac{1}{2} + \frac{2}{4} +\frac{3}{8} + \frac{4}{16} + ... + \frac{p}{2^{p}} + \frac{p+1}{2^{p+1}} = \sum_{k=0}^{p} \frac{k}{2^{k}} + \frac{p+1}{2^{p+1}} = 2 - \frac{p+2}{2^{p}} + \frac{p+1}{2^{p+1}}[/tex]

    If it can be shown that

    [tex]2 - \frac{p+2}{2^{p}} + \frac{p+1}{2^{p+1}} = 2 - \frac{p+3}{2^{p+1}}[/tex]

    then (2) is done. However, here is it where it all goes wrong.

    [tex]2 - \frac{p+2}{2^{p}} + \frac{p+1}{2^{p+1}} = 2 - \frac{2(p+2)}{2^{p+1}} + \frac{p+1}{2^{p+1}} = 2 - \frac{2p + 4 + p + 1}{2^{p+1}}[/tex]

    Which is not the same as that which is looked for. However, there seem to be a sign error somewhere, since if the last two additions are subtractions, it works. Thank you for your time.
     
  2. jcsd
  3. Jun 9, 2008 #2

    Defennder

    User Avatar
    Homework Helper

    It's like this instead:

    [tex]2 - \frac{2(p+1)}{2^{p+1}} + \frac{p+1}{2^{p+1}} = 2 + \frac{p+1-2p-4}{2^{p+1}} [/tex]

    Simplify from here and you're done.
     
  4. Jun 9, 2008 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Moridin! :smile:

    Yes, the sign error is in your p + 1 at the end, isn't it? :smile:
     
  5. Jun 10, 2008 #4
    I cannot find the exact place where I made the sign error, but it seems to stem from this line

    [tex]\sum_{k=0}^{p+1} \frac{k}{2^{k}} = \frac{1}{2} + \frac{2}{4} +\frac{3}{8} + \frac{4}{16} + ... + \frac{p}{2^{p}} + \frac{p+1}{2^{p+1}} = \sum_{k=0}^{p} \frac{k}{2^{k}} + \frac{p+1}{2^{p+1}} = 2 - \frac{p+2}{2^{p}} + \frac{p+1}{2^{p+1}}[/tex]

    ?
     
  6. Jun 10, 2008 #5
    Isn't the p+ 1 in the first fraction suppose to be p + 2? How did that happen?
     
  7. Jun 10, 2008 #6
    typo I suspect
     
  8. Jun 10, 2008 #7

    Defennder

    User Avatar
    Homework Helper

    Yeah it's a typo. Apart from that it should be fine.
     
  9. Jun 14, 2008 #8
    Thanks, I finally understood this now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: More Induction
  1. Even More Induction (Replies: 1)

  2. Some More Induction (Replies: 4)

  3. Even More Induction (Replies: 10)

  4. Proof by induction (Replies: 1)

  5. Proof by Induction (Replies: 3)

Loading...