# What is the $\sum\limits_{i=0}^{\ (\log_2(n))-1)}\frac{n}{2^i}$?

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?

-
Do you mean to find $$\sum_{0}^{\log_{2}(n-1)}\left( \frac{n}{2^i}\right)$$ ? – Babak S. May 10 '12 at 10:46
Is that actually what you mean? Is $n$ from a certain set (say, the powers of 2?), in which case is your summation limit correct? – Henry Gomersall May 10 '12 at 10:51
What happens if $\log_2(n-1)$ is not an integer? Do you mean $\lfloor \log_2(n-1) \rfloor$? – draks ... May 10 '12 at 10:52
Formally, $$n\sum_{k=0}^m 2^{-k}=n\left(2-2^{-m}\right)$$ Replace $m$ with that expression you need... – J. M. May 10 '12 at 10:53
Thanks for the comments, I edited the question to make it clearer I hope. – Paul Caheny May 10 '12 at 10:59

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)$$
Technically $log_2 (n)$ may not give integer value. Therefore it makes sense to use the floor function, i.e. instead of $m-1$, use $\left \lfloor log_2 n - 1\right \rfloor$ – Kirthi Raman May 10 '12 at 11:18