Recurrence relations of binomial coefficients in Pascal's triangle
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
∑
i
=
r
n
(
i
r
)
=
(
n
+
1
r
+
1
)
for
n
,
r
∈
N
,
n
≥
r
{\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
j
→
i
−
r
{\displaystyle j\to i-r}
∑
j
=
0
n
−
r
(
j
+
r
r
)
=
∑
j
=
0
n
−
r
(
j
+
r
j
)
=
(
n
+
1
n
−
r
)
for
n
,
r
∈
N
,
n
≥
r
{\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}
is known as the hockey-stick [1] Christmas stocking identity .[2] 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 [ ] The inductive and algebraic proofs both make use of Pascal's identity :
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
.
{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}
Inductive proof [ ] This identity can be proven by mathematical induction on
n
{\displaystyle n}
Base case
Let
n
=
r
{\displaystyle n=r}
∑
i
=
r
n
(
i
r
)
=
∑
i
=
r
r
(
i
r
)
=
(
r
r
)
=
1
=
(
r
+
1
r
+
1
)
=
(
n
+
1
r
+
1
)
.
{\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
k
∈
N
,
k
⩾
r
{\displaystyle k\in \mathbb {N} ,k\geqslant r}
∑
i
=
r
k
(
i
r
)
=
(
k
+
1
r
+
1
)
{\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}
Then
∑
i
=
r
k
+
1
(
i
r
)
=
(
∑
i
=
r
k
(
i
r
)
)
+
(
k
+
1
r
)
=
(
k
+
1
r
+
1
)
+
(
k
+
1
r
)
=
(
k
+
2
r
+
1
)
.
{\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}.}
Algebraic proof [ ] We use a telescoping argument to simplify the computation of the sum:
∑
t
=
0
n
(
t
k
)
=
∑
t
=
k
n
(
t
k
)
=
∑
t
=
k
n
[
(
t
+
1
k
+
1
)
−
(
t
k
+
1
)
]
=
∑
t
=
k
n
(
t
+
1
k
+
1
)
−
∑
t
=
k
n
(
t
k
+
1
)
=
∑
t
=
k
+
1
n
+
1
(
t
k
+
1
)
−
∑
t
=
k
n
(
t
k
+
1
)
=
(
n
+
1
k
+
1
)
−
(
k
k
+
1
)
⏟
0
by telescoping
=
(
n
+
1
k
+
1
)
.
{\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}}}
A combinatorial proof [ ] Imagine that we are distributing
n
{\displaystyle n}
k
{\displaystyle k}
the stars and bars method , there are
(
n
+
k
−
1
k
−
1
)
{\displaystyle {\binom {n+k-1}{k-1}}}
ways to do this. Alternatively, we can first give
0
⩽
i
⩽
n
{\displaystyle 0\leqslant i\leqslant n}
n
−
i
{\displaystyle n-i}
k
−
1
{\displaystyle k-1}
double counting , we have
(
n
+
k
−
1
k
−
1
)
=
∑
i
=
0
n
(
n
+
k
−
2
−
i
k
−
2
)
,
{\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
n
′
=
n
+
k
−
2
{\displaystyle n'=n+k-2}
r
=
k
−
2
{\displaystyle r=k-2}
n
′
−
n
=
k
−
2
=
r
{\displaystyle n'-n=k-2=r}
(
n
′
+
1
r
+
1
)
=
∑
i
=
0
n
(
n
′
−
i
r
)
=
∑
i
=
r
n
′
(
i
r
)
.
{\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}
Another combinatorial proof [ ] We can form a committee of size
k
+
1
{\displaystyle k+1}
n
+
1
{\displaystyle n+1}
(
n
+
1
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}}
ways. Now we hand out the numbers
1
,
2
,
3
,
…
,
n
−
k
+
1
{\displaystyle 1,2,3,\dots ,n-k+1}
n
−
k
+
1
{\displaystyle n-k+1}
n
+
1
{\displaystyle n+1}
n
−
k
+
1
{\displaystyle n-k+1}
x
{\displaystyle x}
1
⩽
x
⩽
n
−
k
+
1
{\displaystyle 1\leqslant x\leqslant n-k+1}
x
{\displaystyle x}
1
,
2
,
3
,
…
,
x
−
1
{\displaystyle 1,2,3,\dots ,x-1}
(
n
−
x
+
1
k
)
{\displaystyle {\binom {n-x+1}{k}}}
ways. Now we can sum the values of these
n
−
k
+
1
{\displaystyle n-k+1}
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
−
1
k
)
+
(
n
−
2
k
)
+
⋯
+
(
k
+
1
k
)
+
(
k
k
)
.
{\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}}.}
See also [ ] References [ ]
^ CH Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking. Fibonacci Quarterly 34 (3), 280-288.
^ W., Weisstein, Eric. "Christmas Stocking Theorem" . mathworld.wolfram.com . Retrieved 2016-11-01 .
External links [ ] 
![{\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)
