Coeficientes binomiales: propiedades

El binomio como generador de identidades

Una de las ideas más poderosas de la combinatoria es que el teorema del binomio no es solo una fórmula de expansión: es una máquina generadora de identidades. Sustituyendo valores concretos de $x$ (o de $a$ y $b$), obtenemos relaciones entre coeficientes binomiales que serían difíciles de probar de otro modo.

En esta lección probaremos cuatro identidades fundamentales que aparecen en la ONEM y que nacen directamente del binomio. Cada prueba sigue el mismo patrón: toma la igualdad $(a+b)^n = \sum_{k=0}^n \binom{n}{k}a^{n-k}b^k$ y sustituye valores inteligentes.

Identidad 1 — Suma total: $\sum\binom{n}{k} = 2^n$

Sustituimos $a = b = 1$ en el binomio de Newton:

$$(1+1)^n = \sum_{k=0}^{n}\binom{n}{k}1^{n-k}\cdot 1^k \quad\Longrightarrow\quad 2^n = \sum_{k=0}^{n}\binom{n}{k}$$

Interpretación combinatoria: $2^n$ es el número de subconjuntos de un conjunto de $n$ elementos. La identidad dice que si agrupamos los subconjuntos por tamaño, los de tamaño $k$ son $\binom{n}{k}$, y su suma total da $2^n$. Las dos pruebas (algebraica y combinatoria) son igualmente válidas en competencia.

Identidad 2 — Suma alternada: $\sum(-1)^k\binom{n}{k} = 0$

Sustituimos $a = 1$, $b = -1$ en el binomio de Newton:

$$(1-1)^n = \sum_{k=0}^{n}\binom{n}{k}(-1)^k \quad\Longrightarrow\quad 0 = \sum_{k=0}^{n}(-1)^k\binom{n}{k} \quad (n \ge 1)$$

Reformulación: la suma de los $\binom{n}{k}$ con $k$ par es igual a la suma con $k$ impar, y ambas valen $2^{n-1}$. Esto se obtiene combinando esta identidad con la Identidad 1.

Aplicación olímpica: si ves una suma de combinatorios con signos alternados en un problema, esta identidad —o su variante con potencias de $x$— es casi siempre la clave.

Identidad 3 — Absorción: $k\binom{n}{k} = n\binom{n-1}{k-1}$

Esta identidad se prueba algebraicamente expandiendo los factoriales:

$$k\binom{n}{k} = k \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!(n-k)!} = n\binom{n-1}{k-1}$$

Aplicación inmediata: derivando $(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k$ respecto a $x$ y evaluando en $x = 1$, obtenemos $n \cdot 2^{n-1} = \sum_{k=0}^{n} k\binom{n}{k}$. Esta suma ponderada aparece en muchos problemas de olimpiada.

Uso en problemas: siempre que veas $k\binom{n}{k}$ en una suma, reemplázalo por $n\binom{n-1}{k-1}$ para simplificar. El factor $k$ "baja" al interior del combinatorio.

Identidad 4 — Vandermonde: $\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$

La identidad de Vandermonde se deduce comparando coeficientes en el producto $(1+x)^m \cdot (1+x)^n = (1+x)^{m+n}$:

$$\left(\sum_{k=0}^{m}\binom{m}{k}x^k\right)\left(\sum_{j=0}^{n}\binom{n}{j}x^j\right) = \sum_{r=0}^{m+n}\binom{m+n}{r}x^r$$

El coeficiente de $x^r$ en el lado izquierdo es $\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$ (sumando los productos de términos cuyas potencias suman $r$). Igualando con el coeficiente en el lado derecho: $\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$.

Caso especial clave: tomando $m=n=r$, y usando $\binom{n}{n-k}=\binom{n}{k}$, se obtiene $\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}^2$. Esta identidad dice que el coeficiente central de la fila $2n$ es la suma de los cuadrados de la fila $n$.