<s>[INST] Why can't I prove this statement by simple induction? Sum of $1/2^1 + \cdots+ n/2^n = x$ I have to prove the following:
$$
\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{n}{2^n}=2-\frac{2 + n}{2^n}.
$$
I am trying to prove this by simple induction. First, I proved that $P(1)$ holds. It clearly does.
I then assume that $n$ is a positive number $> 1$ and that $P(n)$ holds. Hence,
$$
\frac{1}{2}+\ldots+\frac{n}{2^n}=2-\frac{2 + n}{2^n}.
$$
I now add ${\displaystyle \frac{n + 1}{2\cdot 2^n}}$ to both sides to get the following:
$$
\frac{1}{2}+\cdots+\frac{n}{2^n}+\frac{n+1}{2\cdot 2^n}=2-\frac{2+n}{2^n}+\frac{n+1}{2\cdot 2^n}.
$$
But after manipulating the right side I get the following:
$$
\frac{1}{2}+\cdots+\frac{n}{2^n}+\frac{n+1}{2^{n+1}}=2-\frac{3n + 5}{2^{n+1}}.
$$
This is definitely not right since I should be getting
$$
\frac{1}{2}+\cdots+\frac{n}{2^n}+\frac{n+1}{2^{n+1}}=2-\frac{n + 3}{2^{n+1}}=2-\frac{2+(n+1)}{2^{n+1}}
$$
to prove that $P(n)$ implies $P(n+1)$.
What am I doing wrong?
 [/INST] For $n\geq 1$, let $P(n)$ denote the statement
$$
P(n) : \frac{1}{2}+\frac{2}{2^2}+\cdots+\frac{n}{2^n} = 2-\frac{2+n}{2^n}.
$$
Then, we want to show that $P(n)\to P(n+1)$; that is, we want to show that
$$
P(n+1) : \frac{1}{2}+\frac{2}{2^2}+\cdots+\frac{n}{2^n}+\frac{n+1}{2^{n+1}} = 2-\frac{2+(n+1)}{2^{n+1}}.
$$
The statement $P(1)$ is clearly true: $\frac{1}{2}=2-\frac{2+1}{2^1}$. For the inductive step, fix some $k\geq 1$ and suppose that
$$
P(k) : \frac{1}{2}+\frac{2}{2^2}+\cdots+\frac{k}{2^k} = 2-\frac{2+k}{2^k}
$$
holds. Needed to be shown is that
$$
P(k+1) : \frac{1}{2}+\frac{2}{2^2}+\cdots+\frac{k}{2^k}+\frac{k+1}{2^{k+1}} = 2-\frac{2+(k+1)}{2^{k+1}}
$$
follows. Starting with the left-hand side of $P(k+1)$,
\begin{align*}
\frac{1}{2}+\frac{2}{2^2}+\cdots+\frac{k}{2^k}+\frac{k+1}{2^{k+1}}&= \left(2-\frac{2+k}{2^k}\right)+\frac{k+1}{2^{k+1}}\tag{ind. hyp}\\[1em]&=2-\frac{2(2+k)}{2^{k+1}}+\frac{k+1}{2^{k+1}}\tag{manipulate}\\[1em]&=2-\frac{4+2k-k-1}{2^{k+1}}\tag{simplify}\\[1em]&=2-\frac{3+k}{2^{k+1}}\tag{simplify}\\[1em]&=2-\frac{2+(k+1)}{2^{k+1}},
\end{align*}
which equals the right-hand side of $P(k+1)$. This completes the inductive step. By mathematical induction, for every $n\geq 1, P(n)$ is true. 
</s>