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

• 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. isn't a mathematician Apr 24 '12 at 12:44

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*}$$

You need to know that:

sum ( i / 2^i ) = sum ( 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ... ) = 2

(It's an arithmetic-geometric series.)

From there the rest should be obvious.