Ayuda con la prueba por inducción

Question

El autor genera una Torre de Hanoi y observa la secuencia:

$$1, 3, 7, 15, 31, 63,...$$

Adivina la relación de recurrencia a partir de los primeros términos:

$$H_{n} = 2^{n} - 1$$

Ahora quiere demostrarlo utilizando la prueba por inducción:

Caso base : Para $n = 1$ es verdad.

Caja de inducción : Supongamos por inducción que $H_{n - 1} = 2^{n - 1} - 1$ entonces

$$\begin{align*} H_{n} & = 2H_{n - 1} + 1 \\ & = 2(2^{n - 1} - 1) + 1 \\ & = 2^n - 1\end{align*} $$

No entiendo la ecuación anterior. Primero dice que $H_{n} = 2^{n} - 1$ y luego lo cambia por $H_{n} = 2H_{n - 1} + 1$ - No le encuentro la lógica.

Answer 1

La relación de recurrencia no es $$ H_{n}=2^{n}-1 $$

sino $$ H_{n}=2H_{n-1}+1 $$

(esto viene del problema de Hanoi)

Ahora suponemos que la solución a la recurrencia es $$ H_{n}=2^{n}-1 $$

y demostrar que esto es cierto utilizando la inducción.

Está el caso base que debe quedar claro, nuestra hipótesis sería sería $H_{n-1}=2^{n-1}-1$ y lo utilizaríamos para demostrar $$ H_{n}=2^{n}-1 $$

Utilizando la relación de recurrencia $$ H_{n}=2H_{n-1}+1 $$

y ahora utilizamos la hipótesis de inducción y establecemos $H_{n-1}=2^{n-1}-1$ y obtenemos $$ H_{n}=2(2^{n-1}-1)+1=2^{n}-2+1=2^{n}-1 $$

que es lo que queríamos probar

Answer 2

Creo que se debe a que el algoritmo general para resolver una Torre de Hanoi con $n$ anillos es resolver uno con $n-1$ para mover la base, y luego para resolver el $n-1$ torre. Para más detalles: http://www.sparknotes.com/cs/recursion/examples/section6.rhtml o simplemente busca en Google. Desde $n-1$ Torre de Hanoi requiere $H_{n-1}$ se mueve, $H_n$ debe exigir $H_{n-1}$ para mover inicialmente el $n-1$ anillos, más $1$ mover para mover el anillo base, y luego otro $H_{n-1}$ para mover el $n-1$ anillos de vuelta, para un total de $H_{n-1} + 1 + H_{n-1}=2H_{n-1}+1$