Identidades binomiales

Todas las filas del triángulo suman lo mismo... en escala

Mira el triángulo de Pascal: $1$; $1, 1$; $1, 2, 1$; $1, 3, 3, 1$; $1, 4, 6, 4, 1$. Las sumas de fila son $1, 2, 4, 8, 16$. Cada fila suma exactamente el doble de la anterior. ¿Por qué? Porque cada suma es una potencia de 2.

Esta observación esconde una de las identidades más fundamentales del álgebra combinatoria. En esta lección la probaremos con rigor, y aprenderemos tres identidades más que aparecen repetidamente en olimpiadas.

Identidad 1: la suma total de una fila

Para todo entero $n \ge 0$:

$$\sum_{k=0}^{n} \binom{n}{k} = 2^n$$

Prueba algebraica: El teorema del binomio dice $(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k$. Evaluando en $x=1$: $(1+1)^n = \sum_{k=0}^{n}\binom{n}{k} \cdot 1^k$, que da $2^n = \sum_{k=0}^{n}\binom{n}{k}$.

Prueba combinatoria (doble conteo): $2^n$ cuenta el número de subconjuntos de un conjunto de $n$ elementos (cada elemento puede estar o no estar). Agrupando los subconjuntos según su tamaño $k$: los de tamaño $k$ son $\binom{n}{k}$. Sumando sobre todos los tamaños posibles se obtiene el total $2^n$.

Las dos pruebas son instructivas: la algebraica es rápida; la combinatoria muestra el significado profundo.

Identidad 2: la suma alternada

Para todo entero $n \ge 1$:

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

Prueba algebraica: Evaluamos el binomio en $x = -1$: $(1+(-1))^n = \sum_{k=0}^{n}\binom{n}{k}(-1)^k$, que da $0^n = 0$ para $n \ge 1$.

Reformulación útil: Los términos de índice par suman lo mismo que los de índice impar. Es decir, la suma de $\binom{n}{k}$ sobre $k$ par es igual a la suma sobre $k$ impar, y ambas valen $2^{n-1}$.

Aplicación en olimpiadas: Si en un problema aparece una suma alternada de combinatorios, esta identidad o su variante suele ser la clave para simplificarla a cero o a $\pm 2^{n-1}$.

Identidad 3: suma de cuadrados

Para todo entero $n \ge 0$:

$$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$$

Prueba por Vandermonde: Aplicamos la identidad de Vandermonde con $m = r = n$: $\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k}$. Usando la simetría $\binom{n}{n-k} = \binom{n}{k}$, obtenemos $\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}^2$.

Prueba combinatoria: Queremos elegir $n$ personas de un grupo con $n$ hombres y $n$ mujeres: $\binom{2n}{n}$ formas. Alternativamente, si elegimos $k$ hombres y $n-k$ mujeres: hay $\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2$ formas. Sumando sobre $k$ de 0 a $n$, cubrimos todos los casos.

Esta identidad dice que el coeficiente central de la fila $2n$ del triángulo de Pascal es la suma de los cuadrados de los coeficientes de la fila $n$. Es un hecho sorprendente que conecta distintas filas del triángulo.

Identidad 4: el palo de hockey

La identidad del palo de hockey (o identidad de la suma diagonal) dice:

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$$

O en notación de suma: $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$.

Prueba por inducción: Para $n = r$: $\binom{r}{r} = 1 = \binom{r+1}{r+1}$. Paso inductivo: asumiendo $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$, sumamos $\binom{n+1}{r}$: por Pascal, $\binom{n+1}{r+1} + \binom{n+1}{r} = \binom{n+2}{r+1}$.

Por qué se llama "palo de hockey": en el triángulo de Pascal, la suma de una columna diagonal desde $\binom{r}{r}$ hasta $\binom{n}{r}$ "da vuelta" y apunta al resultado $\binom{n+1}{r+1}$, formando la silueta de un palo de hockey.

Aplicación olímpica: Esta identidad es ideal para cerrar sumas telescópicas de combinatorios. Ejemplo: $\binom{1}{1}+\binom{2}{1}+\cdots+\binom{10}{1} = \binom{11}{2} = 55$. O: $\binom{2}{2}+\binom{3}{2}+\cdots+\binom{n}{2} = \binom{n+1}{3}$.

Problema olímpico resuelto

Problema (estilo ONEM): Demuestra que $\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \cdots + n\binom{n}{n} = n \cdot 2^{n-1}$.

Solución por identidad combinatoria: Usamos la identidad $k\binom{n}{k} = n\binom{n-1}{k-1}$ (que se verifica directamente expandiendo los factoriales). Entonces:

$$\sum_{k=1}^{n} k\binom{n}{k} = \sum_{k=1}^{n} n\binom{n-1}{k-1} = n \sum_{j=0}^{n-1} \binom{n-1}{j} = n \cdot 2^{n-1}$$

donde en el último paso usamos la identidad $\sum_{j=0}^{n-1}\binom{n-1}{j} = 2^{n-1}$.

Alternativa por derivación: $(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k$. Derivamos respecto a $x$: $n(1+x)^{n-1} = \sum_{k=1}^{n}k\binom{n}{k}x^{k-1}$. Evaluando en $x=1$: $n \cdot 2^{n-1} = \sum_{k=1}^{n}k\binom{n}{k}$. Dos caminos, la misma respuesta.