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

Question

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?

Answer 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) $$