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?
What is the $\sum\limits_{i=0}^{\ (\log_2(n))-1)}\frac{n}{2^i}$?
1
$\begingroup$
logarithms
exponential-sum
-
0Do you mean to find $$\sum_{0}^{\log_{2}(n-1)}\left( \frac{n}{2^i}\right) $$ ? – 2012-05-10
-
0Is 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
-
1What happens if $\log_2(n-1)$ is not an integer? Do you mean $\lfloor \log_2(n-1) \rfloor$? – 2012-05-10
-
2Formally, $$n\sum_{k=0}^m 2^{-k}=n\left(2-2^{-m}\right)$$ Replace $m$ with that expression you need... – 2012-05-10
-
0Thanks 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
-
0Maybe 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
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) $$
-
1Technically $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
-
0I did not see that (Oops!..You have already mentioned that) – 2012-05-10