MenúInducción matemática
La inducción matemática es un método para demostrar afirmaciones que dependen de un número natural $n$: fórmulas de sumas, divisibilidad, desigualdades. Aquí verás de dónde viene el nombre del método, por qué es válido y cómo se aplica.
En esta página: Inducción incompleta · Inducción completa · Principio de inducción matemática · Ejemplos · Inducción desde ${n=m}$ · Conjetura y demostración · Problemas
Inducción incompleta
Un método de investigación en el que observamos algunos elementos de un conjunto y a partir de ellos descubrimos propiedades de todo el conjunto se llama método inductivo. Cuando no se han examinado todos los casos, decimos que se ha aplicado la inducción incompleta.
He aquí un ejemplo de la historia de las matemáticas. El matemático francés del siglo XVII Pierre de Fermat observó los números
${2^{2^1}+1=5}$, ${2^{2^2}+1=17}$, ${2^{2^3}+1=257}$, ${2^{2^4}+1=65\,537}$
y notó que todos son primos. Conjeturó que el número ${2^{2^n}+1}$ es primo para todo $n$ natural. Para ${n=5}$ se obtiene ${2^{2^5}+1=4\,294\,967\,297}$, y Fermat no pudo comprobar si tiene divisores no triviales. Más tarde Euler demostró que es divisible por 641: ${4\,294\,967\,297}={641\cdot 6\,700\,417}$. Por lo tanto, la conjetura de Fermat es falsa.
También hay ejemplos en los que el primer caso que refuta una conjetura obtenida por inducción incompleta está tan lejos que no se puede alcanzar con comprobaciones. Por ejemplo, parece que el número ${991n^2+1}$ nunca es un cuadrado perfecto. Esto es cierto para todo $n$ natural menor que
${n}={12\,055\,735\,790\,331}\allowbreak{\,359\,447\,442\,538\,767}$,
pero para este número de 29 cifras ${991n^2+1}$ sí es un cuadrado perfecto. Tantas comprobaciones están fuera del alcance incluso de las computadoras más rápidas.
Estos ejemplos muestran que una conclusión basada en la inducción incompleta puede ser falsa, así que la inducción incompleta debe usarse con cuidado. Es útil porque los casos particulares sugieren una regularidad y ayudan a formular una conjetura. Sin embargo, la veracidad de la conjetura debe demostrarse de otra manera.
Inducción completa
Si los casos particulares son finitos y se han examinado todos, la conclusión está justificada. Por ejemplo, para saber cuántos números primos hay entre los números del 1 al 10, basta con comprobar cada uno de ellos: son primos 2, 3, 5 y 7. La conclusión «entre los diez primeros números hay 4 primos» no necesita otra justificación.
Un método en el que examinamos todos los elementos de un conjunto y sacamos una conclusión sobre todo el conjunto se llama inducción completa (o demostración por agotamiento de casos). Una conclusión obtenida por inducción completa es totalmente fiable, por lo que es un método de demostración rigurosa.
Sin embargo, la inducción completa se usa poco: es engorrosa cuando hay muchos casos e inaplicable cuando hay infinitos. Un conjunto infinito solo puede examinarse con ella si se divide en un número finito de partes y cada una se examina por separado.
Ejemplo. Demuestra que el cuadrado de un número natural no puede terminar en 2.
La última cifra del cuadrado depende solo de la última cifra del número. Por eso dividimos los números naturales en 10 partes según su última cifra y comprobamos cada parte:
| $n$ termina en | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $n^2$ termina en | 0 | 1 | 4 | 9 | 6 |
| $n$ termina en | 5 | 6 | 7 | 8 | 9 |
| $n^2$ termina en | 5 | 6 | 9 | 4 | 1 |
En las filas de $n^2$ no aparece la cifra 2, y el problema está resuelto.
Principio de inducción matemática
Cuando el conjunto de casos es infinito y no se puede dividir en un número finito de partes, se usan otros métodos. Uno de ellos es el método de inducción matemática. Se basa en uno de los axiomas de los números naturales formulados por el matemático italiano Giuseppe Peano (1889). Por eso, a pesar de su nombre, la inducción matemática es un método deductivo.
Axioma de inducción. Si un conjunto $M$ de números naturales contiene el número 1 y, junto con cada número $k$, contiene también el número siguiente ${k+1}$, entonces $M$ contiene todos los números naturales.
En las demostraciones se usa en la siguiente forma.
Principio de inducción matemática. Sea $T(n)$ una afirmación sobre el número natural $n$. Si $T(1)$ es verdadera y, para todo $k$ natural, la veracidad de $T(k)$ implica la veracidad de ${T(k+1)}$, entonces $T(n)$ es verdadera para todo $n$ natural.
En efecto, sea $M$ el conjunto de los números naturales para los que $T(n)$ es verdadera. Por hipótesis ${1\in M}$, y si ${k\in M}$, entonces ${k+1\in M}$. Por el axioma de inducción $M$ contiene todos los números naturales, es decir, $T(n)$ es verdadera para todo $n$ natural.
Por eso una demostración por inducción tiene tres etapas:
- Caso base: comprobamos que la afirmación es verdadera para ${n=1}$.
- Paso inductivo: suponemos que es verdadera para algún ${n=k}$ (la hipótesis de inducción) y demostramos que también es verdadera para ${n=k+1}$.
- Conclusión: por el principio de inducción matemática la afirmación es verdadera para todo $n$ natural. Es verdadera para ${n=1}$, por lo tanto también para ${n=2}$, luego también para ${n=3}$, y así sucesivamente.
Se necesitan tanto el caso base como el paso. Sea $T(n)$ la afirmación «el número ${n^2+n}$ es impar». El paso es verdadero: si ${k^2+k}$ es impar, entonces ${(k+1)^2+(k+1)}={(k^2+k)+2(k+1)}$ también es impar. Sin embargo, el caso base es falso (${1^2+1=2}$), y de hecho ${n^2+n=n(n+1)}$ es par para todo $n$.
Ejemplos
Ejemplo 1. Demuestra que
${S_n}={1\cdot 2\cdot 3+2\cdot 3\cdot 4+\dots}+{n(n+1)(n+2)}={\frac{n(n+1)(n+2)(n+3)}{4}}$.
Caso base. Para ${n=1}$ el lado izquierdo es ${S_1=1\cdot 2\cdot 3=6}$, y el lado derecho es ${\frac{1\cdot 2\cdot 3\cdot 4}{4}=6}$.
Paso. Supongamos que la fórmula es verdadera para ${n=k}$, es decir, ${S_k}={\frac{k(k+1)(k+2)(k+3)}{4}}$. Entonces
${S_{k+1}}={S_k}+{(k+1)(k+2)(k+3)}={\frac{k(k+1)(k+2)(k+3)}{4}}+{(k+1)(k+2)(k+3)}={\frac{(k+1)(k+2)(k+3)(k+4)}{4}}$,
porque ${\frac{k}{4}+1=\frac{k+4}{4}}$. Esta es la fórmula para ${n=k+1}$.
Conclusión. La fórmula es verdadera para ${n=1}$, y su veracidad para ${n=k}$ implica su veracidad para ${n=k+1}$. Por el principio de inducción matemática es verdadera para todo $n$ natural.
Ejemplo 2. Demuestra que para todo $n$ natural el número ${11^{n+2}+12^{2n+1}}$ es divisible por 133.
Caso base. Para ${n=1}$: ${11^3+12^3}={1331+1728}={3059}={133\cdot 23}$.
Paso. Sea ${11^{k+2}+12^{2k+1}=133p}$, donde $p$ es un número entero. Como ${144=11+133}$,
${11^{k+3}+12^{2k+3}}={11\cdot 11^{k+2}}+{144\cdot 12^{2k+1}}={11\left(11^{k+2}+12^{2k+1}\right)}+{133\cdot 12^{2k+1}}={133\left(11p+12^{2k+1}\right)}$.
Conclusión. La expresión es divisible por 133 para ${n=1}$, y si es divisible para ${n=k}$, también lo es para ${n=k+1}$. Por lo tanto, es divisible por 133 para todo $n$ natural.
Ejemplo 3. Demuestra que el conjunto ${M_n=\{a_1,a_2,\dots,a_n\}}$ tiene $2^n$ subconjuntos.
Caso base. Para ${n=1}$ el conjunto ${M_1=\{a_1\}}$ tiene dos subconjuntos: el conjunto vacío y el propio $M_1$. Su número es ${2^1}$.
Paso. Supongamos que ${M_k=\{a_1,\dots,a_k\}}$ tiene $2^k$ subconjuntos, y consideremos ${M_{k+1}}={\{a_1,\dots,a_k,a_{k+1}\}}$. Los subconjuntos de $M_{k+1}$ que no contienen $a_{k+1}$ son exactamente los subconjuntos de $M_k$, es decir, hay $2^k$. Los subconjuntos que contienen $a_{k+1}$ se obtienen añadiendo $a_{k+1}$ a cada subconjunto de $M_k$, así que también hay $2^k$. En total ${2^k+2^k=2\cdot 2^k=2^{k+1}}$.
Conclusión. Por el principio de inducción matemática $M_n$ tiene $2^n$ subconjuntos para todo $n$ natural.
Inducción a partir de ${n=m}$
En las aplicaciones también se usa a menudo la siguiente formulación del principio.
Sea $m$ un número natural. Si la afirmación $T(m)$ es verdadera y, para todo ${k\ge m}$, la veracidad de $T(k)$ implica la veracidad de ${T(k+1)}$, entonces $T(n)$ es verdadera para todo $n$ natural con ${n\ge m}$.
Aquí el caso base es la comprobación de la afirmación para ${n=m}$.
Ejemplo 4. Demuestra que ${2^n\gt 2n+1}$ para todo $n$ natural con ${n\ge 3}$.
Caso base. Para ${n=3}$: ${2^3=8\gt 7=2\cdot 3+1}$. (Para ${n=2}$ la desigualdad es falsa: ${2^2=4\lt 5}$.)
Paso. Sea ${2^k\gt 2k+1}$ para algún ${k\ge 3}$. Demostraremos que ${2^{k+1}\gt 2(k+1)+1}$. Además de la hipótesis de inducción usamos también ${2^k\gt 2}$:
${2^{k+1}}={2^k+2^k}\gt{(2k+1)+2}={2(k+1)+1}$.
Conclusión. Por el principio de inducción matemática (la última formulación) ${2^n\gt 2n+1}$ para todo $n$ natural con ${n\ge 3}$.
Conjetura y demostración
En la investigación a menudo primero hay que descubrir la regularidad, formular una afirmación sobre ella y solo después demostrarla para todo $n$ natural. En ese caso aplicamos sucesivamente la inducción incompleta, para obtener una conjetura a partir de casos particulares, y la inducción matemática, para demostrarla. Las etapas son tres:
- experimentación y observación;
- formulación de una conjetura;
- demostración de la conjetura.
Ejemplo 5. Halla la suma de los $n$ primeros números impares.
El problema pide una fórmula para la suma ${S_n}={1+3+5+\dots}+{(2n-1)}$ más corta que la suma directa.
Primera etapa. Calculamos $S_n$ para varios valores consecutivos de $n$: ${S_1=1}$, ${S_2=1+3=4}$, ${S_3=1+3+5=9}$, ${S_4=1+3+5+7=16}$, etc.:
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| $S_n$ | 1 | 4 | 9 | 16 | 25 | 36 |
Buscamos una regla que dé cada número de la segunda fila a partir del número que tiene encima. Observamos que ${S_1=1^2}$, ${S_2=2^2}$, ${S_3=3^2}$, ${S_4=4^2}$, ${S_5=5^2}$ y ${S_6=6^2}$.
Segunda etapa. La regla se cumple para ${n=1,2,\dots,6}$, y es natural conjeturar que se cumple para todo $n$:
${1+3+5+\dots}+{(2n-1)}={n^2}$.
Encontrar una conjetura así depende de nuestra capacidad de observar, de hacer suposiciones y comprobarlas, de la experiencia con problemas parecidos y de las analogías con problemas ya conocidos.
Tercera etapa. Demostramos la conjetura por inducción matemática. Para ${n=1}$ es verdadera: ${S_1=1=1^2}$. Sea ${S_k=k^2}$. Entonces
${S_{k+1}}={S_k+(2k+1)}={k^2+2k+1}={(k+1)^2}$.
Por el principio de inducción matemática ${S_n=n^2}$ para todo $n$ natural, es decir, la conjetura es verdadera.
Aquí dividimos a propósito la solución en tres etapas para que se vea claramente su camino. En la práctica las etapas se funden de forma natural unas con otras.
Problemas
En los problemas 1–6 demuestra que la afirmación es verdadera para todo $n$ natural.
1. ${\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}+\dots}+{\frac{1}{(2n-1)(2n+1)}}={\frac{n}{2n+1}}$
Caso base: ${\frac{1}{1\cdot 3}=\frac{1}{3}=\frac{1}{2\cdot 1+1}}$.
Paso: ${\frac{k}{2k+1}}+{\frac{1}{(2k+1)(2k+3)}}={\frac{2k^2+3k+1}{(2k+1)(2k+3)}}={\frac{(2k+1)(k+1)}{(2k+1)(2k+3)}}={\frac{k+1}{2k+3}}$.
2. ${\frac{1}{1\cdot 4}+\frac{1}{4\cdot 7}+\frac{1}{7\cdot 10}}+{\dots+\frac{1}{(3n-2)(3n+1)}}={\frac{n}{3n+1}}$
Caso base: ${\frac{1}{1\cdot 4}=\frac{1}{4}=\frac{1}{3\cdot 1+1}}$.
Paso: ${\frac{k}{3k+1}}+{\frac{1}{(3k+1)(3k+4)}}={\frac{3k^2+4k+1}{(3k+1)(3k+4)}}={\frac{(3k+1)(k+1)}{(3k+1)(3k+4)}}={\frac{k+1}{3k+4}}$.
3. ${\frac{1}{a(a+1)}}+{\frac{1}{(a+1)(a+2)}}+{\dots+\frac{1}{(a+n-1)(a+n)}}={\frac{n}{a(a+n)}}$, donde ${a\gt 0}$
Caso base: para ${n=1}$ ambos lados son iguales a ${\frac{1}{a(a+1)}}$.
Paso: ${\frac{k}{a(a+k)}}+{\frac{1}{(a+k)(a+k+1)}}={\frac{k(a+k+1)+a}{a(a+k)(a+k+1)}}={\frac{(a+k)(k+1)}{a(a+k)(a+k+1)}}={\frac{k+1}{a(a+k+1)}}$, porque ${ka+k^2+k+a}={(a+k)(k+1)}$.
4. ${2^{3n}-7n-1}$ es divisible por 49
${2^{3n}=8^n}$. Caso base: ${8-7-1=0}$ es divisible por 49.
Paso: ${8^{k+1}-7(k+1)-1}={8\left(8^k-7k-1\right)+49k}$. Ambos sumandos son divisibles por 49.
5. ${2^{2n}+15n-1}$ es divisible por 9
${2^{2n}=4^n}$. Caso base: ${4+15-1=18=9\cdot 2}$.
Paso: ${4^{k+1}+15(k+1)-1}={4\left(4^k+15k-1\right)}-{9(5k-2)}$. Ambos términos son divisibles por 9.
6. ${2^{n+2}\cdot 3^n+5n-4}$ es divisible por 25
Sea ${A_n=2^{n+2}\cdot 3^n+5n-4}$. Caso base: ${A_1=8\cdot 3+5-4=25}$.
Paso: ${A_{k+1}}={6\cdot 2^{k+2}\cdot 3^k+5k+1}={6A_k-25(k-1)}$, y $6A_k$ y ${25(k-1)}$ son divisibles por 25.
En los problemas 7–10 halla la suma. Calcúlala para varios valores de $n$, formula una conjetura y demuéstrala por inducción.
7. ${1+2+3+\dots+n}$
${\frac{n(n+1)}{2}}$. Paso: ${\frac{k(k+1)}{2}+(k+1)}={\frac{(k+1)(k+2)}{2}}$.
8. ${2+4+6+\dots+2n}$
${n(n+1)}$. Paso: ${k(k+1)+2(k+1)}={(k+1)(k+2)}$.
9. ${1\cdot 2+2\cdot 3+3\cdot 4}+{\dots+n(n+1)}$
${\frac{n(n+1)(n+2)}{3}}$. Paso: ${\frac{k(k+1)(k+2)}{3}}+{(k+1)(k+2)}={\frac{(k+1)(k+2)(k+3)}{3}}$.
10. ${\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}}+{\dots+\frac{1}{n(n+1)}}$
Las sumas son ${\frac{1}{2}}$, ${\frac{2}{3}}$, ${\frac{3}{4}}$, …, así que la conjetura es ${\frac{n}{n+1}}$. Paso: ${\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}}={\frac{k^2+2k+1}{(k+1)(k+2)}}={\frac{k+1}{k+2}}$.
Ver también: Progresión aritmética · Progresión geométrica · Divisibilidad
