Why is this equation correct?

There is this equation:

$$M = \sum\limits_{i = 1}^{\log n} {\frac{{in}}{{{2^i}}}} = n\sum\limits_{i = 1}^{\log n} {\frac{i}{{{2^i}}}} \leqslant n\sum\limits_{i = 1}^\infty {\frac{i}{{{2^i}}} = 2n}$$

And I don't understand why the rightmost summation can be simplified to 2n. Can you please explain it to me?

migrated from stackoverflow.comApr 24 '12 at 12:33

This question came from our site for professional and enthusiast programmers.

• We have the identity $\sum\limits_{k=1}^\infty kx^k=\frac{x}{(1-x)^2}$, which can be derived from differentiating the usual geometric series. Now, take $x=\frac12$... – J. M. is a poor mathematician Apr 24 '12 at 12:44

Knowing that: $$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots = 1$$
We have: $$\begin{eqnarray*} \sum_{i=1}^\infty \frac{i}{2^i} &=& \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \cdots \\ &=& (\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots) + (\frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots) + (\frac{1}{8} + \frac{1}{16} + \cdots) + \cdots \\ &=& 1 + \frac{1}{2} + \frac{1}{4} + \cdots \\ &=& 2 \end{eqnarray*}$$