Voy a demostrar por inducción sobre $n$ (número de discos). Deje $T(n)$ el número de movimientos necesarios para ir de una arbitraria de configuración para cualquier otra configuración. Deje $P(n)$ ser la proposición "$T(n)\leq 2^n-1$". Es decir, $P(n)$ es la proposición "Todos los de inicio y finalización de las configuraciones de $n$ discos son en la mayoría de las $2^n-1$ aparta.". Quiero mostrar que la $P(n)$ es verdadera para todo número natural $n$.
Para el caso base, $P(0)$ es cierto, porque es claro que $T(0)=0\leq 2^0-1=0$.
Por la hipótesis inductiva, vamos a suponer que $P(n-1)$ es verdadero; es decir, vamos a suponer que es cierto que $T(n-1)\leq 2^{n-1}-1$. Ahora, voy a demostrar que $P(n-1)$ implica $P(n)$.
Primer método
Supongamos que tengo una configuración de $n-1$ discos. Por la hipótesis inductiva, sabemos que $T(n-1)\leq 2^{n-1}-1$. Ahora, vamos a considerar lo que va a cambiar si queremos agregar un disco más ($n^{th}$ disco), más pequeño que cualquier otro disco en la configuración, así que tenemos una situación donde hay $n$ discos. Desde esta $n^{th}$ disco es el más pequeño, siempre va a estar en la parte superior de uno de los tres clavijas, debido a las reglas del problema.
La parte inferior $n-1$ discos hará $T(n-1)$ se mueve. Para cada movimiento de la $n-1$ discos, en el peor de los casos, el nuevo disco más pequeño será en la parte superior del disco que se quiere mover, o en la parte superior de la clavija para que el disco se quiere mover. Así, el nuevo disco se tiene que hacer en la mayoría de un solo movimiento, para cada movimiento de la otra $n-1$ discos, es decir, el nuevo disco hará que en la mayoría de las $T(n-1)$ se mueve. En el pasado, cuando el $n-1$ discos ya están en sus posiciones correctas en el fin de la configuración, el nuevo disco puede tener que hacer un turno para llegar a su posición correcta en la configuración final.
Por lo tanto, habrá en la mayoría de las $T(n) = T(n-1) + T(n-1) + 1 \leq 2^{n-1}-1+2^{n-1}-1+1 = 2^n - 2 + 1 = 2^n - 1$ se mueve. Por lo tanto, $T(n) \leq 2^n - 1$, lo que muestra que $P(n)$ es cierto.
Segundo método
También puedo construir el inductivo paso por considerar que el nuevo disco es el más grande de disco (en lugar de ser el más pequeño), como se explica en los comentarios de abajo.
Supongamos que tenemos una configuración de $n-1$ discos. Por la hipótesis inductiva, estos $n-1$ discos necesidad de $T(n-1) \leq 2^{n-1}-1$ se mueve para llegar a cualquier otro tipo de configuración. Ahora, vamos a añadir un $n^{th}$ disco, que es el más grande de disco. Tenemos dos casos:
(1) Si el más grande de disco no se mueve a partir de la configuración para la configuración final, luego podemos mover la parte superior $n-1$ discos como si sólo hubiera $n-1$ discos; de modo que, en este caso, se requiere en la mayoría de las $2^{n-1} - 1$ se mueve. Por lo tanto, es cierto que $T(n) \leq 2^{n} - 1$. Por eso, $P(n)$ se cumple en este caso.
(2) Si el más grande de disco se mueve, así que primero tenemos que mover a su configuración final. Para esto, tenemos que mover la parte superior $n-1$ discos a una clavija para que se fuera del camino; por la hipótesis inductiva, esto lleva a la mayoría de las $2^{n-1} - 1$ se mueve. Entonces, nos tenemos que mover el disco mayor a su posición correcta en la configuración final (1 turno). A continuación, nos movemos en la parte superior $n-1$ discos a sus posiciones correctas en el fin de la configuración (en la mayoría de las $2^{n - 1} - 1$ se mueve). Todo el procedimiento dura en la mayoría de las $2^{n-1} - 1 + 1 + 2^{n-1} - 1 = 2^n - 1$ se mueve. Por eso, $T(n) \leq 2^n - 1$. Esto demuestra que $P(n)$ se cumple en este caso.
