Introducción a la Inducción Matemática

(Este texto pretende ser sólo una breve introducción a una nueva técnica de demostración para algunos de ustedes. Es un fragmento del libro "Principios de Olimpiada" de Alejandro Illanes, y tiene puntos importantes que se deben tener en cuenta para los nuevos; dichos puntos se pondrán en negritas. Las notas que tengan (*) son de mi parte.)


El principio de inducción para los números naturales (1, 2, 3, ...) podría enunciarse así:

Si empezáramos en el 1 y contáramos de uno en uno, entonces recorreríamos todos los números naturales.

Por supuesto, esto ya lo sabíamos desde que éramos niños. Lo que es útil es poderlo traducir a un planteamiento matemático que se pueda usar para demostrar propiedades de estos números. La dificultad se centra en poder decir qué significa la frase "contar de uno en uno". Observemos que el enunciado se puede traducir así:

Si somos capaces de empezar en el 1 y somos capaces de saltar de cualquier número al siguiente, entonces seremos capaces de llegar a cualquier número natural.

Discutamos un poco más este enunciado. Nos dice que podemos empezar en el 1, y que podemos saltar de cualquier número al siguiente. Ya estando en el 1, el enunciado nos dice que podemos saltar al 2, ya que estamos en el 2, podemos saltar al 3, etc. De esta manera podemos llegar a cualquier número natural.

Esta segunda formulación es útil porque la podemos traducir a un enunciado matemático preciso. Hagámoslo pues:

Sea \(A\) un subconjunto de \(\mathbb{N}\). Si \(1 \in A\) y cada vez que un número está en \(A\), también está el siguiente, podemos concluir que \(A = \mathbb{N}\).

La manera más usual (y como aparece en los libros) de enunciar este principio es:

Supongamos que \(A \subset \mathbb{N}\). Si se satisfacen las siguientes dos propiedades:  

1) \(1 \in A\), 

2) si \(n \in A\), entonces \(n+1 \in A\). 

Entonces \(A = \mathbb{N}\).

Nota (*): Teniendo esto en mente, ya podemos dar una definición más tradicional del principio de inducción matemática.

Principio de Inducción Matemática

Consideremos una propiedad \(P(n)\) definida* para todos los números naturales. Si podemos comprobar que:

1. \(P(1)\) es cierta y,
2. suponiendo que \(P(n)\) es cierta podemos dar la manera de comprobar que \(P(n+1)\) también es cierta,

Entonces \(P\) es una propiedad que es cierta para todos los números naturales.


Nota (*): Que la propiedad esté definida para todos los números naturales se puede interpretar como que tiene sentido para todos los naturales, MAS NO SIGNIFICA QUE NECESARIAMENTE ES CIERTA PARA TODOS LOS NATURALES. Aguas con eso.

A primera vista, podría parecer que este principio no es muy útil. Sin embargo es la herramienta matemática más fuerte para demostrar propiedades de los números naturales. A continuación se dará un ejemplo de cómo se aplica.

Ejemplo.
Demuestra que para toda \(n \in \mathbb{N}\) se tiene que \(\displaystyle 1+2+\ldots +n = \frac{n(n+1)}{2}\).

Solución y Análisis
De acuerdo con el principio de inducción matemática tenemos que comprobar dos cosas:

1. Primero tenemos que comprobar que esta fórmula vale para \(n=1\).
   
   
   El miembro de la izquierda de la igualdad, para \(n=1\), nos indica que sumemos desde 1 hasta 1. De manera que el miembro de la izquierda es igual a 1 (cuando \(n=1\)). Mientras que el miembro de la derecha es igual, para \(n=1\), a \(\displaystyle \frac{1(1+1)}{2}=1\). Por tanto, la fórmula es cierta cuando \(n=1\).
2. Supongamos que la fórmula es válida para una \(n\) fija. A partir de que se cumple para \(n\) tenemos que decir cómo podríamos comprobarla para \(n+1\). Es decir, tenemos que ver cómo avanzar de un número natural al que le sigue. ¡OJO!, NO ES QUE ESTEMOS SUPONIENDO QUE LA FÓRMULA ES CIERTA PARA TODA n, SINO QUE ESTAMOS SUPONIENDO QUE ES CIERTA PARA UNA n FIJA Y TENEMOS QUE VER CÓMO AVANZAR AL SIGUIENTE NÚMERO, ES DECIR, A n+1.
   
   Supongamos pues que \(\displaystyle 1 + 2 + \ldots + n = \frac{n(n+1)}{2}\).
   
   Veamos qué pasa pasa \(n+1\). Como
   \[ 1 + 2 + \ldots + n + (n+1) = [ 1 + 2 + \ldots + n ] + (n+1) \]
   y estamos suponiendo que ya sabemos calcular lo del paréntesis cuadrado, tenemos que
   \[ 1 + 2 + \ldots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1)+2(n+1)}{2} = \frac{(n+1)((n+1)+1)}{2} \]
   por lo tanto
   \[ 1 + 2 + \ldots + n + (n+1) = \frac{(n+1)((n+1)+1)}{2}. \]
   
   Así que la fórmula también vale para \(n+1\).

De manera que hemos comprobado la fórmula para el 1 y hemos visto cómo se avanzaría de un número al siguiente. Entonces, por el principio de inducción, la fórmula es válida para todos los números naturales. \(\square\)

Nota (*): En este último ejemplo, la propiedad \(P(n)\) fue \(1+2+\ldots +n = \frac{n(n+1)}{2}\).