Las múltiples caras del razonamiento por inducción

-

Consideremos una propiedad $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ enunciada para cierto número natural n. Para demostrar que esta propiedad es verdadera para todo número natural, se puede proceder en dos pasos.

El primero, el caso base, consiste en demostrar que $\mathcal{P}(0)\backslash mathcal\{P\}(0)$ es verdadera.

El segundo, el paso inductivo, consiste en mostrar que, si $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ es verdadera para un número natural n cualquiera, entonces $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ también lo es. Este principio suele ilustrarse con una fila de fichas de dominó que caen unas tras otras cuando se empuja la primera.

Existen varios refinamientos de este principio, que siguen siendo equivalentes a esta «inducción simple». Por supuesto, se puede iniciar el razonamiento a partir de un número entero no nulo n₀, y se concluirá que $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ es verdadera para todo entero n mayor o igual que n₀. También se puede aplicar una «inducción doble»; en ese caso, se demuestra que $\mathcal{P}(0)\backslash mathcal\{P\}(0)$ y $\mathcal{P}(1)\backslash mathcal\{P\}(1)$ son verdaderas y, después, que si $\mathcal{P}(n-1)\backslash mathcal\{P\}(n\; -\; 1)$ y $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ son verdaderas, entonces $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ también lo es. Incluso se puede llegar a una «inducción fuerte», en la que, para demostrar que $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ es verdadera, se supone que la propiedad es verdadera para todos los enteros menores.