Coeficientes binomiales: trucos de suma y manipulación

El Teorema del Binomio como generatriz

El Teorema del Binomio establece que para cualquier $x, y$ reales (o complejos) y $n$ entero no negativo:

La demostración combinatoria es elegante: al expandir $(x+y)^n = (x+y)(x+y)\cdots(x+y)$ ($n$ factores), cada término del producto se obtiene eligiendo $x$ de $k$ factores e $y$ de los $n-k$ restantes. Como hay $\binom{n}{k}$ formas de hacer esta elección, el coeficiente de $x^k y^{n-k}$ es $\binom{n}{k}$.

La idea clave de esta lección es tratar $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$ como una función generatriz: una función cuya serie de Taylor codifica los coeficientes binomiales. Aplicando operaciones analíticas —sustitución de valores, derivación, integración— obtenemos identidades combinatorias de forma sistemática.

Este método es poderoso porque convierte sumas combinatorias complicadas en cálculos algebraicos estándar. En competencias, la frase clave que activa esta técnica es "evalúa la suma $\sum_{k} f(k) \binom{n}{k}$" donde $f(k)$ es polinomial en $k$.

Sumas con pesos mediante sustitución y derivación

Técnica 1 — Sustitución: Para obtener $\sum_{k} a^k \binom{n}{k}$, sustituir $x = a$, $y = 1$ en el binomio: $\sum_{k=0}^{n} \binom{n}{k} a^k = (1+a)^n$.

Ejemplo: $\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n$ (poniendo $a = 2$).

Técnica 2 — Derivación: La derivada de $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$ respecto a $x$ es $n(1+x)^{n-1} = \sum_{k=1}^{n} k \binom{n}{k} x^{k-1}$. Evaluando en $x = 1$: $\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}$. Multiplicando por $x$ antes de derivar y evaluando en $x = 1$: $\sum_{k=0}^{n} k \binom{n}{k} = n 2^{n-1}$.

Técnica 3 — Derivación iterada: Para $\sum k^2 \binom{n}{k}$, derivamos dos veces. Sea $f(x) = (1+x)^n$. Entonces $f'(x) = n(1+x)^{n-1}$ y $[xf'(x)]' = f'(x) + xf''(x)$. Evaluando: $xf'(x) = \sum k \binom{n}{k} x^k$, luego $(xf'(x))'|_{x=1} = \sum k^2 \binom{n}{k} / 1 = n 2^{n-1} + n(n-1)2^{n-2}$. Usando la identidad $k^2 = k(k-1) + k$: $\sum k^2 \binom{n}{k} = n(n-1)2^{n-2} + n \cdot 2^{n-1} = n(n+1)2^{n-2}$.

Técnica 4 — Integración: Para sumas con denominadores: $\int_0^1 (1+x)^n dx = \sum_{k=0}^{n} \binom{n}{k} \int_0^1 x^k dx = \sum_{k=0}^{n} \frac{\binom{n}{k}}{k+1}$. Evaluando la integral: $\frac{2^{n+1}-1}{n+1} = \sum_{k=0}^{n} \frac{\binom{n}{k}}{k+1}$.

La identidad de absorción y transformaciones algebraicas

La identidad de absorción $k \binom{n}{k} = n \binom{n-1}{k-1}$ (para $k \geq 1$) es la herramienta algebraica más versátil para simplificar sumas con factores polinomiales. La demostración es inmediata: $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}$.

Combinatoriamente: elegir un equipo de $k$ personas de $n$ y designar un capitán equivale a elegir primero al capitán ($n$ formas) y luego elegir los $k-1$ restantes de los $n-1$ sobrantes.

Generalizaciones: $k(k-1) \binom{n}{k} = n(n-1)\binom{n-2}{k-2}$ (absorción doble). En general: $k^{\underline{r}} \binom{n}{k} = n^{\underline{r}} \binom{n-r}{k-r}$ donde $k^{\underline{r}} = k(k-1)\cdots(k-r+1)$ es el factorial descendente. Esto reduce sumas $\sum k^r \binom{n}{k}$ a sumas de la forma $\sum \binom{n-r}{k-r}$, que son $2^{n-r}$ por la identidad de la fila.

Ejemplo completo — suma cubica: $\sum_{k=0}^{n} k^3 \binom{n}{k}$. Escribimos $k^3 = k(k-1)(k-2) + 3k(k-1) + k$ (descomposición en factoriales descendentes). Entonces: $\sum k^3 \binom{n}{k} = n(n-1)(n-2) 2^{n-3} + 3n(n-1) 2^{n-2} + n 2^{n-1} = n 2^{n-3}\bigl((n-1)(n-2) + 6(n-1) + 4\bigr) = n 2^{n-3}(n^2 + 3n + 2) = n(n^2+3n+2) 2^{n-3}$.

