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. 조합론적(combinatorial) 수학에서, 항등식
∑
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>r}
은 하키-스틱 [1] 크리스마스 스타킹 항등식 [2] 파스칼의 삼각형(Pascal's triangle) 에서 항등식의 그래픽 표시에서 나온 것입니다: 합계에서 표시된 피합수와 합 자체가 강조-표시될 때, 드러난 모양은 막연하게 그들 대상을 연상시킵니다.
Proofs 귀납적 및 대수적 증명 둘 다는 파스칼의 항등식(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 이 항등식은
n
{\displaystyle n}
수학적 귀납법(mathematical induction) 에 의해 입증될 수 있습니다.
기본 경우
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}.}
귀납적 단계
어떤
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}}
그런-다음
∑
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 우리는 합의 계산을 단순화하기 위해 망원하는(telescoping) 인수를 사용합니다:
∑
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}}}
우리가
n
{\displaystyle n}
k
{\displaystyle k}
별과 막대 방법(the stars and bars method) 의 직접 적용에 의해, 이것을 수행하기 위해 다음의 방법이 있습니다:
(
n
+
k
−
1
k
−
1
)
{\displaystyle {\binom {n+k-1}{k-1}}}
대안적으로, 우리는 먼저
n
−
i
{\displaystyle n-i}
k
−
1
{\displaystyle k-1}
0
⩽
i
⩽
n
{\displaystyle 0\leqslant i\leqslant n}
이중 셈(double counting) 과 함께, 우리는 다음을 가집니다:
(
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}},}
이것은
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 우리는
n
+
1
{\displaystyle n+1}
k
+
1
{\displaystyle k+1}
(
n
+
1
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}}
이제 우리는
n
+
1
{\displaystyle n+1}
1
,
2
,
3
,
…
,
n
−
k
+
1
{\displaystyle 1,2,3,\dots ,n-k+1}
n
−
k
+
1
{\displaystyle n-k+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}}}
이제 우리는 이들
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 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://dawoum.duckdns.org/api/rest_v1/media/math/render/svg/9ce84ab741d7707c5b7c8fd325a2db456d91c14c)
