Suma de potencias de 2 desde 1 hasta log(N).

Question

Me encontré con la siguiente suma: $\sum_{m=1}^{\log_2(N)} 2^{m}$ . Mi intuición me dice que debería estar acotado por 2N, pero ¿cómo demostrarlo?

Answer 1

$$\sum_{n=0}^d x^n= \frac{x^{d+1}-1}{x-1}$$

Así que tenemos:

$$\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 $$

Answer 2

Para cualquier $p \in \mathbb{N}$ que tienes: $$\sum_{m=1}^p 2^m = 2^{p+1}-2=2\cdot2^p - 2$$

Así que..: $$\sum_{m=1}^{\log_2(N)} 2^m = 2N-2$$ Que está delimitada por $2N$