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?
 A: Knowing that:
$$ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots = 1 $$
And hence by removing successive terms from the left:
$$ \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots = \frac{1}{2} $$
$$ \frac{1}{8} + \frac{1}{16} + \cdots = \frac{1}{4} $$
$$ \vdots $$
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 \\
&& \text{Substituting the identites from above:} \\
&=& 1 + \frac{1}{2} + \frac{1}{4} + \cdots \\
&& \text{And substituting the first identity again:} \\
&=& 1 + 1 \\
&=& 2
\end{eqnarray*}$$
A: You need to know that:
sum ( i / 2^i ) = sum ( 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ... ) = 2

See: http://www.wolframalpha.com/input/?i=sum%28i%2F2%5Ei%29
(It's an arithmetic-geometric series.)
From there the rest should be obvious.
