Inducción fuerte y sus aplicaciones en álgebra olímpica

Inducción débil vs. inducción fuerte

La inducción matemática débil (o simple) establece: si $P(1)$ es verdadera y $P(n) \Rightarrow P(n+1)$ para todo $n \ge 1$, entonces $P(n)$ es verdadera para todo $n \ge 1$. En la hipótesis de inducción solo se asume $P(n)$ para el valor inmediatamente anterior.

La inducción fuerte (o completa) establece: si $P(1)$ es verdadera y, para todo $n \ge 1$, la verdad de $P(1), P(2), \ldots, P(n)$ implica $P(n+1)$, entonces $P(n)$ es verdadera para todo $n \ge 1$. En la hipótesis se asume $P(k)$ para todos los $k \le n$.

Ambas formas son lógicamente equivalentes (se pueden deducir mutuamente), pero la inducción fuerte es más cómoda cuando el paso inductivo necesita información de varios pasos anteriores, no solo del inmediato. Esto ocurre, por ejemplo, cuando $a_n$ se define a partir de $a_{n-1}$ y $a_{n-2}$ (recurrencias de orden 2), o cuando se descompone $n$ en partes más pequeñas que no son necesariamente $n-1$.

Regla práctica: usa inducción fuerte cuando la demostración del caso $n+1$ no puede completarse solo con el caso $n$, o cuando el enunciado involucra una partición arbitraria de $n$.

Inducción sobre el grado en problemas de polinomios

Un contexto clásico para la inducción fuerte es la demostración de propiedades de polinomios por inducción sobre el grado. Sea $P(x)$ un polinomio de grado $n$ con coeficientes reales. Para demostrar la propiedad $\mathcal{Q}(n)$: "$P(x)$ de grado $n$ satisface $\mathcal{Q}$", se procede así:

Base: verificar $\mathcal{Q}(0)$ (polinomios constantes) y $\mathcal{Q}(1)$ (polinomios lineales).

Paso: asumir $\mathcal{Q}(k)$ para todo $k \le n$ (hipótesis fuerte) y demostrar $\mathcal{Q}(n+1)$. La estrategia típica es factorizar $P(x) = (x - r) \cdot Q(x)$ donde $\deg Q = n$, aplicar la hipótesis a $Q$, y ensamblar la propiedad para $P$.

Ejemplo. Sea $P(x)$ un polinomio de grado $n \ge 1$ con coeficientes enteros. Demostrar que si $P(a) = P(b) = 0$ con $a \ne b$ enteros, entonces $(a - b) \mid P(k) - P(j)$ para todos los enteros $k, j$. La demostración procede factorizando $P(x) - P(j) = (x - j) \cdot Q(x)$ con $Q$ de grado $n-1$, y usando la hipótesis de inducción sobre $Q$. El punto clave es que la hipótesis fuerte permite aplicar el resultado a $Q$ directamente.

Inducción en desigualdades algebraicas

Ciertas desigualdades con $n$ variables no admiten una prueba directa por AM-GM, Cauchy-Schwarz o Schur, y la inducción sobre $n$ resulta la ruta más natural. La estrategia general tiene tres pasos:

Paso A — Reducción: mostrar que si la desigualdad falla para $n+1$ variables, entonces falla para $n$ variables (contrarrecíproco), o bien reducir el caso de $n+1$ variables al caso de $n$ variables aplicando la hipótesis inductiva tras eliminar una variable hábilmente.

Paso B — El truco de la variable extrema: en desigualdades simétricas, si hay un máximo $M$ y un mínimo $m$ entre las variables, se puede reemplazar $M$ y $m$ por $M+m-t$ y $t$ (o por $\frac{M+m}{2}$ y $\frac{M+m}{2}$) para igualar dos variables sin empeorar la desigualdad. Esto se llama el método EV (equalizing variables) cuando la función es convexa o cóncava.

Paso C — Base: verificar el caso $n=2$ o $n=3$ directamente.

