I have a summation series of the form: $n + n/2 + n/4 + n/8 + n/16 +\ldots + 1$. Is there a formula for this series? Basically, the denominators are powers of 2.
Asked
Active
Viewed 9,741 times
0
-
1why the last term is $1$, shouldn't it be $\frac{n}{2^q}$ – user5402 Jul 21 '13 at 18:27
-
Is each term the integer part of the last term divided by 2? What happens when $n = 6$? What is the sum then? – marty cohen Jul 21 '13 at 20:56
2 Answers
2
There is : it is the sum of the $\log n + 1$ first terms of a geometric series: $$ \sum_{i=0}^{\log n} \frac{n}{2^i} = n\sum_{i=0}^{\log n} 2^{-i} = n\cdot\frac{1-\frac{1}{2^{\log n + 1}}}{1-\frac{1}{2}} = 2n\left(1-\frac{1}{2n}\right) = 2n - 1 $$
Remark: $\log$ is the binary logarithm, not the natural (i.e., $\ln$) one.
Clement C.
- 67,323
-
Thank you very much for your explanation. Can you please explain how summation of
2^(-1)becomes the fraction(1-(1/2^(log n + 1))/1 - 1/2? If you can direct me to a resource, I can read more about it. – John Doe Jul 21 '13 at 19:11 -
It comes for the closed-form formula for a geometric progression (with ratio $\neq 1$); see for instance this page. – Clement C. Jul 21 '13 at 19:15
1
Let $n=2^k$, the summation is $$1+2+2^2+...+2^k=\frac{1-2^{k+1}}{1-2}=2(2^k)-1=2n-1.$$
eccstartup
- 1,126