How do you prove by induction that $\frac{1}{2} + \frac{2}{2^2} + \ldots + \frac{n}{2^n} = 2 - \frac{n+2}{2^n}$? For $n=1$ this is true because $\frac{1}{2^{1}}=2-\frac{1+2}{2^{1}}=\frac{1}{2}$. Further, it is a little more complicated, can we now assume that this is true up to the number $n-1$? Then do the induction step from $n-1$ to $n$.
So what I've tried:
$$\frac{1}{2}+\frac{1}{2^{2}}+\ldots+\frac{n-1}{2^{n-1}}+\frac{n}{2^{n}}=$$
$$=2-\frac{n+1}{2^{n-1}}+\frac{n}{2^{n}}=$$
 A: \begin{align*}
\frac{1}{2} + \frac{1}{2^2} + ... + \frac{n-1}{2^{n-1}}+\frac{n}{2^n}
&=2-\frac{n+1}{2^{n-1}} + \frac{n}{2^n}\\
&= 2+\frac{-2n-2 + n}{2^{n}}\\
&= 2- \frac{n+2}{2^n}
\end{align*}
A: Another solution : for sequences $\{a_{n}\}, \{b_{n}\}$

*

*Prove $\sum_{k=1}^{n} a_{k} b_{k} = \sum_{k=1}^{n-1} S_{k} (b_{k} - b_{k+1}) + S_{n} b_{n}$ where $S_n = \sum_{k=1}^{n} a_{k}.$ ($n \in \mathbb{N}$)

$pf)$ $(RHS) = b_{n} (S_{n} - S_{n-1}) + b_{n-1} (S_{n-1} - S_{n-2}) + \cdots + b_{1} S_{1} = \sum_{k=1}^{n} a_{k} b_{k}$
since $S_{n} - S_{n-1} = a_{n}$ for $n \ge 1.$


*Evaluate $\sum_{k=1}^{n} \frac{k}{2^{k}}$, $n \in \mathbb{N}$.

let $a_n = 2^{-n}, b_{n} = n, n \in \mathbb{N}$. By the formula shown in 1,
$$\sum_{k=1}^{n} a_{k} b_{k} = \sum_{k=1}^{n-1} S_{k} (b_{k} - b_{k+1}) + S_{n} b_{n}$$
$$= \sum_{k=1}^{n-1} \frac{2^{-1} \cdot (1 - 2^{-k})}{1 - 2^{-1}} \cdot (-1) + \frac{2^{-1} \cdot (1 - 2^{-n})}{1 - 2^{-1}} \cdot n$$
$$= \sum_{k=1}^{n-1} (2^{-k} - 1) + n(1 - \frac{1}{2^{n}})$$
$$= \frac{2^{-1} \cdot (1 - 2^{1-n})}{1 - 2^{-1}} - n + 1 + n - \frac{n}{2^{n}}$$
$$= 1 - \frac{1}{2^{n-1}} + 1 - \frac{n}{2^{n}}$$
$$= 2 - \frac{n+2}{2^{n}}.$$
A: You can write this sum using sigma notation, for clarity.

$\frac{1}{2} +\frac{2}{2^2} + \dots+\frac{n}{2^n} = \sum_{i=1}^{n} \frac{i}{2^i} = 2-\frac{n+2}{2^n}.$ (*)

Let our induction hypothesis $P(n)$ be the equation (*).
Let's apply mathematical induction now.
Base case $(n=1):$ $$\sum_{i=1}^{1} \frac{i}{2^i} = \frac{1}{2^1} = \frac{1}{2} = 2-\frac{1+2}{2^1} = 2-\frac{3}{2} = \frac{1}{2}$$ $P(1)$ holds. $\blacksquare$
Inductive step: Assume $P(n)$ holds for some $n \geq 1.$ Show that $P(n+1)$ holds.
Since $P(n)$ holds, we can write
$$\sum_{i=1}^{n} \frac{i}{2^i} = 2-\frac{n+2}{2^n}$$
$$\sum_{i=1}^{n} \frac{i}{2^i} + \frac{n+1}{2^{n+1}}= 2-\frac{n+2}{2^n}+\frac{n+1}{2^{n+1}}$$
$$\sum_{i=1}^{n+1} \frac{i}{2^i} = 2+\frac{(-2)\cdot(n+2) + (n+1)}{{2}^{n+1}}$$
$$\sum_{i=1}^{n+1} \frac{i}{2^i} = 2+\frac{-n-3}{{2}^{n+1}}$$
$$\sum_{i=1}^{n+1} \frac{i}{2^i} = 2-\frac{n+3}{{2}^{n+1}}$$
$$\sum_{i=1}^{n+1} \frac{i}{2^i} = 2-\frac{(n+1)+2}{{2}^{n+1}}$$
Since $P(n)$ holds for $n+1$, our induction hypothesis is true $\forall n \geq 1.$ $\blacksquare$
