Estaba haciendo la prueba del número mínimo de operaciones necesarias para resolver una torre de Hanoi de n elementos, y me topé con un resultado que no pude demostrar... Lo pongo aquí en el foro. Digo que sé que da así, y la intuición me dice que es así, pero con intuición pura no se puede probar nada en matemáticas.
Procedo:
Defino la función Torre de Hanoi, notada por \( H_n \) como el número de intercambios necesarios para pasar una torre de Hanoi con \( n \) elementos de un poste a otro.
Para la función Torre de Hanoi, se tiene que \( H_1=1 \), y \( H_n=2H_{n-1}+1 \). Con \( n\in{\mathbb{N}} \) y \( n>0 \).
Al definir esta función, para \( n=4 \), tengo que:
\( H_4=2(2(2H_1+1)+1)+1 \), haciendo los reemplazos correspondientes.
Aplicando el axioma de distributividad, llego a que esto se puede escribir como
\( 2^3\cdot{H_1}+2^2+2^1+2^0 \), que se puede escribir como \( \displaystyle\sum_{i=0}^{4-1}2^n \).
Hasta aquí todo bien....
Sin embargo, estoy seguro de que esto aplica para todos los números naturales, pero no sé cómo hacer la demostración por inducción de esto, y la prueba solamente suponiendo que esto ocurre para todo \( n\in{\mathbb{N}} \) es lo que me tiene dudando (quiero llegar a que \( H_n=\displaystyle\sum_{i=0}^{n-1}{2^n} \)).
Con la prueba de este resultado demuestro los pasos necesarios para armar una torre de Hanoi, pero esta prueba no sé cómo hacerla.
Si me pueden echar una mano, muchas gracias
PD: Con el "teorema" de la torre de Hanoi quiero probar que \( \displaystyle\sum_{i=0}^n{\displaystyle\binom{n}{i}}=2^n \), así que por favor, no me respondan usando ese teorema
