El principio de inducción matemática es uno de los métodos de demostración más importantes de toda la matemática. Permite probar que una propiedad se cumple para todos los números naturales, transformando un problema con infinitos casos en un razonamiento finito, riguroso y controlable.
La idea de fondo es simple: si una propiedad es verdadera al principio y si, cada vez que es verdadera para un cierto número natural, resulta verdadera también para el siguiente, entonces es verdadera para todos los números naturales.
Índice
- Intuición del principio de inducción
- Enunciado del principio de inducción
- Base de la inducción y paso inductivo
- Por qué funciona la inducción
- Inducción a partir de un valor arbitrario
- Inducción y conjuntos inductivos
- Ejemplo 1: suma de los primeros números naturales
- Ejemplo 2: una desigualdad exponencial
- Principio del buen orden
- Equivalencia entre inducción y buen orden
- Inducción fuerte
- Errores frecuentes en las demostraciones por inducción
- Inducción y definiciones recursivas
- Conclusión
Intuición del principio de inducción
El principio de inducción se explica habitualmente mediante la imagen de las fichas de dominó.
Imaginemos una fila infinita de fichas. Para estar seguros de que todas caen, no es necesario comprobarlas una a una. Basta con verificar dos hechos:
- la primera ficha cae;
- cada ficha, al caer, hace caer la siguiente.
Si ambas condiciones se cumplen, entonces todas las fichas de la fila caerán.
En matemáticas ocurre algo análogo. Para demostrar que una propiedad \(P(n)\) se cumple para todo número natural \(n\), se verifica que vale para el primer valor y se demuestra que su validez en un número cualquiera implica la validez en el número siguiente.
Enunciado del principio de inducción
Sea \(P(n)\) una propiedad que depende de un número natural \(n\). El principio de inducción matemática afirma que, si se cumplen las dos condiciones:
\[ P(1) \text{ es verdadera} \]
y
\[ P(n) \Rightarrow P(n+1) \quad \text{para todo } n \geq 1, \]
entonces:
\[ P(n) \text{ es verdadera para todo } n\in\mathbb{N}, \ n\geq 1. \]
Si se adopta la convención de que los números naturales comienzan en \(0\), el caso base será \(P(0)\) y el paso inductivo será:
\[ P(n) \Rightarrow P(n+1) \quad \text{para todo } n\geq 0. \]
Base de la inducción y paso inductivo
Una demostración por inducción consta de dos momentos fundamentales.
1. Base de la inducción
Se demuestra que la propiedad es verdadera para el primer valor considerado, habitualmente \(n=1\) o \(n=0\).
Esta verificación es indispensable: sin un punto de partida, la cadena inductiva no puede comenzar.
2. Paso inductivo
Se supone que la propiedad es verdadera para un cierto número natural \(n\). Esta suposición recibe el nombre de hipótesis de inducción.
A partir de ella, se demuestra que la propiedad es verdadera también para \(n+1\).
En forma simbólica:
\[ P(n)\Rightarrow P(n+1). \]
Lo esencial es que no se está suponiendo que la propiedad sea verdadera para todos los números naturales. Se está demostrando una implicación: si la propiedad vale en un cierto punto de la cadena, entonces vale también en el punto siguiente.
Por qué funciona la inducción
El principio de inducción funciona porque los números naturales están construidos de forma ordenada y sucesiva:
\[ 1,2,3,4,\dots \]
o bien, si se parte de \(0\):
\[ 0,1,2,3,\dots \]
Una vez verificado el primer caso, el paso inductivo permite pasar del primero al segundo, del segundo al tercero, del tercero al cuarto, y así sucesivamente.
De este modo se genera una cadena infinita de implicaciones:
\[ P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow P(4)\Rightarrow \dots \]
La fuerza de la inducción reside precisamente en esto: un razonamiento finito logra controlar infinitos casos porque aprovecha la propia estructura de los números naturales.
Inducción a partir de un valor arbitrario
No es necesario que la cadena inductiva comience siempre en \(n=1\) o en \(n=0\). En muchas situaciones, una propiedad solo se hace verdadera a partir de cierto entero \(n_0\).
En este caso, el principio de inducción se enuncia así. Si:
\[ P(n_0) \text{ es verdadera} \]
y
\[ P(n)\Rightarrow P(n+1) \quad \text{para todo } n\geq n_0, \]
entonces:
\[ P(n) \text{ es verdadera para todo } n\geq n_0. \]
Por ejemplo, demostremos que:
\[ 2^n>n^2 \]
para todo \(n\geq 5\).
Base de la inducción
Para \(n=5\), tenemos:
\[ 2^5=32 \]
y
\[ 5^2=25. \]
Por tanto:
\[ 2^5>5^2. \]
Paso inductivo
Supongamos que, para cierto \(n\geq 5\), se tiene:
\[ 2^n>n^2. \]
Debemos demostrar que:
\[ 2^{n+1}>(n+1)^2. \]
Como:
\[ 2^{n+1}=2\cdot 2^n, \]
usando la hipótesis de inducción obtenemos:
\[ 2^{n+1}=2\cdot 2^n>2n^2. \]
Ahora observamos que, para todo \(n\geq 5\),
\[ 2n^2>(n+1)^2. \]
En efecto:
\[ 2n^2-(n+1)^2 = n^2-2n-1. \]
Para \(n\geq 5\), se tiene:
\[ n^2-2n-1=(n-1)^2-2\geq 4^2-2=14>0. \]
Por tanto:
\[ 2n^2>(n+1)^2. \]
Combinando ambas desigualdades, obtenemos:
\[ 2^{n+1}>2n^2>(n+1)^2. \]
Luego:
\[ 2^{n+1}>(n+1)^2. \]
El paso inductivo queda demostrado. Por el principio de inducción a partir de \(n_0=5\), concluimos que:
\[ 2^n>n^2 \]
para todo \(n\geq 5\).
La lógica no cambia: la cadena de implicaciones simplemente comienza desde un punto distinto.
Inducción y conjuntos inductivos
El principio de inducción puede formularse también en términos de conjuntos.
Un subconjunto \(A\subseteq\mathbb{N}\) se denomina inductivo si satisface dos condiciones:
\[ 1\in A \]
y
\[ n\in A\Rightarrow n+1\in A. \]
Dicho de otro modo, \(A\) contiene el primer número natural y, junto con cada número, contiene también su sucesor.
El principio de inducción afirma entonces que:
\[ \text{si } A\subseteq\mathbb{N} \text{ es inductivo, entonces } A=\mathbb{N}. \]
Esta formulación pone de manifiesto algo importante: la inducción no es únicamente una técnica para resolver ejercicios, sino una propiedad estructural del conjunto de los números naturales.
Ejemplo 1: suma de los primeros números naturales
Demostremos por inducción que, para todo \(n\geq 1\),
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Base de la inducción
Para \(n=1\), el miembro izquierdo es:
\[ 1. \]
El miembro derecho es:
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1. \]
La fórmula es, por tanto, verdadera para \(n=1\).
Paso inductivo
Supongamos que la fórmula es verdadera para cierto \(n\geq 1\), es decir, supongamos:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Debemos demostrar que entonces también vale:
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
Partimos del miembro izquierdo:
\[ 1+2+3+\dots+n+(n+1). \]
Por la hipótesis de inducción podemos sustituir la suma \(1+2+\dots+n\) por \(\frac{n(n+1)}{2}\):
\[ 1+2+\dots+n+(n+1)=\frac{n(n+1)}{2}+(n+1). \]
Factorizamos \(n+1\):
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right). \]
Como:
\[ \frac{n}{2}+1=\frac{n+2}{2}, \]
obtenemos:
\[ (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2}. \]
Por tanto:
\[ 1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
La propiedad es verdadera para \(n+1\). Por el principio de inducción, la fórmula vale para todo \(n\geq 1\).
Ejemplo 2: una desigualdad exponencial
Demostremos que, para todo \(n\in\mathbb{N}\) con \(n\geq 0\),
\[ 2^n\geq n+1. \]
Base de la inducción
Para \(n=0\), tenemos:
\[ 2^0=1 \]
y
\[ 0+1=1. \]
Por tanto:
\[ 2^0\geq 0+1. \]
La propiedad es verdadera para \(n=0\).
Paso inductivo
Supongamos que, para cierto \(n\geq 0\), se tiene:
\[ 2^n\geq n+1. \]
Debemos demostrar que:
\[ 2^{n+1}\geq n+2. \]
Observamos que:
\[ 2^{n+1}=2\cdot 2^n. \]
Usando la hipótesis de inducción:
\[ 2\cdot 2^n\geq 2(n+1). \]
Por tanto:
\[ 2^{n+1}\geq 2n+2. \]
Como \(n\geq 0\), se tiene:
\[ 2n+2\geq n+2. \]
En consecuencia:
\[ 2^{n+1}\geq n+2. \]
La propiedad vale también para \(n+1\). Por inducción:
\[ 2^n\geq n+1 \]
para todo \(n\geq 0\).
Principio del buen orden
El principio del buen orden afirma que todo subconjunto no vacío de \(\mathbb{N}\) posee un elemento mínimo.
En símbolos:
\[ A\subseteq\mathbb{N},\quad A\neq\varnothing \quad\Longrightarrow\quad \exists m\in A \text{ tal que } m\leq a \text{ para todo } a\in A. \]
El elemento \(m\) se denomina mínimo de \(A\).
Atención: el mínimo no es simplemente un elemento pequeño. Es un elemento del conjunto que es menor o igual que todos los demás elementos del conjunto.
Por ejemplo, si:
\[ A=\{5,8,13,21\}, \]
entonces:
\[ \min A=5. \]
Si en cambio:
\[ B=\{n\in\mathbb{N}\mid n\geq 10\}, \]
entonces:
\[ \min B=10. \]
El principio del buen orden es una propiedad característica de los números naturales. No vale, por ejemplo, para todos los subconjuntos no vacíos de \(\mathbb{Z}\). En efecto, el conjunto:
\[ \mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\} \]
no tiene mínimo.
Equivalencia entre inducción y buen orden
El principio de inducción y el principio del buen orden son equivalentes: asumiendo uno de los dos, se puede demostrar el otro.
Esta equivalencia es importante porque muestra que la inducción no es un mero artificio técnico, sino una consecuencia profunda de la estructura ordenada de los números naturales.
Del buen orden al principio de inducción
Supongamos válido el principio del buen orden. Queremos demostrar el principio de inducción.
Sea \(P(n)\) una propiedad de los números naturales. Supongamos que:
\[ P(1) \text{ es verdadera} \]
y que:
\[ P(n)\Rightarrow P(n+1) \quad \text{para todo } n\geq 1. \]
Debemos demostrar que \(P(n)\) es verdadera para todo \(n\geq 1\).
Razonamos por reducción al absurdo. Supongamos que existe al menos un número natural para el que \(P\) es falsa. Consideremos el conjunto de los contraejemplos:
\[ A=\{n\in\mathbb{N}\mid P(n)\text{ es falsa}\}. \]
Por hipótesis, \(A\neq\varnothing\). Entonces, por el principio del buen orden, \(A\) posee un mínimo. Llamémoslo \(m\).
Como \(P(1)\) es verdadera, el número \(1\) no pertenece a \(A\). Luego \(m\neq 1\), es decir, \(m>1\).
Entonces \(m-1\) es un número natural menor que \(m\). Como \(m\) es el mínimo elemento de \(A\), el número \(m-1\) no puede pertenecer a \(A\).
Por tanto, \(P(m-1)\) es verdadera.
Pero, por el paso inductivo:
\[ P(m-1)\Rightarrow P(m). \]
Se sigue que \(P(m)\) es verdadera.
Esto es imposible, puesto que \(m\in A\) y, por tanto, \(P(m)\) debería ser falsa.
Hemos llegado a una contradicción. Luego el conjunto de los contraejemplos es vacío:
\[ A=\varnothing. \]
Por consiguiente, \(P(n)\) es verdadera para todo \(n\geq 1\). El principio de inducción queda demostrado.
Del principio de inducción al buen orden
Supongamos ahora válido el principio de inducción. Queremos demostrar el principio del buen orden.
Sea \(A\subseteq\mathbb{N}\) un subconjunto no vacío. Debemos demostrar que \(A\) posee un mínimo.
Razonamos por reducción al absurdo. Supongamos que \(A\) no tiene ningún mínimo.
Si \(1\in A\), entonces \(1\) sería automáticamente el mínimo de \(A\), ya que ningún número natural positivo es menor que \(1\). Pero por hipótesis \(A\) no tiene mínimo. Por tanto:
\[ 1\notin A. \]
Consideremos ahora la propiedad:
\[ P(n): \quad 1,2,\dots,n \notin A. \]
Es decir, \(P(n)\) afirma que ninguno de los primeros \(n\) números naturales pertenece a \(A\).
Base de la inducción
Ya hemos observado que:
\[ 1\notin A. \]
Por tanto, \(P(1)\) es verdadera.
Paso inductivo
Supongamos verdadera \(P(n)\), es decir, supongamos que:
\[ 1,2,\dots,n \notin A. \]
Debemos demostrar que:
\[ 1,2,\dots,n,n+1 \notin A. \]
Ya sabemos, por hipótesis de inducción, que \(1,2,\dots,n\) no pertenecen a \(A\). Queda por demostrar que \(n+1\notin A\).
Si fuera:
\[ n+1\in A, \]
entonces \(n+1\) sería el mínimo de \(A\), ya que ninguno de los números naturales anteriores pertenece a \(A\).
Pero esto contradice la hipótesis de que \(A\) no tiene mínimo.
Por tanto:
\[ n+1\notin A. \]
El paso inductivo queda demostrado.
Por el principio de inducción, \(P(n)\) es verdadera para todo \(n\geq 1\). Luego ningún número natural pertenece a \(A\), es decir:
\[ A=\varnothing. \]
Pero esto es imposible, pues habíamos supuesto \(A\neq\varnothing\).
La contradicción muestra que \(A\) debe poseer un mínimo. El principio del buen orden queda demostrado.
Inducción fuerte
Existe una variante del principio de inducción denominada inducción fuerte (también llamada inducción completa).
En la inducción ordinaria, para demostrar \(P(n+1)\), se supone verdadera únicamente \(P(n)\).
En la inducción fuerte, en cambio, para demostrar \(P(n+1)\), se supone que son verdaderas todas las propiedades anteriores:
\[ P(1),P(2),\dots,P(n). \]
El enunciado es el siguiente. Si:
\[ P(1) \text{ es verdadera} \]
y, para todo \(n\geq 1\),
\[ P(1)\land P(2)\land \dots \land P(n) \Rightarrow P(n+1), \]
entonces:
\[ P(n) \text{ es verdadera para todo } n\geq 1. \]
La inducción fuerte no es lógicamente más potente que la inducción ordinaria: ambas formas son equivalentes. Sin embargo, en muchas demostraciones, la inducción fuerte resulta más natural y más sencilla de aplicar.
Ejemplo 1: factorización en números primos
Un ejemplo clásico de aplicación de la inducción fuerte es la demostración de que todo número natural mayor que \(1\) es primo o puede escribirse como producto de números primos.
Sea \(n>1\). Si \(n\) es primo, no hay nada que demostrar.
Si \(n\) no es primo, entonces existen dos enteros \(a\) y \(b\), ambos mayores que \(1\) y menores que \(n\), tales que:
\[ n=ab. \]
Como \(a<n\) y \(b<n\), la hipótesis de la inducción fuerte permite suponer que \(a\) y \(b\) son primos o productos de números primos.
En consecuencia, \(n=ab\) también es producto de números primos.
Este ejemplo muestra por qué, en ciertos contextos, es útil poder emplear no solo el caso inmediatamente anterior, sino todos los casos precedentes.
Ejemplo 2: la sucesión de Fibonacci
La sucesión de Fibonacci se define mediante:
\[ F_1=1,\quad F_2=1,\quad F_n=F_{n-1}+F_{n-2} \quad \text{para todo } n\geq 3. \]
Demostremos por inducción fuerte que, para todo \(n\geq 1\),
\[ F_n<2^n. \]
Casos base
Para \(n=1\):
\[ F_1=1<2=2^1. \]
Para \(n=2\):
\[ F_2=1<4=2^2. \]
Son necesarios dos casos base porque la relación de recurrencia define cada término a partir de los dos términos anteriores.
Paso inductivo
Sea \(n\geq 3\). Supongamos, por hipótesis de inducción fuerte, que la desigualdad vale para todos los índices menores que \(n\). En particular:
\[ F_{n-1}<2^{n-1} \qquad \text{y} \qquad F_{n-2}<2^{n-2}. \]
Entonces:
\[ F_n=F_{n-1}+F_{n-2} < 2^{n-1}+2^{n-2}. \]
Como:
\[ 2^{n-1}+2^{n-2} = 2^{n-2}(2+1) = 3\cdot 2^{n-2}, \]
y puesto que \(3<4\), obtenemos:
\[ 3\cdot 2^{n-2} < 4\cdot 2^{n-2} = 2^2\cdot 2^{n-2} = 2^n. \]
Por tanto:
\[ F_n<2^n. \]
Por el principio de inducción fuerte, \(F_n<2^n\) para todo \(n\geq 1\).
Este ejemplo ilustra bien por qué la inducción fuerte resulta natural: la relación de recurrencia \(F_n=F_{n-1}+F_{n-2}\) involucra los dos términos anteriores, no solo el inmediatamente precedente. Usar directamente la inducción fuerte hace el razonamiento más directo.
Errores frecuentes en las demostraciones por inducción
1. Olvidar el caso base
Sin el caso base, el paso inductivo no es suficiente. Demostrar únicamente:
\[ P(n)\Rightarrow P(n+1) \]
no garantiza que la propiedad sea verdadera para algún número natural.
Es como afirmar que cada ficha hace caer la siguiente, sin hacer caer la primera.
2. Utilizar mal la hipótesis de inducción
La hipótesis de inducción debe usarse exactamente en la forma en que fue asumida.
Si se quiere demostrar una propiedad \(P(n+1)\), hay que partir de \(P(n)\) y transformarla correctamente en el caso siguiente.
3. Demostrar una implicación incompleta
El paso inductivo debe valer para todo valor de \(n\) perteneciente al dominio considerado.
Si el razonamiento funciona solo para algunos valores de \(n\), la demostración no es válida.
La paradoja de los caballos
Un ejemplo célebre de falsa demostración por inducción es la llamada paradoja de los caballos.
Se pretende demostrar la siguiente afirmación:
\[ P(n): \quad \text{en todo conjunto de } n \text{ caballos, todos tienen el mismo color.} \]
Para \(n=1\), la propiedad es verdadera: en un conjunto formado por un solo caballo, todos los caballos tienen ciertamente el mismo color.
Consideremos ahora un conjunto de \(n+1\) caballos:
\[ \{c_1,c_2,\dots,c_n,c_{n+1}\}. \]
Los primeros \(n\) caballos:
\[ \{c_1,c_2,\dots,c_n\} \]
tienen todos el mismo color, por hipótesis de inducción. Los últimos \(n\) caballos:
\[ \{c_2,c_3,\dots,c_{n+1}\} \]
también tienen todos el mismo color, igualmente por hipótesis de inducción.
Como ambos subconjuntos se solapan, parecería seguirse que los \(n+1\) caballos tienen todos el mismo color.
El error está en el paso de \(n=1\) a \(n=2\). En ese caso los dos subconjuntos son:
\[ \{c_1\} \qquad \text{y} \qquad \{c_2\}, \]
y no tienen ningún elemento en común. No existe, por tanto, ningún caballo compartido que permita relacionar el color del primero con el del segundo.
El paso inductivo no es válido para todos los valores de \(n\), sino solo para \(n\geq 2\). La cadena inductiva se rompe, pues, precisamente en el paso de \(P(1)\) a \(P(2)\).
4. Confundir verificación numérica y demostración
Verificar una fórmula para \(n=1\), \(n=2\), \(n=3\) y \(n=4\) puede sugerir que es verdadera, pero no constituye una demostración.
La inducción no consiste en comprobar muchos casos iniciales, sino en demostrar un mecanismo general de paso de \(n\) a \(n+1\).
Inducción y definiciones recursivas
El principio de inducción está estrechamente ligado a las definiciones recursivas.
Muchos objetos matemáticos se definen especificando:
- uno o más valores iniciales;
- una regla que permite construir los términos sucesivos.
Por ejemplo, el factorial se define mediante:
\[ 0!=1 \]
y
\[ (n+1)!=(n+1)n!. \]
La recursión construye los objetos paso a paso, mientras que la inducción permite demostrar propiedades válidas para todos los objetos construidos de este modo.
Recursión e inducción son, por tanto, dos aspectos complementarios de la estructura de los números naturales: la recursión define, la inducción demuestra.
Conclusión
El principio de inducción matemática es mucho más que una técnica para demostrar fórmulas. Expresa una propiedad fundamental de los números naturales: cada número natural se alcanza partiendo del primero y aplicando repetidamente la operación de sucesor.
Su fuerza reside en transformar una afirmación infinita en dos verificaciones finitas:
- una verificación inicial;
- una regla de propagación del caso \(n\) al caso \(n+1\).
Además, la equivalencia con el principio del buen orden muestra que la inducción está profundamente vinculada a la estructura ordenada de \(\mathbb{N}\).
Por este motivo, el principio de inducción ocupa un lugar central en álgebra, teoría de números, lógica, combinatoria, informática teórica y en muchos otros ámbitos de la matemática.
En definitiva, la inducción matemática muestra cómo es posible gobernar lo infinito mediante un razonamiento finito, siempre que la estructura lógica esté construida con precisión.