Processing math: 100%

60 votos

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

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

Por ejemplo, la suma de n números es 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?

130voto

Technophile Puntos 101

La expansión binaria de nk=02k es una cadena de n+1 1's: 111111n+1 Si sumo un 1 a este número, ¿qué obtengo? 1000000n+1 1 seguido de n+1 0, por lo tanto 2n+1 . Por lo tanto nk=02k=2n+11

21voto

Ennar Puntos 1760

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

Sea S=1+x+x2++xn . Entonces xS=x+x2++xn+xn+1=S1+xn+1 .

Todo lo que tienes que hacer ahora es resolver para S (suponiendo x1 ).

12voto

titaniumdecoy Puntos 7548

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 22n .

Pongamos los elementos del primer término ( 2n ) en la caja. Ahora queda exactamente la mitad del espacio para los otros términos, de 2n1 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 22n=2n+1 pero podría acortarse en uno, que es 2n+11 y esta es nuestra fórmula.

Por ejemplo, empaquemos: 3i=02i

Longitud de la caja: 223=16

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

Podría ser más corto por uno: 23+11=15

Por cierto, se puede utilizar una explicación geométrica similar para la progresión geométrica siempre decreciente i=02i 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.

7voto

Cromax Puntos 101

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.

ni=02i

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.

ni=02i=2n+11.

7voto

Tim Almond Puntos 1887

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X