Suma de elementos en diagonal (palo de hockey).
La Fórmula de la Suma Diagonal, muy conocida como la Hockey Stick Identity, es un resultado fundamental en combinatoria que describe la suma de coeficientes binomiales a lo largo de una diagonal del Triángulo de Pascal. Específicamente, dice que la suma de los primeros $n-r+1$ términos a lo largo de una diagonal que empieza en el borde del triángulo (donde los índices superior e inferior son iguales) es igual al coeficiente binomial que está "abajo y a la derecha" del último término de la suma. El nombre "Hockey Stick" viene del patrón visual que forman los términos de la suma y el resultado en el Triángulo de Pascal, que se parece a la forma de un palo de hockey.
Esta identidad es súper importante en las olimpiadas de matemáticas, sobre todo en el AMC 12 y el AIME, porque te permite simplificar series que tienen combinaciones. Se usa seguido para resolver problemas de conteo donde repartes objetos en cajas, o cuando cuentas el número de soluciones enteras de desigualdades. Además, la fórmula sirve como un puente entre sumas algebraicas e interpretaciones combinatorias, y muchas veces deja que reduzcas una suma compleja de casos a una sola operación de "combinación". Una intuición clave para esta fórmula viene de clasificar subconjuntos basándote en su elemento más grande, una técnica que transforma la suma del lado izquierdo directamente en el coeficiente del lado derecho.
La forma estándar de la Fórmula de la Suma Diagonal es:
$$ \sum_{i=r}^{n} \binom{i}{r} = \binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dots + \binom{n}{r} = \binom{n+1}{r+1} $$
donde $n$ y $r$ son enteros no negativos con $n \ge r$.
Indexación Alternativa: A veces la suma se indexa por el número de pasos hacia abajo en la diagonal en lugar de usar el índice superior directamente. Si tomas $k = i-r$, puedes escribir la fórmula así:
$$ \sum_{k=0}^{m} \binom{r+k}{r} = \binom{r+m+1}{r+1} $$
donde $m = n-r$.
Nota sobre el Triángulo de Pascal: La suma empieza en el borde del triángulo, lo que significa que el primer término tiene que ser $\binom{r}{r}$ (que es igual a 1). Si una suma de coeficientes binomiales con un índice inferior $r$ constante no empieza en $\binom{r}{r}$, tienes que sumar y restar los términos que falten para poder usar la fórmula.
Aquí tienes una demostración combinatoria, que suele ser más útil que una por inducción algebraica porque resalta los principios de conteo que hay detrás.
Teorema: Para enteros $n \ge r \ge 0$, $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$.
Demostración: Considera el conjunto $S = {1, 2, 3, \dots, n+1}$. Lo que quieres es encontrar el número de subconjuntos distintos de $S$ que tienen exactamente $r+1$ elementos.
Lado Derecho (RHS): Por definición, el número de formas de elegir un subconjunto de tamaño $r+1$ de un conjunto de tamaño $n+1$ es simplemente: $$ \binom{n+1}{r+1} $$
Lado Izquierdo (LHS): Puedes contar la misma colección de subconjuntos clasificándolos según su elemento más grande. Imagina que $A$ es un subconjunto de $S$ con tamaño $r+1$. Sea $M$ el elemento máximo en $A$. Como $A$ debe tener $r+1$ enteros distintos, el valor más pequeño posible para el elemento máximo $M$ es $r+1$ (que pasa si $A = {1, 2, \dots, r+1}$). El valor más grande posible para $M$ es $n+1$.
Ahora suma sobre todos los valores posibles de $M$:
Como estos casos son mutuamente excluyentes y cubren todos los subconjuntos posibles de tamaño $r+1$, el número total de subconjuntos es la suma de las formas de cada caso. Si dejas que el índice $i$ represente el tamaño del grupo disponible para los $r$ elementos restantes (así que $M = i+1$), sumas desde $i=r$ hasta $i=n$: $$ \sum_{i=r}^{n} \binom{i}{r} $$
Conclusión: Como tanto el LHS como el RHS cuentan el mismo objeto (subconjuntos de tamaño $r+1$ de $n+1$ elementos), tienen que ser iguales. Por lo tanto: $$ \sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1} $$ $\square$