Demostraciones con recursión e inducción

Cuando se trabaja con definiciones y algoritmos recursivos, es importante poder demostrar que realmente hacen lo correcto. El método natural para ello es la inducción matemática. La inducción se parece a la recursión: se empieza con un paso base y luego se muestra que si la afirmación es válida para un paso, también lo es para el siguiente.

Ejemplo 1: Factorial

Queremos demostrar que la definición recursiva del factorial corresponde a la fórmula habitual del producto:

$$ \large n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \quad n \geq 1 $$

Base

Para $ \large n = 1 $:

$$ \large 1! = 1 \quad \text{se cumple} $$

Paso de inducción

Supongamos que la afirmación es válida para un cierto $ \large n $, es decir

$$ \large n! = 1 \cdot 2 \cdot \ldots \cdot n $$

Entonces, para $ \large n+1 $:

$$ \large (n+1)! = (n+1) \cdot n! $$

Por la hipótesis de inducción podemos sustituir $ \large n! $:

$$ \large (n+1)! = (n+1) \cdot (1 \cdot 2 \cdot \ldots \cdot n) $$

Así obtenemos exactamente el producto hasta $ \large n+1 $. Por lo tanto, la afirmación es válida para todo $ \large n $.

Ejemplo 2: Fibonacci

La sucesión de Fibonacci se define por

$$ \large F_{0} = 0, \quad F_{1} = 1, \quad F_{n} = F_{n-1} + F_{n-2} \;\; (n \geq 2) $$

Una fórmula conocida dice que la suma de los primeros $ \large n $ números de Fibonacci es:

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

Base

Para $ \large n = 0 $ tenemos a la izquierda la suma $ \large F_{0} = 0 $.

A la derecha tenemos $ \large F_{2} - 1 = 1 - 1 = 0 $.

Ambos lados dan el mismo resultado, por lo que la afirmación es válida en el caso base.

Paso de inducción

Supongamos que la afirmación es válida para un cierto $ \large n $:

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

Lo mostramos para $ \large n+1 $:

$$ \large F_{0} + F_{1} + \ldots + F_{n} + F_{n+1} $$

$$ \large = (F_{n+2} - 1) + F_{n+1} \quad \text{(por hipótesis de inducción)} $$

$$ \large = F_{n+1} + F_{n+2} - 1 $$

$$ \large = F_{n+3} - 1 $$

Por lo tanto, la afirmación también es válida para $ \large n+1 $. Por inducción, la fórmula es válida para todo $ \large n $.

Ejemplo 3: Corrección de un algoritmo recursivo

Antes vimos el algoritmo que encuentra el máximo en una lista:

function max(list):
    if list has length 1:
        return list[0]            // base
    else:
        m = max(rest of list)     // paso recursivo
        return the larger of list[0] and m

Queremos demostrar que el algoritmo siempre devuelve el elemento más grande de la lista.

Base

Si la lista tiene longitud 1, el algoritmo devuelve el único elemento. Esto es correcto, ya que un solo elemento es obviamente el máximo.

Paso de inducción

Supongamos que el algoritmo funciona correctamente para todas las listas de longitud $ \large n $. Debemos mostrar que también funciona para una lista de longitud $ \large n+1 $.

Sea la lista $ \large [x_0, x_1, \ldots, x_n] $. El algoritmo se llama a sí mismo con la sublista $ \large [x_1, \ldots, x_n] $, que tiene longitud $ \large n $. Por la hipótesis de inducción, esta llamada devuelve correctamente el máximo de la sublista.

Finalmente, el algoritmo compara este máximo con el primer elemento $ \large x_0 $. Así devuelve el mayor de todos los elementos $ \large x_0, x_1, \ldots, x_n $, es decir, el máximo de toda la lista.

Conclusión

Por inducción, el algoritmo max siempre devuelve el elemento más grande de una lista, cualquiera que sea su longitud.

Resumen

La inducción es el método natural para demostrar la corrección de las definiciones recursivas. Se muestra que la base es válida, y que si la afirmación es válida en un paso, también lo es en el siguiente. Así queda cubierta toda la construcción infinita. Esto hace de la inducción una herramienta fundamental en el trabajo con la recursión.