Proof of $\sum_{k=0}^{n} \frac{k}{2^{k}}$ Equation

[Moridin]

Homework Statement

Show that

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

The Attempt at a Solution

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

$$\frac{0}{2^{0}} = 2 - \frac{2}{2^{0}} = 0$$

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

Assume that

$$\sum_{k=0}^{p} \frac{k}{2^{k}} = 2 - \frac{p+2}{2^{p}}$$

Now,

$$\sum_{k=0}^{p} \frac{k}{2^{k}} = \frac{1}{2} + \frac{2}{4} +\frac{3}{8} + \frac{4}{16} + ... + \frac{p}{2^{p}}$$

$$\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}}$$

If it can be shown that

$$2 - \frac{p+2}{2^{p}} + \frac{p+1}{2^{p+1}} = 2 - \frac{p+3}{2^{p+1}}$$

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

$$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}}$$

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.

 

[Defennder]

$$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}}$$

It's like this instead:

$$2 - \frac{2(p+1)}{2^{p+1}} + \frac{p+1}{2^{p+1}} = 2 + \frac{p+1-2p-4}{2^{p+1}}$$

Simplify from here and you're done.

 

[tiny-tim]

$$2 - \frac{2(p+2)}{2^{p+1}} + \frac{p+1}{2^{p+1}} = 2 - \frac{2p + 4 + p + 1}{2^{p+1}}$$

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!

Yes, the sign error is in your p + 1 at the end, isn't it?

 

[Moridin]

Hi Moridin!

Yes, the sign error is in your p + 1 at the end, isn't it?

I cannot find the exact place where I made the sign error, but it seems to stem from this line

$$\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}}$$

?

 

[Moridin]

It's like this instead:

$$2 - \frac{2(p+1)}{2^{p+1}} + \frac{p+1}{2^{p+1}} = 2 + \frac{p+1-2p-4}{2^{p+1}}$$

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?

 

[GregA]

typo I suspect

 

[Defennder]

Yeah it's a typo. Apart from that it should be fine.

 

[Moridin]

Thanks, I finally understood this now.