<s>[INST] 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?
 [/INST] 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*}$$
</s>