3
$\begingroup$

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?

  • 4
    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$...2012-04-24

2 Answers 2

7

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

1

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.

  • 0
    My bad - yes, that does seem to be correct - see: http://www.wolframalpha.com/input/?i=sum%28i%2F2%5Ei%292012-04-24