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
    Do you mean to find $$\sum_{0}^{\log_{2}(n-1)}\left( \frac{n}{2^i}\right) $$ ?2012-05-10
  • 0
    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?2012-05-10
  • 1
    What happens if $\log_2(n-1)$ is not an integer? Do you mean $\lfloor \log_2(n-1) \rfloor$?2012-05-10
  • 2
    Formally, $$n\sum_{k=0}^m 2^{-k}=n\left(2-2^{-m}\right)$$ Replace $m$ with that expression you need...2012-05-10
  • 0
    Thanks for the comments, I edited the question to make it clearer I hope.2012-05-10
  • 0
    @J.M.: It is obviously the answer is given from your comment and the draks' one altogether. Is your statemnt supposed to be verified by induction?2012-05-10
  • 0
    @Babak: it's a truncated geometric series, no? There are standard methods for demonstrating that identity...2012-05-10
  • 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) $$

  • 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$2012-05-10
  • 1
    @KVRaman indeed, see my [comment](http://math.stackexchange.com/questions/143431/what-is-the-sum-limits-i-0-log-2n-1-fracn2i/143442#comment330480_143431) above. Let's see if the OP is fine with my answer...2012-05-10
  • 0
    I did not see that (Oops!..You have already mentioned that)2012-05-10