La inducción matemática permite demostrar que una propiedad vale para todos los números naturales. Es el modelo lógico que conecta una base inicial con un paso que se puede repetir indefinidamente.
Muchas afirmaciones de matemática discreta dependen de un número natural n: fórmulas de sumas, propiedades de secuencias, tamaño de estructuras y cantidad de operaciones de un algoritmo. Como hay infinitos valores de n, comprobar algunos no alcanza.
La inducción matemática demuestra una afirmación P(n) para todos los valores de n a partir de un inicio determinado. La idea es establecer el primer caso y probar que cada caso correcto obliga al siguiente a ser correcto.
Imaginemos una fila infinita de fichas de dominó numeradas. Si derribamos la primera ficha y demostramos que cada ficha derriba a la siguiente, entonces todas caerán.
La analogía tiene un límite importante: no prueba que una propiedad sea cierta por repetición mecánica, sino que representa una regla lógica sobre los números naturales. El caso base y el paso inductivo deben demostrarse por separado.
Sea P(n) una proposición que depende de un número natural n. Para demostrar P(n) para todo n ≥ n0, necesitamos dos partes.
La proposición P(k) que se supone temporalmente verdadera se llama hipótesis inductiva. No podemos usar P(k + 1) como si ya fuera cierta: justamente eso es lo que debemos demostrar.
La parte más importante de una demostración por inducción es expresar con precisión P(n). Debe incluir el dominio, el punto de inicio y la igualdad o propiedad que se desea demostrar.
Una proposición demasiado débil puede no permitir completar el paso inductivo. Una proposición demasiado amplia puede ser falsa. Escribirla antes de comenzar evita errores.
Demostraremos que para todo n ≥ 1 se cumple:
Caso base, n = 1: el lado izquierdo vale 1 y el derecho vale 1(1 + 1)/2 = 1. Por lo tanto P(1) es verdadera.
Hipótesis inductiva: supongamos que para un k ≥ 1 se cumple 1 + 2 + ... + k = k(k + 1)/2.
Paso inductivo: debemos demostrar P(k + 1).
El código calcula la suma iterativamente y la compara con la fórmula. La comparación funciona para los valores probados; la demostración inductiva garantiza la fórmula para todos los naturales positivos.
function sumarHasta(n) {
let suma = 0;
for (let i = 1; i <= n; i++) {
suma += i;
}
return suma;
}
function formulaSuma(n) {
return n * (n + 1) / 2;
}
console.log(sumarHasta(10)); // 55
console.log(formulaSuma(10)); // 55Demostraremos que la suma de los primeros n números impares es n²:
Caso base: para n = 1, el lado izquierdo es 1 y 1² = 1.
Hipótesis inductiva: supongamos que 1 + 3 + ... + (2k - 1) = k².
Paso inductivo: al agregar el siguiente impar, obtenemos:
Demostraremos que 7 divide a 8n - 1 para todo n ≥ 1.
Caso base: 8¹ - 1 = 7, que es divisible por 7.
Hipótesis inductiva: supongamos que 8k - 1 = 7m para algún entero m.
function esDivisiblePorSiete(n) {
return (8 ** n - 1) % 7 === 0;
}
console.log(esDivisiblePorSiete(1)); // true
console.log(esDivisiblePorSiete(5)); // true
console.log(esDivisiblePorSiete(10)); // truePara valores grandes no siempre conviene calcular potencias completas: en temas posteriores usaremos aritmética modular para trabajar con restos de manera más eficiente.
Demostraremos que 2n ≥ n + 1 para todo n ≥ 0.
Caso base: para n = 0, 2⁰ = 1 y 0 + 1 = 1.
Hipótesis inductiva: supongamos 2k ≥ k + 1.
El último paso usa que k ≥ 0. En una prueba de desigualdades siempre debemos indicar qué condición hace válida cada comparación.
La estructura de un bucle se parece a una demostración inductiva. Antes de la primera iteración debe valer un invariante; si vale antes de una iteración, el cuerpo del bucle debe preservarlo; al terminar, el invariante y la condición de salida permiten obtener la postcondición.
| Inducción | Bucle |
|---|---|
| Caso base | Inicialización antes del ciclo |
| Hipótesis inductiva P(k) | Invariante antes de una iteración |
| Paso P(k) → P(k + 1) | El cuerpo preserva el invariante |
| Conclusión para todo n | Corrección al finalizar el ciclo |
En la función sumarHasta, el invariante es: antes de cada iteración con índice i, suma contiene 1 + 2 + ... + (i - 1). Al agregar i, pasa a contener la suma hasta i.
Esta es una demostración por inducción disfrazada de análisis de programa. La variable i avanza de un natural al siguiente exactamente como el índice n en la prueba matemática.
La inducción es especialmente natural para funciones recursivas. Una función recursiva tiene un caso base y un caso que reduce el problema a una entrada más pequeña; la prueba de corrección suele seguir la misma forma.
function factorial(n) {
if (!Number.isInteger(n) || n < 0) {
throw new Error("n debe ser un entero no negativo");
}
if (n === 0) return 1;
return n * factorial(n - 1);
}
console.log(factorial(0)); // 1
console.log(factorial(5)); // 120Para demostrar que factorial(n) calcula n!, se prueba el caso base n = 0 y se supone que la llamada con n - 1 calcula (n - 1)!. Entonces la llamada con n devuelve n · (n - 1)! = n!.
No todas las propiedades comienzan en 0 o en 1. Podemos iniciar la inducción en cualquier n0 si la afirmación solo tiene sentido desde allí.
El punto de inicio debe quedar explícito. Si omitimos casos iniciales para los que la proposición es falsa, la demostración no es válida.
A veces el paso inductivo avanza más de una unidad, por ejemplo de P(k) a P(k + 2). En ese caso se necesitan suficientes casos base para cubrir todas las cadenas de valores.
Este tipo de situación aparece en sucesiones definidas con dos términos previos, como Fibonacci, y en algoritmos que reducen el tamaño de entrada de a dos unidades.
En la inducción simple, el paso inductivo supone únicamente P(k). En la inducción fuerte se puede suponer que valen P(n0), P(n0 + 1), ..., P(k). Ambas se apoyan en el mismo principio de los números naturales.
La inducción fuerte es útil cuando el caso k + 1 depende de varios casos anteriores o de un caso menor que k. La estudiaremos con detalle en el próximo tema.
La inducción matemática permite convertir una afirmación infinita en dos pruebas finitas: un inicio y una regla de propagación. Por eso es una herramienta central para las sucesiones, los algoritmos iterativos y las funciones recursivas.
En el próximo tema ampliaremos el método con la inducción fuerte, que permite usar todos los casos anteriores para demostrar el siguiente.