Resolución del problema

Método de inducción

Ahora que ya tenemos una expresión con la que creemos se puede calcular el número de movimientos, tenemos que demostrar que es válida para las 64 piezas. Esto lo haremos por medio del método de inducción matemática.

Piensa en este método como una fila infinita de fichas de dominó alineadas. Cuando tiras la primera, la siguiente se cae en consecuencia, pero al caer la siguiente provocará que se caiga una tercera y así sucesivamente.

Otra forma de verlo es si demostramos que funciona para n+1 y funciona para 1, entonces funciona para 1+1. Y como funciona para 2, funciona para 2+1, y como funciona para 3, entonces funciona para 3+1... Y así podríamos seguir para cualquier valor de n.

En general, lo complicado es ver (demostrar) que, si es válido para n, al agregar un elemento más, es decir, sumarle 1, llegamos a una expresión que involucre a n+1.

Objetivo

Intentemos demostrar que el número mínimo de movimientos para n discos será 2ⁿ -1, haciendo uso de la inducción matemática.

Para ello sigamos los pasos que se listaron anteriormente.

1) Verificar un caso base (Caso Base)

En las escenas anteriores comprobamos que para 1, 2 y 3 discos se cumple la fórmula, ya que: $$\begin{align} 2^1 - 1 &= 1 \\ 2^2 - 1 &= 3 \\ 2^3 - 1 &= 7 \\ \end{align}$$ Por lo que ya tenemos por lo menos un caso base.

Es importante hacer notar que la n de nuestro caso base debe de ser lo más pequeña posible, ya que sólo podemos decir que es válido para las n mayores o iguales a nuestro caso base.

2) Suponer verdadero para $n$ (Hipótesis de inducción)

Este paso sólo consiste en decir que es válido para $n$. En nuestro caso, vamos a decir que la fórmula funciona para $n$ discos, es decir, que se cumple $2^n-1$ cuando tenemos $n$ discos. A partir de aquí, llamaremos hipótesis de inducción a la expresión $2^n-1$.

3) Demostrar que es valido al agregar un elemento más ($n +1$) (Paso inductivo)

Supongamos que ya movimos los discos de la torre a excepción del último, o dicho de otra manera, ya movimos una torre de $n$ discos a otro poste y le agregamos un disco más. Entonces tenemos que determinar cuántos movimientos nos faltan a partir de la configuración actual para mover una torre de $n+1$ discos.

Si observas, primero tuviste que mover el último disco al poste vacío ($1$ movimiento) y luego hiciste $2^n - 1$ movimientos para acomodar la torre que ya teníamos sobre el nuevo disco. Si hacemos la suma de la cantidad de movimientos nos da un total de $2^n - 1 + 1 = 2^n$.