Identidad del Palo de Hockey

Teoría

La Identidad del Palo de Hockey, también conocida como la Identidad de la Bota de Navidad o la Fórmula de la Suma Diagonal, es una identidad combinatoria muy útil que involucra sumas de coeficientes binomiales. Dice que la suma de los coeficientes binomiales a lo largo de una diagonal del Triángulo de Pascal, empezando desde un borde (donde $n=k$), es igual al coeficiente binomial que está "abajo y a la derecha" del último término de la suma. Visualmente, si resaltas los términos que estás sumando y el resultado en el Triángulo de Pascal, la forma se parece a un palo de hockey.

Esta identidad se usa mucho en matemáticas de competencia, como en el AMC 12 y el AIME, para simplificar sumatorias donde el índice inferior del coeficiente binomial se queda fijo mientras que el índice superior cambia. Es súper útil para reducir series complejas a un solo término, y muchas veces transforma un problema de sumar varios casos en un cálculo directo.

La intuición detrás de la identidad viene del conteo combinatorio. Aunque la derivación algebraica se basa en aplicar varias veces la Identidad de Pascal, la perspectiva combinatoria ve la identidad como una forma de clasificar subconjuntos según su elemento más grande. Esta técnica te permite calcular rápido sumas que de otra forma necesitarían cálculos tediosos o inducción.

Fórmulas Clave

La forma estándar de la Identidad del Palo de Hockey 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 tales que $n \ge r \ge 0$.

Notas importantes:

• La sumatoria debe empezar en $i=r$ (donde $\binom{r}{r}=1$). Si una suma empieza en un índice $i > r$, tienes que sumar y restar los términos iniciales que faltan para poder usar la identidad.
• Por la simetría del Triángulo de Pascal ($\binom{n}{k} = \binom{n}{n-k}$), también puedes escribir la identidad para la "otra" diagonal, aunque la forma de arriba es la definición estándar.

Forma con límite superior variable: A veces la identidad se escribe con un límite superior variable $k$ para la sumatoria: $$ \sum_{k=0}^{n} \binom{r+k}{k} = \binom{r+n+1}{n} $$ Esto es equivalente a la forma estándar, pero usa la propiedad de simetría $\binom{n}{k} = \binom{n}{n-k}$.

Demostración

Aquí tienes una demostración combinatoria, ya que es la que mejor explica por qué funciona la identidad y es una técnica estándar en la combinatoria de olimpiadas.

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}$. La idea es contar cuántos subconjuntos distintos de $S$ tienen exactamente $r+1$ elementos.

Método 1: Conteo directo 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} $$

Método 2: Contar por el elemento más grande Puedes partir la colección de todos esos subconjuntos basándote en su elemento más grande. Digamos que $L$ es el elemento más grande en un subconjunto específico de tamaño $r+1$. Como el subconjunto debe tener $r+1$ enteros distintos de $S$, el elemento más grande $L$ tiene que ser al menos $r+1$. El valor máximo posible para $L$ es $n+1$. Por lo tanto, los valores posibles para $L$ son ${r+1, r+2, \dots, n+1}$.

Ahora cuenta el número de subconjuntos donde el elemento más grande es exactamente $k+1$ (donde $r \le k \le n$):

1. Un elemento del subconjunto ya está fijo como $k+1$.
2. Tienes que elegir los $r$ elementos restantes del conjunto de enteros que son estrictamente menores que $k+1$.
3. Los enteros disponibles son ${1, 2, \dots, k}$.
4. El número de formas de elegir estos $r$ elementos es $\binom{k}{r}$.

Para encontrar el número total de subconjuntos, suma el número de formas para cada valor posible del elemento más grande. Usa el índice $i$ para representar el tamaño del grupo de donde eliges los $r$ elementos restantes (así que el elemento más grande es $i+1$). Los valores posibles para $i$ van desde $r$ hasta $n$.

Sumando todos los casos: $$ \text{Total de subconjuntos} = \sum_{i=r}^{n} \binom{i}{r} $$

Conclusión: Como el Método 1 y el Método 2 cuentan exactamente el mismo conjunto de objetos, sus resultados deben ser iguales. Así que: $$ \sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1} $$ $\square$