El principio de inducción combinatoria

El principio de inducción matemática

Sea $P(n)$ una propiedad sobre los enteros positivos. El principio de inducción matemática establece: si $P(1)$ es verdadera (caso base) y, para todo $k \ge 1$, $P(k)$ verdadera implica $P(k+1)$ verdadera (paso inductivo), entonces $P(n)$ es verdadera para todo $n \ge 1$.

La metáfora clásica es la fila de fichas de dominó: la primera cae (caso base), y cada ficha que cae derriba la siguiente (paso inductivo). Si ambas condiciones se cumplen, todas las fichas caen.

En combinatoria, $P(n)$ suele ser una identidad (por ejemplo, $\sum_{k=0}^n \binom{n}{k} = 2^n$), una cota ($a_n \le 2^n$), o la afirmación de que toda configuración de $n$ objetos tiene cierta propiedad. El reto en olimpiadas no es aplicar mecánicamente el esquema, sino elegir la hipótesis inductiva correcta.

Inducción fuerte y su ventaja en combinatoria

La inducción fuerte (o inducción completa) tiene el siguiente paso inductivo: supone que $P(1), P(2), \ldots, P(k)$ son todas verdaderas, y demuestra $P(k+1)$. Es equivalente a la inducción simple, pero más cómoda cuando el paso de $n$ a $n+1$ usa varios valores anteriores, no solo el inmediato.

La inducción fuerte es natural para demostrar propiedades de recurrencias. Por ejemplo, si $a_n = a_{n-1} + a_{n-2}$ y queremos probar $a_n \le 2^n$, el paso inductivo usa $a_{n-1} \le 2^{n-1}$ y $a_{n-2} \le 2^{n-2}$: $a_n \le 2^{n-1} + 2^{n-2} = 3 \cdot 2^{n-2} \le 2^n$ (pues $3 \le 4$). Aquí se necesitan dos hipótesis anteriores, así que la inducción fuerte es la herramienta adecuada.

Regla práctica: si en el paso inductivo necesitas suponer el resultado para $n-1$ y para $n-2$ (o para más de un valor anterior), usa inducción fuerte desde el principio. No es más difícil que la inducción simple; solo la hipótesis es "más grande".

Inducción combinatoria: demostrar identidades

Una de las aplicaciones más elegantes de la inducción en combinatoria es demostrar identidades que involucran coeficientes binomiales.

Ejemplo: demuestra que $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ por inducción.

**Caso base $n=0$:** $\binom{0}{0} = 1 = 2^0$. ✓

Paso inductivo: supongamos que $\sum_{k=0}^{n} \binom{n}{k} = 2^n$. Entonces:

$\sum_{k=0}^{n+1} \binom{n+1}{k} = \binom{n+1}{0} + \sum_{k=1}^{n} \binom{n+1}{k} + \binom{n+1}{n+1}$.

Usando la identidad de Pascal $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$:

$= 1 + \sum_{k=1}^{n} \left[ \binom{n}{k-1} + \binom{n}{k} \right] + 1 = 1 + \sum_{j=0}^{n-1} \binom{n}{j} + \sum_{k=1}^{n} \binom{n}{k} + 1$.

$= 2 + \left( \sum_{j=0}^{n} \binom{n}{j} - \binom{n}{n} \right) + \left( \sum_{k=0}^{n} \binom{n}{k} - \binom{n}{0} \right) = 2 + (2^n - 1) + (2^n - 1) = 2^{n+1}$. ✓

Nota: existe también una prueba directa (cada subconjunto de $\{1,\ldots,n\}$ incluye o excluye cada elemento, dando $2^n$ subconjuntos), pero la prueba inductiva muestra cómo la identidad de Pascal y la inducción se combinan naturalmente.

Inducción para demostrar propiedades de configuraciones

Muchos problemas olímpicos piden demostrar que toda configuración de $n$ objetos satisface cierta propiedad. La inducción funciona si podemos "reducir" una configuración de tamaño $n$ a una de tamaño $n-1$ sin perder la estructura.

Ejemplo: demuestra que todo polígono convexo con $n$ vértices ($n \ge 3$) se puede triangular usando $n-3$ diagonales no cruzadas, obteniendo exactamente $n-2$ triángulos.

**Caso base $n=3$:** un triángulo ya es una triangulación con $0$ diagonales y $1 = 3 - 2$ triángulo. ✓

Paso inductivo: dado un polígono convexo $P$ con $n \ge 4$ vértices $V_1, V_2, \ldots, V_n$, considera la diagonal $V_1 V_3$ (que existe pues el polígono es convexo y $n \ge 4$). Esta diagonal divide $P$ en el triángulo $V_1 V_2 V_3$ y el polígono convexo $V_1 V_3 V_4 \ldots V_n$ con $n-1$ vértices. Por hipótesis inductiva, el polígono de $n-1$ vértices se triangula con $(n-1) - 3 = n-4$ diagonales, obteniendo $n-3$ triángulos. Sumando el triángulo $V_1 V_2 V_3$ y la diagonal $V_1 V_3$: el total de diagonales es $(n-4) + 1 = n-3$ y el total de triángulos es $(n-3) + 1 = n-2$. ✓

El paso clave fue encontrar una estructura dentro de la configuración grande que permite separar un "pedazo pequeño" (el triángulo $V_1 V_2 V_3$) y reducir al caso de tamaño $n-1$.

Errores comunes en inducción combinatoria

El error más frecuente es el caso base omitido o incorrecto. Por ejemplo, si la propiedad solo vale para $n \ge 3$, el caso base debe ser $n = 3$, no $n = 1$.

Otro error es asumir en el paso inductivo algo más fuerte que la hipótesis disponible. Si la hipótesis dice "para $n = k$" y la demostración usa "para todo $m \le k$", se está usando inducción fuerte sin declararlo; esto no es un error lógico (la inducción fuerte es válida), pero debe quedar explícito.

El tercer error clásico es el argumento circular: usar en el paso inductivo la misma afirmación que se está tratando de demostrar para $n = k+1$, sin haberla reducido a $n = k$.

Consejo final: en una solución olímpica, el esquema debe declarar explícitamente (a) el enunciado $P(n)$, (b) la verificación del caso base, (c) la hipótesis inductiva ("supongamos que $P(k)$ es verdadera para algún $k \ge$ base"), y (d) la demostración de $P(k+1)$ a partir de $P(k)$. Omitir cualquiera de estos puntos resta puntaje.