• Support PF! Buy your school textbooks, materials and every day products Here!

More Induction

  • Thread starter Moridin
  • Start date
  • #1
664
3

Homework Statement



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]


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.
 

Answers and Replies

  • #2
Defennder
Homework Helper
2,591
5
[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]
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.
 
  • #3
tiny-tim
Science Advisor
Homework Helper
25,832
249
[tex]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.
Hi Moridin! :smile:

Yes, the sign error is in your p + 1 at the end, isn't it? :smile:
 
  • #4
664
3
Hi Moridin! :smile:

Yes, the sign error is in your p + 1 at the end, isn't it? :smile:
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]

?
 
  • #5
664
3
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.
Isn't the p+ 1 in the first fraction suppose to be p + 2? How did that happen?
 
  • #6
210
0
typo I suspect
 
  • #7
Defennder
Homework Helper
2,591
5
Yeah it's a typo. Apart from that it should be fine.
 
  • #8
664
3
Thanks, I finally understood this now.
 

Related Threads for: More Induction

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
4
Views
1K
Replies
1
Views
8K
  • Last Post
Replies
7
Views
572
  • Last Post
Replies
6
Views
808
Replies
2
Views
5K
  • Last Post
Replies
2
Views
1K
Top