In combinatorial mathematics, the hockey-stick identity,[1] Christmas stocking identity,[2] boomerang identity, Fermat's identity or Chu's Theorem,[3] states that if
n\geqr\ge0
\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}+ … +\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
n | |
\sum | |
i=r |
{i\chooser}={n+1\chooser+1} forn,r\inN, n\geqr
or equivalently, the mirror-image by the substitution
j\toi-r
n-r | |
\sum | |
j=0 |
{j+r\choose
n-r | |
r}=\sum | |
j=0 |
{j+r\choosej}={n+1\choosen-r} forn,r\inN, n\geqr.
Let
X=1+x
Xr+Xr+1+...+Xn=
Xr-Xn+1 | |
1-X |
=
Xn+1-Xr | |
x |
Xr=(1+x)r=
r+k | |
\sum | |
i=0 |
\binom{r+k}{i}xi
Note that this means the coefficient of
xr
Xr
\binom{r+k}{r}
Thus, the coefficient of
xr
xr
n-r | |
\sum | |
k=0 |
\binom{r+k}{r}
Similarly, we find that the coefficient of
xr
xr
Xn+1-Xr
\binom{n+1}{r+1}-\binom{r}{r+1}=\binom{n+1}{r+1}
Therefore, we can compare the coefficients of
xr
n-r | |
\sum | |
k=0 |
\binom{r+k}{r}=\binom{n+1}{r+1}
The inductive and algebraic proofs both make use of Pascal's identity:
{n\choosek}={n-1\choosek-1}+{n-1\choosek}.
This identity can be proven by mathematical induction on
n
Base caseLet
n=r
n | |
\sum | |
i=r |
{i\chooser}=
r | |
\sum | |
i=r |
{i\chooser}={r\chooser}=1={r+1\chooser+1}={n+1\chooser+1}.
Inductive stepSuppose, for some
k\inN,k\geqslantr
k | |
\sum | |
i=r |
{i\chooser}={k+1\chooser+1}
Then
k+1 | |
\sum | |
i=r |
{i\chooser}=
k | |
\left(\sum | |
i=r |
{i\chooser}\right)+{k+1\chooser}={k+1\chooser+1}+{k+1\chooser}={k+2\chooser+1}.
We use a telescoping argument to simplify the computation of the sum:
\begin{align} \sumt=\color{blue0}n\binom{t}{k}=\sumt=\color{bluek}n\binomtk &=
n\left[ | |
\sum | |
t=k |
\binom{t+1}{k+1}-\binom{t}{k+1}\right]\\ &=\sumt=\color{greenk}\color{greenn}\binom{\color{green}{t+1}}{k+1}-
n | |
\sum | |
t=k |
\binomt{k+1}\\ &=\sumt=\color{green{k+1}}\color{green{n+1}}\binom{\color{green}{t}}{k+1}-
n | |
\sum | |
t=k |
\binomt{k+1}\\ &=\binom{n+1}{k+1}-\underbrace{\binomk{k+1}}0&&bytelescoping\\ &=\binom{n+1}{k+1}. \end{align}
Imagine that we are distributing
n
k
\binom{n+k-1}{k-1}
ways to do this. Alternatively, we can first give
0\leqslanti\leqslantn
n-i
k-1
\binom{n+k-1}{
n\binom{n+k-2-i}{k-2}, | |
k-1}=\sum | |
i=0 |
which simplifies to the desired result by taking
n'=n+k-2
r=k-2
n'-n=k-2=r
\binom{n'+1}{
n | |
r+1}=\sum | |
i=0 |
\binom{n'-i}r=
n' | |
\sum | |
i=r |
\binom{i}r.
We can form a committee of size
k+1
n+1
\binom{n+1}{k+1}
ways. Now we hand out the numbers
1,2,3,...,n-k+1
n-k+1
n+1
n-k+1
x
k
k+1
x
x
1,2,3,...,x-1
\binom{n-x+1}{k}
ways. Now we can sum the values of these
n-k+1
\binom{n+1}{k+1}=\binomnk+\binom{n-1}k+\binom{n-2}k+ … +\binom{k+1}k+\binomkk.