# Prove by induction: $\sum_{i=0}^{n-1}\frac{i}{2^i}=2-\frac{n+1}{2^{n-1}}$

So far I have: Let $P(n)$: $\sum_{i=0}^{n-1}\frac{i}{2^i}$ for all n $\geq 1$.

Basis: show $P(1)$: $$\sum_{i=0}^{n-1}\frac{i}{2^i}=0$$ $\therefore P(1)$ holds.

Inductive step: Show $P(k) \to P(k+1)$. Assume $P(k)$: $\sum_{i=0}^{k-1}\frac{i}{2^i}=2-\frac{k+1}{2^{k-1}},$ for arbitrary $k\geq 1$ and show $P(k+1)$: $\sum_{i=0}^{k}\frac{i}{2^i}=2-\frac{k+2}{2^k}.$ So we show: \begin{align}\sum_{i=0}^{k}\frac{i}{2^i}&=\frac{k}{2^k}+\sum_{i=0}^{k-1}\frac{i}{2^i}=\frac{k}{2^k}+2-\frac{k+1}2^{k-1}\quad \text{by IH}\\[0.2cm]&=2+\frac{k}{2^k}-\frac{k+1}{2^{k-1}}\end{align}

So I am confused now. I cannot solve for $2-\frac{n+1}{2^{n-1}}$ from this can I? Where did I go wrong?

No, there is no mistake (apart from a typo, one line before the end), so you are almost there$$2+\frac{k}{2^k}-\frac{k+1}{2^{k-1}}=2+\frac{k-(2)(k+1)}{2^k}=2+\frac{-k-2}{2^k}=2-\frac{k+2}{2^k}$$ Also, in the last line you say that you need to solve for $2-\dfrac{n+1}{2^{n-1}}$, but as you said above, what you really need is to solve for $2-\dfrac{n+2}{2^{n}}$.