Stuck on Induction Hypothesis, I don't know how to continue

Question

I would like to prove the following proposition by induction:

For all $m\in\mathbb N$, we have $\sum_{i=1}^m \frac{i}{2^i} = 2 - \frac{m+2}{2^m}.$

First, I prove the base step $m = 1$:

$\sum_{i=1}^m \frac{i}{2^i} = 2 - \frac{3}{2}.$, which is effectively $\frac{1}{2}$ on both sides of this equation.

Next, I assume that there is some $k\in\mathbb N$ such that $$ \sum_{i=1}^k \frac{i}{2^i} = 2 - \frac{k+2}{2^{k}}. $$

Now, to prove the inductive step I do: (I cannot put the 2nd 2k as 2^k+1) $$ \sum_{i=1}^{k+1} \frac{i}{2^i}= 2 - \frac{k+2}{2^k}+ \frac{k+1}{2^{k+1}} $$

I don't know what to do at this point as I cross multiply them, they decide to not work past that point. Any suggestions?

Answer 1

Simplify the right hand side :

$$2 - \frac{k+2}{2^k}+ \frac{k+1}{2^{k+1}} = 2 + \frac{-2(k+2)+k+1}{2^{k+1}} = 2-\frac{(k+1)+2}{2^{k+1}} $$

which is your proposition in the $k+1$-th case.

Answer 2

Here is an easier way.

Put $$S_m=\sum_{i=1}^m\frac{i}{2^i}=2-\frac{m+2}{2^m}$$

You just need, for the inductive step, to prove that

$$S_{m+1}-S_m=\color{red}{\frac{m+1}{2^{m+1}}}$$

but

$$S_{m+1}-S_m=$$ $$(2-\frac{m+3}{2^{m+1}})-(2-\frac{m+2}{2^m})=$$

$$\frac{m+2}{2^m}-\frac{m+3}{2^{m+1}}=$$

$$\frac{2m+4-m-3}{2^{m+1}}=$$ $$\color{red}{\frac{m+1}{2^{m+1}}}$$ Done.