La inducción

Definición

La inducción demuestra que una propiedad $P(n)$P(n) vale para todo entero a partir de un rango $n_0$n0​, mediante dos comprobaciones solamente:

Estos dos puntos establecen infinitos enunciados. Ahí reside su fuerza: nunca se comprueba más que un caso y una implicación.

Una imagen, y su límite

Una fila de fichas de dominó: derribar la primera, y garantizar que cada una tumbe a la siguiente, basta para que caigan todas.

La imagen acierta en el mecanismo y yerra en el alcance. Una fila de fichas es finita y la caída lleva tiempo; la inducción versa sobre infinitos rangos y no se despliega. No narra una propagación, prueba una propiedad.

Un ejemplo llevado hasta el final

Mostremos que la suma de los $n$n primeros enteros vale $\dfrac{n(n+1)}{2}$2n(n+1)​.

Caso base. Para $n = 1$n=1: la suma vale 1, y $\dfrac{1 \times 2}{2} = 1$21×2​=1.

Paso inductivo. Supongamos la fórmula verdadera en el rango $n$n. Entonces:

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

Es la fórmula en el rango $n+1$n+1. Ambas etapas se cumplen, luego la propiedad vale para todo $n \geq 1$n≥1.

Ambas etapas son necesarias

El paso inductivo solo no prueba nada. Tomemos $P(n)$P(n): «$n = n + 1$n=n+1».

Esta propiedad es hereditaria: si $n = n+1$n=n+1, sumando 1 a ambos lados resulta $n + 1 = n + 2$n+1=n+2. El paso se propaga perfectamente — y la propiedad es falsa para todo entero, porque ningún rango la inicia.

El caso base solo no basta tampoco: una propiedad puede ser verdadera en 1 y falsa después.

Inducción fuerte

Algunas demostraciones reclaman más que el rango anterior. La inducción fuerte supone $P(k)$P(k) para todos los $k \leq n$k≤n, y no solo para $n$n.

Sirve cuando el paso apela a un rango muy anterior — descomponer un entero en factores primos, por ejemplo, remite a dos factores cualesquiera menores, no al predecesor.

Resumen

Un punto de partida y un paso que se propaga demuestran infinitos casos; ninguno de los dos es prescindible.