La idea detrás de la suma de potencias de 2

Question

Sé que la suma de la potencia de $2$ es $2^{n+1}-1$ y conozco la prueba de inducción matemática. Pero ¿alguien sabe cómo $2^{n+1}-1$ aparece en primer lugar.

Por ejemplo, la suma de n números es $\frac{n(n+1)}{2}$ . La idea es que replicamos el conjunto y lo ponemos en un rectángulo, de ahí que podamos hacer el truco. ¿Cuál es la lógica de la suma de potencias de $2$ ¿Fórmula?

Answer 1

La expansión binaria de $\sum_{k=0}^n2^k$ es una cadena de $n+1$ 1's: $$\underbrace{111\dots111}_{n+1}$$ Si sumo un 1 a este número, ¿qué obtengo? $$1\underbrace{000\dots000}_{n+1}$$ 1 seguido de $n+1$ 0, por lo tanto $2^{n+1}$ . Por lo tanto $$\sum_{k=0}^n2^k=2^{n+1}-1$$

Answer 2

Esto funciona para cualquier suma parcial de series geométricas.

Sea $S = 1 + x + x^2+\ldots +x^n$ . Entonces $xS = x + x^2 + \ldots +x^n + x^{n+1} = S - 1 + x^{n+1}$ .

Todo lo que tienes que hacer ahora es resolver para $S$ (suponiendo $x\neq 1$ ).

Answer 3

Existe una explicación geométrica.

Coge una caja lo suficientemente larga para meter el doble de objetos que el último término de la suma, e intenta empaquetarla.

Tomemos una caja de longitud $2 * 2^n$ .

Pongamos los elementos del primer término ( $2^n$ ) en la caja. Ahora queda exactamente la mitad del espacio para los otros términos, de $2^{n-1}$ hasta $1$ así que repetimos este proceso, empezando por el siguiente término más grande.

A medida que colocamos los elementos de cada término, observamos que ocupan exactamente la mitad del espacio vacío que queda en la caja, porque tanto el término más grande que queda como el espacio que queda disminuyen a la mitad en cada paso.

En algún momento llegamos al primer término, que es igual a 1, y quedan dos lugares vacíos en la caja para un solo elemento, por lo que después de colocar el último elemento en la caja, aún queda espacio para un elemento más.

La longitud de la caja es $2*2^n = 2^{n+1}$ pero podría acortarse en uno, que es $2^{n+1} - 1$ y esta es nuestra fórmula.

Por ejemplo, empaquemos: $$\sum_{i=0}^3 2^i$$

Longitud de la caja: $$2 * 2^3 = 16$$

2^3    |● ● ● ● ● ● ● ●|               |
2^2    |○ ○ ○ ○ ○ ○ ○ ○|● ● ● ●|       |
2^1    |○ ○ ○ ○ ○ ○ ○ ○|○ ○ ○ ○|● ●|   |
2^0    |○ ○ ○ ○ ○ ○ ○ ○|○ ○ ○ ○|○ ○|●| |

Podría ser más corto por uno: $$2^{3+1}-1 = 15$$

Por cierto, se puede utilizar una explicación geométrica similar para la progresión geométrica siempre decreciente $\sum_{i=0}^\infty 2^{-i}$ con la única diferencia de que no necesitamos tener en cuenta el último trozo de espacio vacío, porque tiende a 0. En su lugar, tomamos como ejemplo algún medio continuo, como una cinta o un hilo, que puede dividirse virtualmente de forma infinita para que sume exactamente una longitud de 2 unidades.

Answer 4

Otra prueba pictórica, similar a la respuesta del empaquetado en cajas, consiste en contar el número de nodos de un árbol binario completo con n+1 niveles.

$$\sum_{i = 0}^{n} 2^i$$

es el número de nodos del árbol binario completo para los niveles 0 (la raíz) a n.

Si dibujas un ejemplo y numeras los nodos así

       1  
     /   \
    2     3
   / \   / \
  4   5 6   7 
 / \ 
8   ...

etc. observará que el nodo situado más a la izquierda de cada nivel es una potencia de 2 (1, 2, 4, 8, 16, ...).

por lo que el número de nodos en el árbol desde la raíz hasta el nivel n es 2^{n+1} - 1.

$$ \sum_{i = 0}^{n} 2^i = 2^{n+1} - 1 \,.$$

Answer 5

Otro enfoque famoso es contar los $2$ -partidas de jugadores para determinar un ganador entre $2^{n+1}$ personas. Es $2^{n+1}-1$ el número de personas a eliminar. También es $2^n$ personas eliminadas en la primera ronda, reduciéndose a la mitad cada ronda hasta llegar a la final.