# More Induction

1. Jun 9, 2008

### Moridin

1. The problem statement, all variables and given/known data

Show that

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

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

2. Jun 9, 2008

### Defennder

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.

3. Jun 9, 2008

### tiny-tim

Hi Moridin!

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

4. Jun 10, 2008

### Moridin

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

?

5. Jun 10, 2008

### Moridin

Isn't the p+ 1 in the first fraction suppose to be p + 2? How did that happen?

6. Jun 10, 2008

### GregA

typo I suspect

7. Jun 10, 2008

### Defennder

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

8. Jun 14, 2008

### Moridin

Thanks, I finally understood this now.