Inducción matemática — principio, pasos y ejemplos

La inducción matemática es un método de demostración para mostrar que una afirmación es verdadera para todo entero a partir de cierto valor inicial. Para demostrar una afirmación para todos los $n \ge n_0$, muestras que el primer caso es verdadero y luego que la verdad en un entero obliga a la verdad en el siguiente.

Si ambas partes son correctas, la afirmación vale para todos los enteros del rango indicado. Esa es toda la idea.

Cómo funciona la inducción matemática

Escribe la afirmación como $P(n)$. Entonces la inducción tiene esta estructura:

1. Demuestra el caso base: muestra que $P(n_0)$ es verdadera.
2. Demuestra el paso inductivo: muestra que si $P(k)$ es verdadera para un entero arbitrario $k \ge n_0$, entonces $P(k+1)$ también es verdadera.

Una vez hecho eso, puedes concluir que $P(n)$ es verdadera para todo entero $n \ge n_0$.

La lógica es secuencial. El caso base inicia la cadena, y el paso inductivo hace que la cadena avance de un entero al siguiente.

Por qué importan tanto el caso base como el paso inductivo

El caso base te da la primera afirmación verdadera. El paso inductivo dice que la verdad pasa de un entero al siguiente.

Así que si $P(n_0)$ es verdadera, entonces $P(n_0 + 1)$ es verdadera. Luego $P(n_0 + 2)$ es verdadera, y así sucesivamente. La inducción no se salta el punto de partida, ni tampoco el enlace entre un caso y el siguiente.

Ejemplo resuelto: demostrar una fórmula de suma por inducción

Un ejemplo estándar es la fórmula

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

para todos los enteros $n \ge 1$.

Sea

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Caso base

Toma $n = 1$. El lado izquierdo es $1$, y el lado derecho es

$$\frac{1(1+1)}{2} = 1$$

Así que $P(1)$ es verdadera.

Paso inductivo

Supón que $P(k)$ es verdadera para algún entero arbitrario $k \ge 1$. Eso significa que

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Ahora demuestra $P(k+1)$. Empieza con el lado izquierdo para $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Usando la hipótesis de inducción,

$$\frac{k(k+1)}{2} + (k+1)$$

Saca factor común $(k+1)$:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Luego simplifica:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Esa es exactamente la fórmula con $n = k+1$. Así que $P(k+1)$ es verdadera.

Como el caso base y el paso inductivo están ambos demostrados, la fórmula vale para todos los enteros $n \ge 1$.

Cuándo usar la inducción matemática

La inducción es útil cuando una afirmación depende de un parámetro entero y cada caso se conecta de forma natural con uno anterior. Esto ocurre a menudo con sumas, afirmaciones de divisibilidad, desigualdades, relaciones de recurrencia y demostraciones de algoritmos.

Primero, identifica el valor inicial correcto. Algunas afirmaciones empiezan en $n = 0$, otras en $n = 1$, y otras solo tienen sentido para enteros mayores.

Luego comprueba cuál es el siguiente caso válido. El paso habitual es de $k$ a $k+1$, pero si la afirmación solo trata sobre enteros pares, un paso de $k$ a $k+2$ puede ser la versión correcta.

Errores comunes en las demostraciones por inducción

Demostrar solo el caso base

El caso base comprueba únicamente el primer valor. Por sí solo, no demuestra la afirmación para los enteros posteriores.

Usar un valor inicial incorrecto

Si la afirmación está pensada para todos los $n \ge 2$, demostrar solo $P(1)$ no ayuda. El caso base debe coincidir con el rango real de la afirmación.

Tratar la hipótesis de inducción con descuido

En el paso inductivo, supones $P(k)$ para un entero arbitrario $k$ dentro del rango válido. No supones que todo el teorema ya está demostrado.

Demostrar el caso siguiente equivocado

Si tu teorema necesita un paso $k \to k+1$, demostrar un paso distinto no completa el argumento a menos que expliques por qué ese paso diferente es suficiente.

Una extensión útil: inducción fuerte

A veces, demostrar $P(k+1)$ requiere más que solo $P(k)$. En esa situación, la inducción fuerte te permite suponer todos los casos anteriores hasta $k$ y luego demostrar el siguiente.

La idea está muy relacionada, pero la suposición es más fuerte. Es útil, por ejemplo, cuando una demostración depende de dividir un número en partes más pequeñas.

Prueba tu propia versión

Toma la afirmación

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

y demuéstrala para todos los enteros $n \ge 1$ usando la misma estructura: primero el caso base y luego el paso de $k$ a $k+1$. Si puedes escribir esa demostración con claridad, el método suele encajar.