ホッケースティック恒等式

総和を表すシグマ記号を用いれば、この恒等式を

${\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}$

と書ける。また、ダミー変数を ${\displaystyle j=i-r}$ へと変更した上で、二項係数の性質 ${\displaystyle {n \choose k}={n \choose n-k}}$ を利用すれば、この恒等式を次のようにも表せることがわかる:

${\displaystyle \sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose r+1}={n+1 \choose n-r}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r}$

Summarize Timeline Top Qs Fact Check

これらの手法は以下に示すパスカルの法則を利用する:

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$

ホッケースティック恒等式は ${\displaystyle n}$ に関する数学的帰納法によって証明できる。

まず、${\displaystyle n=r}$ の時に恒等式が成立することを示す:

${\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}}$

により、${\displaystyle n=r}$ の時に成立していることが示される。次に、ある${\displaystyle k\in \mathbb {N} ,k\geqslant r}$ に対して

${\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}$

と、所与の式が成立していると仮定する。すると、所与の式で ${\displaystyle n=k+1}$ とおいた場合に

${\displaystyle {\begin{aligned}(\mathrm {LHS} )&=\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}=(\mathrm {RHS} )\end{aligned}}}$

が示される。ただし最後の変形にパスカルの法則を用いた。以上2ステップより、数学的帰納法からホッケースティック恒等式が示される。

パスカルの法則から導かれる式を利用して、畳み込み級数を利用する形に帰着させることで証明できる:

${\displaystyle {\begin{aligned}(\mathrm {LHS} )=\sum _{t=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}\\&={\binom {n+1}{k+1}}=({\text{RHS}})\end{aligned}}}$

${\displaystyle n}$ 個の区別不能な玉を ${\displaystyle k}$ 個の識別可能な袋に入れる状況を考える。多重集合の議論により、このような状況で袋に分配する方法は

${\displaystyle \left(\!\!{k \choose n}\!\!\right)={\binom {n+k-1}{n}}}$

通りだけある。ここで、${\displaystyle k}$ 個ある袋の中から特定の1つに着目すると、分配の結果その袋の中には玉が ${\displaystyle 0\leqslant i\leqslant n}$ 個だけ入ることになる。今、その袋に ${\displaystyle i}$ 個だけ玉を入れるような分配法をそれぞれの ${\displaystyle i}$ について数え上げ、それを全ての ${\displaystyle i}$ について和をとれば、全ての分配方法の数に一致する。

注目している袋に ${\displaystyle i}$ 個だけ玉を入れ、残りを分配する方法は${\displaystyle \left(\!\!{k-1 \choose n-i}\!\!\right)={\binom {n-i+k-2}{n-i}}}$ 通りだけある。これでダブルカウンティング（英語版）による証明が適用できるので、

${\displaystyle {\binom {n+k-1}{n}}=\sum _{i=0}^{n}{\binom {n-i+k-2}{n-i}}}$

が成立する。あとは、${\displaystyle r=k-2,n'=n+k-2=n+r}$ なる変数変換のもとで

${\displaystyle {\begin{aligned}{\binom {n'+1}{r+1}}&={\binom {n+k-1}{k-1}}={\binom {n+k-1}{n}}\\&=\sum _{i=0}^{n}{\binom {n-i+k-2}{n-i}}=\sum _{i=0}^{n}{\binom {i+r}{i}}=\sum _{i=0}^{n'-r}{\binom {i+r}{i}}\end{aligned}}}$

が得られ、証明が完了する。

${\displaystyle n+1}$ 個の要素からなる集合から、 ${\displaystyle k+1}$ 個の要素を持つ部分集合を構成することを考える。そのような部分集合は

${\displaystyle {\binom {n+1}{k+1}}}$

通りだけある。ここで、${\displaystyle n+1}$ 個の要素のうち任意の${\displaystyle n-k+1}$ 個に、${\displaystyle 1,2,3,\dots ,n-k+1}$ の番号を割り振る。今、番号が割り振られていない要素は ${\displaystyle (n+1)-(n-k+1)=k}$ 個しかないため、${\displaystyle k+1}$ 個の要素からなる部分集合には番号が割り振られている要素が必ず含まれる。部分集合に含まれる番号の割り振られた要素のうち、最小の番号を ${\displaystyle x}$ とするならば、部分集合の構築手法は ${\displaystyle x}$ の数値による場合分けで背反かつ網羅的に分割できる。最小の番号が ${\displaystyle x}$ となるような部分集合を構成するとき、 ${\displaystyle x}$ は必ず部分集合に含まれ、かつ残りの ${\displaystyle k}$ 個の要素は ${\displaystyle x,x-1,\ldots ,1}$を除いた ${\displaystyle n-x+1}$ 個の要素から選択される。よって、そのような選択方法は

${\displaystyle {\binom {n-x+1}{k}}}$

通りある。あとは ダブルカウンティング（英語版）を利用することで、

${\displaystyle {\binom {n+1}{k+1}}=\sum _{x=1}^{n-k+1}{\binom {n-x+1}{k}}={\binom {n}{k}}+\cdots +{\binom {k}{k}}}$

が示され、証明が完了する。

${\displaystyle X=1+x}$ とし、${\displaystyle X^{r}+X^{r+1}+\cdots +X^{n}}$ を展開した時の ${\displaystyle x^{r}}$ の係数を考える。まず、等比級数の公式により、以下が成立する:

${\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}={\frac {X^{n+1}-X^{r}}{x}}}$.

さらに、二項定理により

${\displaystyle X^{r+k}=(1+x)^{r+k}=\sum _{i=0}^{r+k}{\binom {r+k}{i}}x^{i}}$

が任意の自然数 ${\displaystyle k}$ に対して成立する。よって、特に ${\displaystyle x^{r}}$ の係数は ${\displaystyle {\binom {r+k}{r}}}$ で与えられる。

今、${\displaystyle X^{r}+X^{r+1}+\cdots +X^{n}}$を展開した際の${\displaystyle x^{r}}$の係数に関して、${\displaystyle X^{r}+X^{r+1}+\cdots +X^{n}}$に素朴に二項定理を適用すると、

${\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}}$

という表示が得られる。同様に、${\displaystyle (X^{n+1}-X^{r})/x}$ の${\displaystyle x^{r}}$の係数を考えると、これは ${\displaystyle X^{n+1}-X^{r}}$ における ${\displaystyle x^{r+1}}$ の係数に一致するので、

${\displaystyle {\binom {n+1}{r+1}}-{\binom {r}{r+1}}={\binom {n+1}{r+1}}}$

となる。等比級数の公式によりこれらは一致するので、

${\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}={\binom {n+1}{r+1}}}$

が得られ、証明が完了する。