# More Induction

## 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.

Related Precalculus Mathematics Homework Help News on Phys.org
Defennder
Homework Helper
$$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}}$$

$$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
Homework Helper
$$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? 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}}$$

?

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

typo I suspect

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

Thanks, I finally understood this now.