The sum of powers of $2$ that are less than or equal to $n$ is less than $2n$.

Question

I am working with an amortised analysis problem where the given solution states that $$\sum\{2^k:0<2^k\le n\}<2n$$ I am not mathematically literate; is there a simple way to prove this or at least calculate said sum?

Answer 1

hint

$$2^0+2^1+...+2^p=2.2^p-1<2\cdot 2^p$$

if $2^p\le n$, then the sum is $<2n$.

For example, take $n=9$ then $p=3$.

$$2^0+2^1+2^2+2^3=15<18.$$

Answer 2

If $k = \lfloor \log n \rfloor$ then you would like to prove that $$ \sum_{i=0}^k 2^i < 2n $$

Note that by summing the geometric series, $$ \sum_{i=0}^k 2^i = \frac{2^{k+1}-1}{2-1} = 2\cdot 2^k - 1 = 2 \cdot 2^{\lfloor \log n \rfloor}-1 < 2n-1 < 2n. $$

Answer 3

Assume, that $n\in \{2^m, 2^m+1, ..., 2^{m+1}-1\}$.

We have $$\sum_{k=0}^{m} 2^k = \frac{1-2^{m+1}}{1-2} = 2^{m+1}-1 < 2^{m+1} =2\cdot 2^m\leq 2n$$