Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook