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

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.
