La inducción fuerte permite suponer que una propiedad vale para todos los casos anteriores antes de demostrar el siguiente. Es ideal cuando una estructura o algoritmo se construye a partir de subproblemas de tamaños diversos.
En la inducción matemática simple, para demostrar P(k + 1) suponemos solamente P(k). A veces esa información no alcanza: el caso siguiente puede depender de P(k - 1), P(k - 2) o de cualquier caso anterior.
La inducción fuerte, también llamada inducción completa, resuelve esta situación. En el paso inductivo podemos suponer que P(n0), P(n0 + 1), ..., P(k) son verdaderas y usar cualquiera de ellas para demostrar P(k + 1).
Sea P(n) una proposición definida para todos los naturales n ≥ n0. Una demostración por inducción fuerte contiene estas partes:
| Característica | Inducción simple | Inducción fuerte |
|---|---|---|
| Hipótesis inductiva | Se supone P(k). | Se suponen P(n0) hasta P(k). |
| Uso típico | El siguiente caso depende del anterior. | El siguiente caso depende de cualquier caso menor. |
| Ejemplo | Suma de los primeros n enteros. | Factorización prima de un entero. |
| Poder lógico | Equivalente. | Equivalente. |
La inducción fuerte no es «más poderosa» en sentido lógico: puede derivarse de la inducción simple y viceversa. Su ventaja es práctica: expresa de manera natural las dependencias de muchos problemas.
La hipótesis debe incluir todos los casos anteriores dentro del rango. No basta con afirmar vagamente que «los anteriores son verdaderos». Es necesario indicar qué valores cubre y qué propiedad cumple cada uno.
Esta formulación permite usar la propiedad para cualquier factor propio de k + 1, no solo para k.
Demostraremos que todo entero n ≥ 2 puede escribirse como producto de números primos.
Caso base: n = 2. Como 2 es primo, ya es un producto de un único primo.
Hipótesis inductiva fuerte: supongamos que cada entero m con 2 ≤ m ≤ k puede escribirse como producto de primos.
Paso inductivo: consideremos k + 1. Hay dos posibilidades:
El argumento necesita la hipótesis para a y b, que no tienen por qué ser iguales a k. Por eso la inducción fuerte es la forma natural de esta demostración.
El siguiente algoritmo obtiene factores primos de un entero positivo. Muestra cómo un número compuesto se descompone en factores menores.
function factoresPrimos(n) {
const factores = [];
let divisor = 2;
while (n > 1) {
while (n % divisor === 0) {
factores.push(divisor);
n /= divisor;
}
divisor++;
}
return factores;
}
console.log(factoresPrimos(84)); // [2, 2, 3, 7]
console.log(factoresPrimos(97)); // [97]La demostración anterior garantiza que existe una factorización. Este algoritmo produce una de ellas para cualquier entero válido mayor o igual que 2.
Supongamos que tenemos monedas de 4 y 5 unidades. Demostraremos que toda cantidad n ≥ 12 puede formarse con estas monedas.
Casos base: 12 = 4 + 4 + 4; 13 = 4 + 4 + 5; 14 = 4 + 5 + 5; 15 = 5 + 5 + 5.
Hipótesis inductiva fuerte: supongamos que todas las cantidades entre 12 y k pueden formarse, donde k ≥ 15.
La prueba usa un caso anterior que no es k, sino k - 3. Esa es otra señal de que la inducción fuerte es adecuada.
function sePuedeFormarCon4y5(cantidad) {
for (let monedasDe4 = 0; monedasDe4 * 4 <= cantidad; monedasDe4++) {
const resto = cantidad - monedasDe4 * 4;
if (resto % 5 === 0) return true;
}
return false;
}
console.log(sePuedeFormarCon4y5(12)); // true
console.log(sePuedeFormarCon4y5(13)); // true
console.log(sePuedeFormarCon4y5(11)); // falseEl algoritmo prueba una cantidad concreta mediante búsqueda. La inducción fuerte demuestra la garantía general a partir de 12.
Una recurrencia define un término a partir de valores anteriores. La sucesión de Fibonacci es el ejemplo más conocido:
Para demostrar una propiedad de F(n), el paso inductivo suele necesitar las propiedades de F(k) y F(k - 1). Podemos usar inducción fuerte o inducción simple con dos hipótesis y dos casos base.
Demostraremos que F(n) < 2n para todo n ≥ 1.
Casos base: F(1) = 1 < 2 y F(2) = 1 < 4.
Hipótesis inductiva fuerte: supongamos que F(j) < 2j para todo j entre 1 y k, con k ≥ 2.
function fibonacci(n) {
if (n < 0 || !Number.isInteger(n)) {
throw new Error("n debe ser un entero no negativo");
}
let anterior = 0;
let actual = 1;
for (let i = 0; i < n; i++) {
[anterior, actual] = [actual, anterior + actual];
}
return anterior;
}
console.log(fibonacci(10)); // 55
console.log(fibonacci(10) < 2 ** 10); // trueUn algoritmo recursivo suele resolver un problema reduciéndolo a uno o varios subproblemas más pequeños. Para demostrar que funciona con una entrada de tamaño n, necesitamos saber que funciona con todos los tamaños menores que n que pueda invocar.
Por ejemplo, merge sort divide un arreglo en dos partes cuyos tamaños pueden no ser exactamente n - 1. La corrección de sus llamadas recursivas se expresa naturalmente suponiendo correctos todos los casos de tamaño menor que n.
Una búsqueda binaria recursiva recibe un segmento ordenado. Si el valor central no coincide, llama a sí misma sobre un segmento estrictamente menor. Para demostrar corrección para un segmento de longitud n, la hipótesis fuerte garantiza que las llamadas sobre cualquier longitud menor funcionan correctamente.
function busquedaBinariaRecursiva(numeros, buscado, inicio = 0, fin = numeros.length - 1) {
if (inicio > fin) return -1;
const centro = Math.floor((inicio + fin) / 2);
if (numeros[centro] === buscado) return centro;
if (buscado < numeros[centro]) {
return busquedaBinariaRecursiva(numeros, buscado, inicio, centro - 1);
}
return busquedaBinariaRecursiva(numeros, buscado, centro + 1, fin);
}
console.log(busquedaBinariaRecursiva([2, 5, 9, 14, 20], 14)); // 3
console.log(busquedaBinariaRecursiva([2, 5, 9, 14, 20], 7)); // -1La cantidad de casos base debe ser suficiente para que el paso inductivo pueda comenzar y continuar. Para Fibonacci necesitamos al menos los casos iniciales que aparecen en la recurrencia. Para el problema de monedas usamos cuatro casos base porque el paso agrega 4 unidades y debe cubrir todos los residuos relevantes.
Omitir un caso base crea una brecha lógica: puede haber valores que nunca queden conectados con la regla inductiva.
El principio del buen orden afirma que todo subconjunto no vacío de los números naturales tiene un elemento mínimo. Es equivalente a la inducción matemática y ofrece otra manera de demostrar propiedades universales.
Una prueba típica por buen orden supone que hay contraejemplos y toma el menor. Como los casos menores cumplen la propiedad, se obtiene una contradicción. En el próximo tema estudiaremos este principio en detalle.
La inducción fuerte permite propagar una propiedad a través de los números naturales incluso cuando el siguiente caso depende de varias instancias anteriores. Por eso aparece en teoría de números, recurrencias, algoritmos recursivos y análisis de estructuras.
En el próximo tema veremos el principio del buen orden, una herramienta equivalente que basa las demostraciones en la existencia de un contraejemplo mínimo.