Pascal's triangle, rows 0 through 7. The hockey stick identity confirms, for example: for
n=6,
r=2: 1+3+6+10+15=35.
In combinatorial mathematics, the identity
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39ca9b5bdbd62b8335df01364d8650bfe314a1a2)
or equivalently, the mirror-image by the substitution
:
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bcd6833a9ce2fec099f922a0a64bb6faefe7742)
is known as the hockey-stick,[1] Christmas stocking identity,[2] boomerang identity, or Chu's Theorem.[3] 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).
Proofs
Generating function proof
We have
![{\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/173daae7db54e382ac6be423f6ad0657fc203b4e)
Let
, and compare coefficients of
.
Inductive and algebraic proofs
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4828d956ef936f8d9533953c6e3473c7bde410d5)
Inductive proof
This identity can be proven by mathematical induction on
.
Base case
Let
;
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7cd5d38710299739da51b4e21e26145b4c7362d)
Inductive step
Suppose, for some
,
![{\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46af95c610830cd9213ec18ab1331678c5065429)
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc752b84b999235c3651124f9f2bfe26ed0aa10c)
Algebraic proof
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ce84ab741d7707c5b7c8fd325a2db456d91c14c)
Combinatorial proofs
Proof 1
Imagine that we are distributing
indistinguishable candies to
distinguishable children. By a direct application of the stars and bars method, there are
![{\displaystyle {\binom {n+k-1}{k-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2f50898b606219d61c737dddccf656677f3e0bf)
ways to do this. Alternatively, we can first give
candies to the oldest child so that we are essentially giving
candies to
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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb8022fd832ef0399bce374b422882baa2b1184d)
which simplifies to the desired result by taking
and
, and noticing that
:
![{\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12d6833d72ee3bdf2fc69fc5b078357c3ff6c8f6)
Proof 2
We can form a committee of size
from a group of
people in
![{\displaystyle {\binom {n+1}{k+1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aeb68e1b44875b49ef2ba4c1dfaf646897a0e806)
ways. Now we hand out the numbers
to
of the
people. We can divide this into
disjoint cases. In general, in case
,
, person
is on the committee and persons
are not on the committee. This can be done in
![{\displaystyle {\binom {n-x+1}{k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6cae789f340b47a5282a2508dce814eafcd2363)
ways. Now we can sum the values of these
disjoint cases, getting
![{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/084c6e49e59500434647f3cb0e17331d6258a266)
See also
References
External links