Prove by induction that $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$

Question

Prove by induction $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$

Step 1: Show true for n = 0:

LHS: $\frac{0}{2^{0}}$ = 0

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

Step 2: Show that it is true for $n = p$, it is true for $n = p + 1$

Starting with the LHS of the $n = p + 1$ expression, breaking out the largest term and substituting in the $n = p$ equality gives:

$\sum_{k=0}^{p+1} \frac{k}{2^{k}} = \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}}$

Making everything besides the 2 have the same denominator $2^{p+1}$

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

...I get lost here.

Question: Where have I gone wrong in the above attempt?

Answer 1

You've just made a sign mistake: $$p+1-2(p+2)=-p-3=-(p+3)$$ and not $-(p-3)$.

And then you're done, since $p+3=(p+1)+2=n+2$.

Good job otherwise.

Answer 2

$\dfrac{p+1}{2^{p+1}} + 2 - \dfrac{p + 2}{2^{p}} = 2 + \dfrac{p + 1 - 2(p+2)}{2^{p+1}} = 2 + \dfrac{(-p - 3)}{2^{p+1}} = 2 - \dfrac{p+3}{2^{p+1}} = 2 - \dfrac{(p + 1)+2}{2^{p+1}}.$