Más sobre inducción

¿Has visto ya el vídeo que subí hace unos días en el que te contaba lo que es la inducción matemática? Si todavía no lo has hecho, ahora es el mejor momento, porque en este post resolveré el problema que te proponía al final del vídeo.

Tras ver un par de ejemplos de cómo funciona la inducción y cómo se utiliza en las demostraciones, te pedía que probaras que n³ - n es múltiplo de 3 para todo n natural. Veamos, pues, cómo se podría demostrar. Obviamente, ya que el tema que estamos tratando es la inducción, haremos una prueba por inducción.

<< Caso base: n = 0. Cuando n = 0, nuestra expresión se convierte en 0³ - 0, que es igual a 0. Y comprobamos que, trivialmente, es múltiplo de 3.

Paso de inducción: n --> n+1. Asumimos que n³ - n es múltiplo de 3 para un cierto n. Debemos demostrar que la propiedad también se cumple para n+1, es decir, que (n+1)³ - (n+1) es múltiplo de 3. Si desarrollamos ese cubo, la expresión pasa a ser n³ + 3n² + 3n + 1 - n - 1 = n³ - n + 3(n² + n). La primera mitad, n³ - n, por la hipótesis de inducción, es múltiplo de 3. La segunda mitad también, porque aparece un 3 como factor. Por lo tanto, la expresión entera es múltiplo de 3, que es lo que queríamos probar.

Así, aplicando el principio de inducción, hemos demostrado que n³ - n es múltiplo de 3 para todo n natural. >>

Además de esta pequeña demostración, quería enseñarte otra cosa en este post. Al aplicar el principio de inducción, es muy importante comprobar las dos condiciones, ya que una laxitud en este aspecto puede dar lugar a resultados muy absurdos. Aquí te muestro dos de estas "falsas demostraciones".

En primer lugar, todo número natural es mayor que 1000. Esto es obvio, ¿no? 1031, 2000, 37465,... son todos mayores que 1000. ¿Cómo? ¿Que no estás convencido del todo? No te preocupes, que yo te lo demuestro rápidamente.

<< Supongamos, como hipótesis de inducción, que n es un número natural mayor que 1000. Tenemos que demostrar que n + 1 es también mayor que 1000. Pero, si n > 1000, entonces está claro que n + 1 > 1001 > 1000, por lo que hemos probado nuestro resultado. >>

Ves dónde está el fallo, ¿verdad? Es cierto que se cumple la segunda condición, la del paso de inducción, pero no hemos comprobado nada acerca del caso base, cuando n = 0 (que, obviamente, NO es mayor que 1000). Esto hace que todo el castillo de naipes se derrumbe sin una base sólida, lo habíamos construido en el aire.

Veamos otro ejemplo: para todo número natural n, si a y b son dos números naturales tales que el mayor de ellos es igual a n, entonces a = b. Es decir, que como entre 2 y 3, el mayor es 3, tenemos que 2 = 3. Y, como corolario, ¡todos los números son iguales! Esto es así por la siguiente razón:

<< Caso base: n = 0. Hemos aprendido de antes, tenemos que comprobar los cimientos del castillo de naipes. Cuando n = 0, sean a y b dos números naturales tales que el mayor de ellos es igual a 0. Como los naturales comienzan en 0, no hay ningún número por debajo, así que, trivialmente, a = b = 0 para que el máximo sea 0.

Paso de inducción: n --> n+1. Asumimos el enunciado para n y lo probaremos para n + 1: sean a y b dos números naturales tales que el mayor de ellos es n + 1. Entonces, si restamos una unidad a todo, es obvio que el máximo entre a - 1 y b - 1 es n. Pero aquí podemos aplicar nuestra hipótesis de inducción: a - 1 = b - 1. Simplificando esa igualdad, llegamos a a = b, lo que completa nuestra demostración >>

Se cumple el caso base y se cumple el paso de inducción, pero el resultado es claramente erróneo. ¿Qué es lo que ha ocurrido? Bueno, aquí el fallo está un poco más escondido. Intenta encontrarlo por tu cuenta antes de continuar leyendo el siguiente párrafo.

Es cierto que el caso base se cumple, pero el paso de inducción contiene un pequeñísimo detalle que hace que todo el castillo se desmorone. Lo que he afirmado en la demostración es verdadero... casi siempre, pero no cuando a ó b valen 0. Mi argumento se basaba en que podía aplicar la hipótesis de inducción a los números naturales a - 1 y b - 1. Pero si, al menos, uno de a ó b es 0, entonces obtenemos un valor negativo al calcular a - 1 y b - 1. En este caso, nos saldríamos del ámbito de los naturales y no podríamos aplicar la hipótesis de inducción, que claramente está enunciada para los naturales.

¿Y si quitásemos esa condición de que a y b tienen que ser números naturales? Entonces, sí, el paso de inducción se cumpliría, pero ahora el que fallaría sería el caso base (¿ves por qué?), por lo que el resultado seguiría sin funcionar.

Por eso hay que tener mucho cuidado con las demostraciones: aunque suenen correctas y naturales, a veces esconden pequeños fallos que hacen que todo el teorema se venga abajo. Y esto es justamente la razón de ser de los "proof assistants", de los que hablé hace algo más de un año.