Hockey-stick identity

In combinatorics, the hockey-stick identity,^[1] Christmas stocking identity,^[2] boomerang identity, Fermat's identity or Chu's Theorem,^[3] states that if ${\displaystyle n\geq r\geq 0}$ are integers, then

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

The name stems from the graphical representation of the identity on Pascal's triangle: when the addends represented in the summation and the sum itself are highlighted, the shape revealed is vaguely reminiscent of those objects (see hockey stick, Christmas stocking).

Using sigma notation, the identity states

${\displaystyle \sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r}$

or equivalently, the mirror-image by the substitution ${\displaystyle j\to i-r}$, and by using the identify ${\displaystyle {n \choose k}={n \choose n-k}}$:

${\displaystyle \sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r.}$

The inductive and algebraic proofs both make use of Pascal's identity:

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}$

This identity can be proven by mathematical induction on ${\displaystyle n}$.

Base case Let ${\displaystyle n=r}$;

${\displaystyle \sum _{i=r}^{n}{i \choose r}=\sum _{i=r}^{r}{i \choose r}={r \choose r}=1={r+1 \choose r+1}={n+1 \choose r+1}.}$

Inductive step Suppose, for some ${\displaystyle k\in \mathbb {N} ,k\geqslant r}$,

${\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}$

Then

${\displaystyle \sum _{i=r}^{k+1}{i \choose r}=\left(\sum _{i=r}^{k}{i \choose r}\right)+{k+1 \choose r}={k+1 \choose r+1}+{k+1 \choose r}={k+2 \choose r+1}.}$

We use a telescoping argument to simplify the computation of the sum:

${\displaystyle {\begin{aligned}\sum _{t=\color {blue}0}^{n}{\binom {t}{k}}=\sum _{t=\color {blue}k}^{n}{\binom {t}{k}}&=\sum _{t=k}^{n}\left[{\binom {t+1}{k+1}}-{\binom {t}{k+1}}\right]\\&=\sum _{t=\color {green}k}^{\color {green}n}{\binom {\color {green}{t+1}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&=\sum _{t=\color {green}{k+1}}^{\color {green}{n+1}}{\binom {\color {green}{t}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&={\binom {n+1}{k+1}}-\underbrace {\binom {k}{k+1}} _{0}&&{\text{by telescoping}}\\&={\binom {n+1}{k+1}}.\end{aligned}}}$

Imagine that we are distributing ${\displaystyle n}$ indistinguishable candies to ${\displaystyle k}$ distinguishable children. By a direct application of the stars and bars method, there are

${\displaystyle {\binom {n+k-1}{k-1}}}$

ways to do this. Alternatively, we can first give ${\displaystyle 0\leqslant i\leqslant n}$ candies to the oldest child so that we are essentially giving ${\displaystyle n-i}$ candies to ${\displaystyle k-1}$ kids and again, with stars and bars and double counting, we have

${\displaystyle {\binom {n+k-1}{k-1}}=\sum _{i=0}^{n}{\binom {n+k-2-i}{k-2}},}$

which simplifies to the desired result by taking ${\displaystyle n'=n+k-2}$ and ${\displaystyle r=k-2}$, and noticing that ${\displaystyle n'-n=k-2=r}$:

${\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}$

Count the ${\displaystyle (k+1)}$-element subsets of the set ${\displaystyle \{1,2,\ldots ,n+1\}}$ in two ways.

There are clearly ${\displaystyle {\binom {n+1}{k+1}}}$ such subsets in total.

Alternatively, partition these subsets according to their largest element. If the largest element is ${\displaystyle r+1}$, where ${\displaystyle k\leq r\leq n}$, then the remaining ${\displaystyle k}$ elements must be chosen from ${\displaystyle \{1,2,\ldots ,r\}}$, which can be done in ${\displaystyle {\binom {r}{k}}}$ ways.

Therefore, $${\displaystyle \sum _{r=k}^{n}{\binom {r}{k}}={\binom {n+1}{k+1}}.}$$

Let ${\displaystyle X=1+x}$. Then, by the partial sum formula for geometric series, we find that

${\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}={\frac {X^{n+1}-X^{r}}{x}}}$.

Further, by the binomial theorem, we also find that

${\displaystyle X^{r+k}=(1+x)^{r+k}=\sum _{i=0}^{r+k}{\binom {r+k}{i}}x^{i}}$.

Note that this means the coefficient of ${\displaystyle x^{r}}$ in ${\displaystyle X^{r+k}}$ is given by ${\displaystyle {\binom {r+k}{r}}}$.

Thus, the coefficient of ${\displaystyle x^{r}}$ in the left hand side of our first equation can be obtained by summing over the coefficients of ${\displaystyle x^{r}}$ from each term, which gives

${\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}}$

Similarly, we find that the coefficient of ${\displaystyle x^{r}}$ on the right hand side is given by the coefficient of ${\displaystyle x^{r+1}}$ in ${\displaystyle X^{n+1}-X^{r}}$, which is

${\displaystyle {\binom {n+1}{r+1}}-{\binom {r}{r+1}}={\binom {n+1}{r+1}}}$

Therefore, we can compare the coefficients of ${\displaystyle x^{r}}$ on each side of the equation to find that

${\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}={\binom {n+1}{r+1}}}$

• Pascal's identity
• Pascal's triangle
• Leibniz triangle
• Vandermonde's identity
• Faulhaber's formula, for sums of arbitrary polynomials.

• On AOPS
• On StackExchange, Mathematics
• Pascal's Ladder on the Dyalog Chat Forum