Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Do you mean to find $$\sum_{0}^{\log_{2}(n-1)}\left( \frac{n}{2^i}\right) $$ ? –  B. 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
1  
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
2  
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

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

share|improve this answer
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
1  
@KVRaman indeed, see my comment above. Let's see if the OP is fine with my answer... –  draks ... May 10 '12 at 12:15
    
I did not see that (Oops!..You have already mentioned that) –  Kirthi Raman May 10 '12 at 14:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.