Matemáticas concretas - Torres de Hanoi Relación de recurrencia

Question

He decidido sumergirme en las Matemáticas Concretas a pesar de haber hecho sólo un par de años de matemáticas de licenciatura hace muchos años. Estoy buscando trabajar a través de todo el material, mientras que tapar las lagunas en mi conocimiento no importa lo grande que son.

Sin embargo, la resolución de la relación de recurrencia 1.1 - Las Torres de Hanoi me está causando problemas.

La relación de recurrencia es la siguiente:

$T_0 = 0$
$T_n=2T_{n-1}+1$ para $n>0$

Para encontrar la forma cerrada el libro suma 1 a ambos lados de las ecuaciones para obtener:

$T_0+1=1$
$T_n+1=2T_{n-1}+2$

Entonces dejamos que $U_n=T_n+1$ . Ahora me pierdo. ¿Cómo puedo pasar de la línea de arriba a la segunda línea de abajo después de la sustitución de $U_n$ . Parece que me falta algo sencillo.

$U_0=1$
$U_n=2U_{n-1}$

Luego el libro continúa diciendo:

No hace falta ser un genio para descubrir que la solución a este la recurrencia es sólo $U_n=2^n$ Por lo tanto $T_n=2^n-1$ .

De nuevo, estoy perdido, ¿cómo puedo llegar a $U_n=2^n$ ?

Un poco descorazonador teniendo en cuenta que se supone que esto es muy fácil.

Se agradece cualquier ayuda. Gracias.

Answer 1

Sólo te falta un poco de álgebra. Tienes $U_n=T_n+1$ para todos $n\ge 0$ Así que $U_{n-1}=T_{n-1}+1$ y por lo tanto $2T_{n-1}+2=2(T_{n-1}+1)=2U_{n-1}$ . Combine esto con $T_n+1=2T_{n-1}+2$ y $U_n=T_n+1$ y se obtiene $U_n=2U_{n-1}$ con $U_0=1$ .

Ahora, fíjate en que $U_n$ se duplica cada vez que $n$ se incrementa en $1$ :

$$\begin{align*} U_1&=2U_0\\ U_2&=2U_1=2^2U_0\\ U_3&=2U_2=2^3U_0\\ U_4&=2U_3=2^4U_0 \end{align*}$$

Está claro que el patrón va a persistir, por lo que conjeturamos que $U_n=2^nU_0$ para cada $n\ge 0$ . Esto es ciertamente cierto para $n=0$ . Supongamos que es cierto para algunos $n\ge 0$ Entonces $$U_{n+1}=2U_n=2\cdot2^nU_0=2^{n+1}U_0\;,$$ y la conjetura se deduce por inducción matemática.

Ahora volvemos a utilizar el hecho de que $U_0=1$ para decir que $U_n=2^n$ para cada $n\ge 0$ y por lo tanto $T_n=U_n-1=2^n-1$ .

En mi respuesta a esta pregunta He resuelto otro problema utilizando esta técnica; puede que la explicación que aparece allí te resulte útil.