# Hockey-stick identity

In combinatorics, the hockey-stick identity, Christmas stocking identity, boomerang identity, Fermat's identity or Chu's Theorem, states that if $n\geq r\geq 0$ are integers, then
    ${\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).

## Formulations

Using sigma notation, the identity states
    $\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 $j\to i-r$, and by using the identify ${n \choose k}={n \choose n-k}$:
    $\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.$

## Proofs
### Inductive and algebraic proofs

The inductive and algebraic proofs both make use of Pascal's identity:
    ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.$

#### Inductive proof

This identity can be proven by mathematical induction on $n$.
Base case Let $n=r$;
    $\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 $k\in \mathbb {N} ,k\geqslant r$,
    $\sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}$
Then
    $\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}.$

#### Algebraic proof

We use a telescoping argument to simplify the computation of the sum:
    ${\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}}$

### Combinatorial proofs
#### Proof 1

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of the stars and bars method, there are
    ${\binom {n+k-1}{k-1}}$
ways to do this. Alternatively, we can first give $0\leqslant i\leqslant n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with stars and bars and double counting, we have
    ${\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 $n'=n+k-2$ and $r=k-2$, and noticing that $n'-n=k-2=r$:
    ${\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.$

#### Proof 2

We can form a committee of size $k+1$ from a group of $n+1$ people in
    ${\binom {n+1}{k+1}}$
ways. Now we hand out the numbers $1,2,3,\dots ,n-k+1$ to $n-k+1$ of the $n+1$ people. We can then divide our committee-forming process into $n-k+1$ exhaustive and disjoint cases based on the committee member with the lowest number, $x$. Note that there are only $k$ people without numbers, meaning we must choose at least one person with a number in order to form a committee of $k+1$ people. In general, in case $x$, person $x$ is on the committee and persons $1,2,3,\dots ,x-1$ are not on the committee. The rest of the committee can then be chosen in
    ${\binom {n-x+1}{k}}$
ways. Now we can sum the values of these $n-k+1$ disjoint cases, and using double counting, we obtain
    ${\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.$

### Generating function proof

Let $X=1+x$. Then, by the partial sum formula for geometric series, we find that
    $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
$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 $x^{r}$ in $X^{r+k}$ is given by ${\binom {r+k}{r}}$.
Thus, the coefficient of $x^{r}$ in the left hand side of our first equation can be obtained by summing over the coefficients of $x^{r}$ from each term, which gives
$\sum _{k=0}^{n-r}{\binom {r+k}{r}}$
Similarly, we find that the coefficient of $x^{r}$ on the right hand side is given by the coefficient of $x^{r+1}$ in $X^{n+1}-X^{r}$, which is
${\binom {n+1}{r+1}}-{\binom {r}{r+1}}={\binom {n+1}{r+1}}$
Therefore, we can compare the coefficients of $x^{r}$ on each side of the equation to find that
$\sum _{k=0}^{n-r}{\binom {r+k}{r}}={\binom {n+1}{r+1}}$