Identidad de la doble suma (Rothe–Hagen): $\sum_{k=0}^{n} \binom{n}{k}^2 x^k =$ coeficiente de $y^n$ en $(1 + xy)^n(1+y)^n$. Esta generalización de Vandermonde aparece en problemas avanzados de conteo.

Sumas con paridad: separar pares e impares

Una técnica muy útil es separar los coeficientes binomiales según la paridad de $k$. Tenemos:

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$ (suma de todos)

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ para $n \geq 1$ (suma alternada)

Sumando y restando: $\sum_{k \text{ par}} \binom{n}{k} = 2^{n-1}$ y $\sum_{k \text{ impar}} \binom{n}{k} = 2^{n-1}$. El número de subconjuntos de tamaño par es igual al número de subconjuntos de tamaño impar (ambos $2^{n-1}$) para $n \geq 1$.

Más generalmente, usando las raíces cuartas de la unidad $i = \sqrt{-1}$, podemos extraer coeficientes con $k \equiv r \pmod{4}$: $\sum_{k \equiv r \pmod 4} \binom{n}{k} = \frac{1}{4}\bigl(2^n + (1+i)^n(-i)^r + (1-1)^n \cdot 0 + (1-i)^n (i)^r\bigr)$. La idea general es que para extraer coeficientes $k \equiv r \pmod m$, se usan las $m$ raíces $m$-ésimas de la unidad.

Problema paradigmático: Demuestra que $\sum_{j=0}^{\lfloor n/3 \rfloor} \binom{n}{3j} = \frac{2^n + 2\cos(n\pi/3)}{3}$. Usando $\omega = e^{2\pi i/3}$ (raíz cúbica primitiva de la unidad): $3\sum_{j} \binom{n}{3j} = (1+1)^n + (1+\omega)^n + (1+\omega^2)^n$. Luego $|1+\omega| = 1$ y $\arg(1+\omega) = \pi/3$, así $(1+\omega)^n = e^{in\pi/3} = \cos(n\pi/3) + i\sin(n\pi/3)$, y sumando con su conjugado obtenemos la fórmula.

Problema trabajado: suma con dos coeficientes

Problema (Iberoamericana 2003, estilo): Calcular $S = \sum_{k=0}^{n} \binom{n}{k} \binom{n+k}{k}$.

Solución: Usaremos la identidad $\binom{n+k}{k} = \binom{n+k}{n}$ y la identidad de suma superior $\sum_{k=0}^{n} \binom{n+k}{n} \binom{n}{k}$.

Consideramos la función generatriz: $\binom{n}{k} =$ coeficiente de $x^k$ en $(1+x)^n$, y $\binom{n+k}{n} =$ coeficiente de $y^n$ en $1/(1-y)^{k+1}$ (serie de potencias). Sin embargo, el enfoque más directo es el de la identidad de Zhu-Vandermonde iterada.

Usamos la identidad $\sum_{k=0}^{n} \binom{n}{k}\binom{n+k}{k} = \sum_{k=0}^{n} \binom{n}{k} \binom{n+k}{n}$. Interpretamos combinatoriamente: $\binom{n+k}{n}$ cuenta las secuencias no decrecientes de $n$ pasos de tamaño $\leq k$, o equivalentemente los caminos reticulares de $(0,0)$ a $(k,n)$.

Método alternativo por recurrencia: sea $S_n = \sum_{k=0}^{n} \binom{n}{k}\binom{n+k}{k}$. Verificamos: $S_0 = 1$, $S_1 = \binom{1}{0}\binom{1}{0} + \binom{1}{1}\binom{2}{1} = 1 + 2 = 3$, $S_2 = 1 + 2\cdot 3 + 6 = 13$, $S_3 = 1 + 3\cdot 4 + 3 \cdot 10 + 20 = 63$. La secuencia $1, 3, 13, 63, \ldots$ satisface $S_n = (2n+1)S_{n-1}/n - S_{n-2}$ (recurrencia de Apéry). En problemas olímpicos, generalmente se pide demostrar una identidad específica o calcular el residuo módulo un primo, y las herramientas son las expuestas en esta lección.

Moraleja: Cuando las sustituciones directas no funcionan, la recurrencia de la suma (usando la regla de Pascal sobre uno de los índices) y las identidades de suma superior son el camino a seguir.