En su estructura moderna, el principio se basa en dos pasos fundamentales para demostrar que una propiedad \( \mathcal{P}(n) \) es cierta para todo número natural \( n \):
- Caso base o inicio de inducción: Probar que la afirmación es verdadera para el primer valor (habitualmente \( n=0 \) o \( n=1 \)).
- Paso inductivo o relación de inducción: Asumir que la afirmación es cierta para un número \( n=k \) arbitrario (Hipótesis de inducción) y demostrar que, bajo esa suposición, la afirmación también debe ser cierta para \( n=k+1 \) (Tesis de inducción o tesis inductiva).
Ejemplos
1.- Un ejemplo gráfico de aplicación de este principio, el lector lo puede encontrar en la entrada de este blog llamada La Torre de Hanoi y el fin del mundo.
2.- El problema del cocinero perezoso (también conocido como el problema de las líneas en el plano o los números perezosos del pastelero) plantea lo siguiente:
\(\mathcal{P}(n)\): El número máximo de trozos en los que se puede cortar una tortilla de patatas (pizza o pastel) mediante \(n\) cortes rectos es \( T(n) =\frac{n(n+1)}{2}+1\).
La siguiente imagen nos muestra lo que sucede al experimentar con los primeros cortes:
Relación de inducción.
- Asumimos que la fórmula es correcta para un número arbitrario de cortes \( k \ge 0 \). Es decir, suponemos cierto que: \( T(k) = \frac{k(k + 1)}{2} + 1\) (Hipótesis Inductiva).
- Debemos demostrar que, al añadir el corte número \( k + 1 \), el total de piezas \( p_{k+1} \) cumple la misma fórmula sustituyendo \( n \) por \( k + 1 \). Es decir, \( T(k+1) = \frac{(k + 1)(k + 2)}{2} + 1 \).
Notemos que, al realizar el corte número \(k + 1\), para maximizar el número de trozos, la nueva recta debe cruzar a las \(k \) rectas anteriores en puntos distintos. Por tanto, al cortar $k$ rectas, la nueva línea recta queda dividida en \(k + 1\) segmentos (los tramos interiores entre cruces más los dos extremos). Cada uno de esos \(k + 1\) segmentos atraviesa una trozo existente y la divide en dos partes, añadiendo exactamente 1 trozo nuevo por segmento. Por lo tanto, la relación de recurrencia es: \( T(k+1) = T(k) + k+1 \).
Utilizando la hipótesis inductiva en la relación de recurrencia anterior se tiene que: \[T(k+1) = T(k) + k+1= \frac{k(k + 1)}{2}+k+2= \frac{k(k + 1)+2(k+1)}{2}+1=\frac{(k + 1)(k + 2)}{2} + 1, \] tal como debíamos demostrar.
3.- Caso base o inicio de inducción es necesario. Si suprimimos el caso base o inicio de inducción podemos llegar a conclusiones erróneas, como en el siguiente ejemplo:
Queremos probar la proposición \( \mathcal{P}(n) \), la cual afirma que \( n = n + 1 \) para todo número natural \( n \).
Si suprimimos el caso base, por hipótesis de inducción tenemos que para \( n=k \) se cumple que \( k=k+1 \). Entonces debemos demostrar que \( \mathcal{P}(k+1) \) es cierta. Sumamos \( 1 \) a ambos lados de la igualdad de la hipótesis y obtenemos \( k + 1 = (k + 1) + 1 \). Dado que hemos llegado exactamente a la estructura \( \mathcal{P}(k+1) \), el paso inductivo es algebraicamente irreprochable: si la propiedad se cumpliera para \( k \), obligatoriamente se cumpliría para \( k+1 \). Pero no hemos comprobado un caso base (\( n = 1 \)) y, obviamente, si intentamos verificar si \( 1 = 1 + 1 \), vemos que \( 1 = 2 \) es totalmente falso.
4.- La relación de inducción es necesaria. La inducción incompleta (o inducción empírica) es un tipo de razonamiento inductivo en el cual se extrae una conclusión general a partir de la observación empírica de solo una muestra de casos donde se cumple la propiedad \( \mathcal{P}(n) \). Si queremos probar que dicha propiedad se cumple para todo número natural \( n \) y obviamos el paso inductivo, podemos llegar a una conclusión errónea, como en el siguiente ejemplo debido al célebre matemático suizo Leonhard Euler:
Al evaluar el polinomio \( p(n) = n^2 + n + 41 \) para los primeros 40 enteros no negativos (\( 0 \le n \le 39 \)), obtenemos: \( p(0) = 41 \), \( p(1) = 43 \), \( p(2) = 47 \), \( p(3) = 53 \), \( \dots \), \( p(39) = 1601 \). Mediante esta observación empírica, en todos los 40 casos observados \( p(n) \) es un número primo, y esto pudiera llevarnos a afirmar que para todo número natural \( n \), el valor \( p(n) \) es un número primo. Sin embargo, al no haber realizado la demostración formal mediante el paso inductivo, la afirmación falla para \( n = 40 \), ya que \( p(40) = 1681 = 41^2 \), es decir, \( p(40) \) no es un número primo.
Destaquemos que los dos últimos ejemplos muestran que no podemos prescindir de niguno de los dos pasos con los que consta el principio de inducción, ambos son necesarios.
Antecedentes
Aunque no utilizó la inducción matemática formal, ni la notación algebraica moderna —ya que las matemáticas griegas eran fundamentalmente geométricas y visuales—, su razonamiento sigue una estructura recursiva e implícita paso a paso que anticipó el pensamiento inductivo.Euclides no intentó demostrar la infinitud hablando del «infinito» directamente (un concepto que los griegos evitaban), sino que demostró un procedimiento que siempre puede dar un paso más.
El razonamiento de Euclides, en versión moderna, es como a continuación:
- Supongamos que existen \(n\) números primos, donde \(n \in \mathbf{N}\) es fijo. Denotemos dicha lista de números pr1mos como \(\{p_1,p_2, \dots,p_n\}\).
- Ahora construyamos el número \(p_*=1+\prod_{k=1}^n p_k\). Notemos que \(p_*\) no es divisible por ninguno de los número primos que se encuentran en la lista, por tanto \(p_*\) es un número primo diferente de todos los que aparecen en la lista, lo que contradice nuestro supuesto de que solo existían \(n\) número primos.
En resumen, la demostración de Euclides se considera un antecesor del principio de inducción debido a que:
- Es un algoritmo constructivo: Euclides no solo afirma que existe otro primo, sino que muestra el mecanismo lógico exacto para encontrarlo a partir de cualquier lista dada.
- Carácter "Paso a Paso" (Mecanismo generador): El argumento demuestra que, dado cualquier número entero \(n\) de primos, siempre es posible generar al menos el primo \(n+1\). Al poder repetirse el proceso de manera indefinida, la lista nunca se agota.
Mucho más tarde, en el mundo islámico, el matemático Al-Karaji (aproximadamente por el año 1000) aplicó una forma primitiva de paso inductivo para demostrar la fórmula del binomio y la suma de cubos enteros. Lo que hizo Al-Karaji fue en lugar de demostrar una propiedad para un número general \(k\) y dar el salto al caso \(k+1\), utilizó un razonamiento escalonado: Demostraba la regla para \(n=1\), luego el caso \(n=2\) basándose en el resultado obtenido para \(n=1\)luego el caso \(n=3\) basándose en \(n=2\), y así sucesivamente para varios números (por ejemplo, hasta el 5 o 10). Al observar que el patrón se repetía de manera idéntica, añadía una frase que significaba "y así sucesivamente hasta el infinito", generalizando la regla.
En resumen, aunque le faltaba la formalización rigurosa que se logró siglos después con la abstracción algebraica moderna, Al-Karaji fue el primero en estructurar un argumento de naturaleza inductiva para demostrar patrones numéricos infinitos.
El camino hacia el rigor
- Francesco Maurolico y la primera demostración explícita (1575). El sacerdote y matemático siciliano Francesco Maurolico publicó Arithmeticorum libri duo. En esta obra demostró explícitamente que la suma de los primeros \(n\) números impares es igual a \(n^2\), estableciendo primero el caso base y demostrando formalmente que si la propiedad se cumple para un número, se cumple para el siguiente.
- Blaise Pascal y el Triángulo Aritmético (1654). Pascal formalizó y popularizó el método en su Traité du triangle arithmétique. Pascal utilizó el principio explícitamente para demostrar las propiedades de los coeficientes binomiales, reconociendo el patrón dual: probar la verdad del primer caso y demostrar que la verdad de un caso implica la del siguiente.
- Adopción del nombre 'Inducción' en 1838. Aunque Jacob Bernoulli y De Moivre contribuyeron a su desarrollo en los siglos XVII y XVIII, fue Augustus De Morgan quien acuñó oficialmente el término "Mathematical Induction" en un artículo para la Penny Cyclopaedia, dándole una identidad clara dentro del análisis matemático.
- Axiomatización formal (1889). El matemático italiano Giuseppe Peano incluyó la inducción como uno de sus célebres Axiomas de Peano para construir los números naturales. A partir de este momento, la inducción dejó de ser solo una técnica de demostración para convertirse en la definición axiomática misma del conjunto de los números naturales.
En definitiva, la inducción matemática es mucho más que un simple formalismo técnico: es el resultado de un fascinante viaje histórico que comenzó con los ingeniosos razonamientos iterativos de pioneros como Euclides y Al-Karaji y que, con el paso del tiempo, evolucionó hasta convertirse en uno de los pilares lógicos que hoy nos permiten tender un puente sólido entre lo particular y lo general, y pasar de lo finito a lo infinito numerable. Comprender su evolución nos recuerda que detrás de cada demostración rigurosa hay siglos de curiosidad, ingenio y esfuerzo humano. Y nos muestra que, con una base sólida y una regla clara, incluso aquello que parece inalcanzable puede llegar a demostrarse.
Lecturas complementarias.
