# 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 $\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?

• Sign error in the long displayed line after "$\dots$ to both sides:". Jan 15, 2015 at 5:04
• Going from that line to the one with $3n+5$, the numerator should be $4+2n-(n+1)=n+3$ Jan 15, 2015 at 5:49

In RHS, $-\dfrac{2+n}{2^n} + \dfrac{n+1}{2^{n+1}} = \dfrac{-4-2n+n+1}{2^{n+1}} = \dfrac{-(n+3)}{2^{n+1}} = -\dfrac{2+(n+1)}{2^{n+1}}$ which is what you want.
Since there is always the possibility that the original statement that you try to prove is false, I tried $n = 1, 2, 3$.
For $n = 3$, the sum is $\frac{11}{8}=2-\frac{5}{8}$ as the statement claims, but not $2-\frac{11}{8}$ as you calculated. So it seems that you are making a mistake in your calculation. Note that $a-b+c$ is not $a-(b+c)$ but $a-(b-c)$.
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.
$$\begin{array}{l} \left| x \right| < 1:\frac{1}{{1 - x}} = \sum\limits_{k = 0}^\infty {x^k } = 1 + \sum\limits_{k = 1}^\infty {x^k } \\ \Rightarrow \sum\limits_{k = 1}^\infty {kx^k } + \sum\limits_{k = 1}^\infty {x^k } = \frac{x}{{\left( {1 - x} \right)^2 }} + \frac{x}{{1 - x}} \\ \Rightarrow \sum\limits_{k = 1}^\infty {\left( {k + 1} \right)x^k } = \frac{x}{{\left( {1 - x} \right)^2 }} + \frac{x}{{1 - x}} \\ \left| x \right| < 1;x = \frac{1}{2} \Rightarrow \sum\limits_{k = 1}^\infty {\left( {k + 1} \right)\left( {\frac{1}{2}} \right)^k } = \frac{{\frac{1}{2}}}{{\left( {1 - \frac{1}{2}} \right)^2 }} + \frac{{\frac{1}{2}}}{{1 - \frac{1}{2}}} = 3 \\ \end{array}$$