<s>[INST] 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}}=$$
 [/INST] 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}}.$$
</s>