I came across the following sum: $\sum_{m=1}^{\log_2(N)} 2^{m}$. My intuition tells me that this should be bounded by 2N, but how would I prove this?
Asked
Active
Viewed 1.1k times
2 Answers
2
$$\sum_{n=0}^d x^n= \frac{x^{d+1}-1}{x-1}$$
So we have:
$$\sum_{m=1}^{\log_2 N} 2^m=\sum_{m=0}^{\log_2 N} 2^m-2^0=\sum_{m=0}^{ \log_2 N } 2^m-1 = \frac{2^{\lfloor \log_2N \rfloor +1}-1}{2-1}-1 \leq \frac{N \cdot 2-1}{1}-1 \\=N \cdot 2-2 $$
evinda
- 7,823
-
This works exactly for a power of two. If $N$ is not a power of two the argument almost works but you have to interpret the log as a floor of the log base 2. – amcalde Apr 27 '15 at 17:19
-
It always holds that $2^{\log_2{x}}=x$, it doesn't depend on $x$. @amcalde – evinda Apr 27 '15 at 17:21
-
1Sure, but what does it mean to have $\sum_{i=1}^{5.5}$? – Batman Apr 27 '15 at 17:23
-
What you say is true. But I don't know how to do a discrete sum over an integer ($m$) when the upper limit is not an integer. Hence my comment. – amcalde Apr 27 '15 at 17:24
-
Ah, I see... @amcalde – evinda Apr 27 '15 at 17:25
-
If you wrap the final log in a floor function, then use a less than or equal to sign instead of the next equal sign. The argument is exactly right. – amcalde Apr 27 '15 at 17:32
-
@amcalde I edited my post. Do you agree with it now? – evinda Apr 27 '15 at 17:36
-
Yes. I already up voted. – amcalde Apr 27 '15 at 17:43
-
@amcalde Thank you :) – evinda Apr 27 '15 at 17:44
0
For any $p \in \mathbb{N}$ you have: $$\sum_{m=1}^p 2^m = 2^{p+1}-2=2\cdot2^p - 2$$
So: $$\sum_{m=1}^{\log_2(N)} 2^m = 2N-2$$ Which is indeed bounded by $2N$
mathcounterexamples.net
- 70,018