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

**ホッケースティック恒等式**（ホッケースティックこうとうしき、）とは、2つの整数 n \geq r \ge 0 に関して成立する、組み合わせ論における次の恒等式のことである:

: \binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1} 

「ホッケースティックの恒等式」という名前は、パスカルの三角形上で恒等式に出現する項がホッケースティックのように並んでいることに由来する。英語ではホッケースティックの代わりに同様の形状のもので代用されることもあり、例えば**Chirstmas stocking identity**などとも呼ばれる。 

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

\sum^n_{i=r}{i\choose r}={n+1\choose r+1} \qquad \text{ for } n,r\in\mathbb{N}, \quad n\geq r

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

: \sum^{n-r}_{j=0}{j+r\choose r}=\sum^{n-r}_{j=0}{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

## 証明

### 代数学または数学的帰納法による証明
これらの手法は以下に示すパスカルの法則を利用する:

: {n \choose k}={n-1\choose k-1}+{n-1\choose k}

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

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

: \sum^n_{i=r} {i\choose r} = \sum^r_{i=r}{i\choose r}={r\choose r} = 1 = {r+1\choose r+1} = {n+1\choose r+1} 

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

: \sum^k_{i=r}{i\choose r}={k+1\choose r+1}

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

: \begin{align}
(\mathrm{LHS}) &= \sum^{k+1}_{i=r} {i\choose r} = \left(\sum^k_{i=r} {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{align}

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

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

: 
\begin{align}
(\mathrm{LHS})=\sum_{t=k}^n\binom tk
&= \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{align}


### 組み合わせ論による証明

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

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

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

注目している袋に i 個だけ玉を入れ、残りを分配する方法は\left(\!\!{k-1 \choose n-i}\!\!\right)=\binom{n-i+k-2}{n-i} 通りだけある。これでによる証明が適用できるので、

: \binom{n+k-1}{n}=\sum_{i=0}^n\binom{n-i+k-2}{n-i}

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

: \begin{align}
\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{align}

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

#### 証明2
n+1 個の要素からなる集合から、 k+1 個の要素を持つ部分集合を構成することを考える。そのような部分集合は

:  \binom{n+1}{k+1}

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

: \binom{n-x+1}{k}

通りある。あとは を利用することで、 

:  \binom{n+1}{k+1} = \sum_{x=1}^{n-k+1}\binom {n-x+1}{k} = \binom{n}{k}+\cdots+\binom{k}{k}

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

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

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

さらに、二項定理により

X^{r + k} = (1+x)^{r + k} = \sum_{i = 0}^{r + k} \binom{r + k}{i} x^{i} 

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

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

\sum_{k = 0}^{n-r} \binom{r + k}{r} 

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

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

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

\sum_{k = 0}^{n-r} \binom{r + k}{r} = \binom{n + 1}{r + 1} 

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

## 関連項目

* パスカルの法則
* パスカルの三角形
* ライプニッツの調和三角形
* 
* ファウルハーバーの公式

## 脚注

## 外部リンク
* On AOPS
* On StackExchange, Mathematics
* ''Pascal's Ladder'' on the Dyalog Chat Forum