El principio recursivo descrito por LA TORRE DE HANOI

La Torre de Hanói fue inventada por el matemático chino Edward Lucas en 1883. Dada una torre que consta de 8 discos, los discos se colocan en una de las tres pilas en orden de tamaño decreciente.

Comencemos con dos discos de tamaño mínimo

T 0 =0

T n =2T n-1 +1

El Se ha completado la fórmula recursiva normal. Podemos realizar además cálculos de fórmulas (inducción matemática)

T 0 +1=1

T n +1=2T n-1 +2

If Let U n =T n +1, entonces tenemos

U n =2U n-1 =>U n =2 n

Esto se deriva