Ejemplo modelo. Para $n \ge 2$ y $x_1, x_2, \ldots, x_n > 0$ con $x_1 x_2 \cdots x_n = 1$, demostrar que $(1+x_1)(1+x_2)\cdots(1+x_n) \ge 2^n$. Base $n=2$: $(1+x_1)(1+x_2) \ge 4\sqrt{x_1 x_2}...$ con $x_1 x_2 = 1$ da $\ge 4 = 2^2$. $\checkmark$ Paso: $(1+x_1)\cdots(1+x_{n+1}) = (1+x_1)\cdots(1+x_n)(1+x_{n+1})$. Sustituimos $x_n$ por $x_n x_{n+1}$ (el producto de los últimos dos) y aplicamos la hipótesis al producto de $n$ variables: $(1+x_1)\cdots(1+x_n x_{n+1}) \ge 2^n$. Luego multiplicamos por $(1+x_{n+1})$ y usamos $(1 + x_n x_{n+1})(1+x_{n+1}) \ge (1+x_{n+1}^2)...$ El paso correcto es más sutil y usa AM-GM directamente en el factor final. Esta tensión entre la hipótesis y el ensamble final es característica de la inducción en desigualdades.

Ejemplo estilo IbAm/Cono Sur con inducción fuerte

Problema (estilo Cono Sur). Sean $a_1, a_2, \ldots, a_n$ números reales positivos. Probar que para todo $n \ge 1$:

$\dfrac{a_1}{a_2} + \dfrac{a_2}{a_3} + \cdots + \dfrac{a_{n-1}}{a_n} + \dfrac{a_n}{a_1} \ge n.$

Demostración por inducción fuerte.

Base $n=1$: la suma vacía equivale a $a_1/a_1 = 1 \ge 1$. $\checkmark$ Base $n=2$: $\dfrac{a_1}{a_2} + \dfrac{a_2}{a_1} \ge 2$ por AM-GM. $\checkmark$

Hipótesis fuerte: supongamos que el resultado vale para todo $k < n$. Para $n \ge 3$, consideramos la suma $S_n = \sum_{i=1}^{n} \dfrac{a_i}{a_{i+1}}$ (índices mod $n$). Si $a_j \le a_{j+1}$ para algún $j$ (es decir, $\dfrac{a_j}{a_{j+1}} \le 1$ y $\dfrac{a_j}{a_{j-1}} \le \dfrac{a_{j+1}}{a_{j-1}}$), podemos eliminar $a_j$ de la sucesión cíclica y sustituir los dos términos $\dfrac{a_{j-1}}{a_j} + \dfrac{a_j}{a_{j+1}}$ por el único término $\dfrac{a_{j-1}}{a_{j+1}}$. Por AM-GM, $\dfrac{a_{j-1}}{a_j} + \dfrac{a_j}{a_{j+1}} \ge \dfrac{2a_{j-1}^{1/2}}{a_{j+1}^{1/2}} \ge \dfrac{a_{j-1}}{a_{j+1}} + 1$ ... la reducción directa da $S_n \ge S_{n-1} + 1$ (donde $S_{n-1}$ es la suma cíclica con $n-1$ términos). Por hipótesis inductiva $S_{n-1} \ge n-1$, luego $S_n \ge n$. $\square$ (La verificación rigurosa del paso de reducción usa AM-GM: $x + 1/x \ge 2$ para $x = a_{j-1}/a_{j+1} > 0$, lo que da $\dfrac{a_{j-1}}{a_j} + \dfrac{a_j}{a_{j+1}} \ge 2\sqrt{\dfrac{a_{j-1}}{a_{j+1}}} \ge \dfrac{a_{j-1}}{a_{j+1}} + \dfrac{a_{j+1}}{a_{j-1}}$... El argumento estándar usa directamente AM-GM en toda la suma sin inducción, pero la versión inductiva ilustra perfectamente la técnica de reducción.)