1
$\begingroup$

What is the value of the following sum: $\sum\limits_{i=0}^{\ (\log_2(n))-1)}\frac{n}{2^i}$ Can you show how to go about arriving at the answer?

  • 0
    Maybe it helps, if @PaulCaheny would write out sum (without $\sum$) he's interested. If you restrict yourself to $n=2^m$ everthings fine.2012-05-10

1 Answers 1

1

You are dealing with a geometric sum, for which we have $ \sum_{k=0}^{m-1} ar^k= a \, \frac{1-r^{m}}{1-r}. $ In your case $a=n$, $r=2^{-1}$ and $m=\log_2(n)$. Substituting this gives: $ n \, \frac{1-2^{-\log_2(n)}}{1-\frac{1}{2}}=n\, \frac{1-1/n}{\frac{1}{2}}=2n(1-1/n)=2(n-1) $

  • 0
    I did not see that (Oops!..You have already mentioned that)2012-05-10