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

同義語:ホッケースティックの恒等式hockey-stick identityhockey stick identityhockey stick theorem

概要

ホッケースティック恒等式(hockey-stick identity)とは、$0$ 以上の整数 $r,n$ について $\sum_{j=r}^n\binom jr=\binom{n+1}{r+1}$ が成り立つという二項係数の恒等式である($n< r$ のとき左辺は空和で $0$)。Pascal の三角形で下の添字が同じ数を $\binom rr$ から順に足すと、足し終えた数の右下の数になる。証明には帰納法、最大の元による分類、差分の打ち消し合いがあり、自然数の和やべき和、四面体数、重複組合せの数を導く道具になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 二項係数, 数学的帰納法

Pascal の三角形で、斜めの列の端の $1$ から順に数を足していくと、足し終えた数のすぐ隣の下の段に、その和がそのまま現れる。たとえば $1+3+6+10+15=35$ で、$35$ は $15$ の右下にある。式で書くと
$$ \binom22+\binom32+\binom42+\binom52+\binom62=\binom73 $$
である。この等式を一般の場合に述べたものが ホッケースティック恒等式(hockey-stick identity)である。足す数の列が柄、折れ曲がった先の和が刃に見えるので、この名がある(「hockey stick theorem」の呼び方は Lev24 §4.5、p. 375 にある)。
この恒等式は、Pascal の関係式を足し合わせただけの短い事実だが、「次数が 1 つ上がる和の公式」として多くの場面に現れる。自然数の和 $\sum j=\binom{n+1}2$ はその最初の場合であり、四面体数、べき和、重複組合せの数、順序統計の期待値もこの恒等式から出る。

問い答え
何を足すのか下の添字が同じ二項係数を、上の添字を $1$ ずつ増やして足す(thm-hs-main)
なぜ成り立つか差分の和が打ち消し合う。数え上げでは最大の元で分類する(節「3 通りの証明」)
上の添字は整数でなくてよいか差の形に直せば実数でよい(prop-hs-real)
途中から足すと$\binom a{r+1}$ の分だけ差が残る(節「反例と注意」)

恒等式の主張

この記事では、$0$ 以上の整数 $n$ と整数 $k$ について $\binom nk$ を、$0\le k\le n$ なら $\dfrac{n!}{k!(n-k)!}$、それ以外なら $0$ と定める。特に $k>n$ では $\binom nk=0$ である。

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

$0$ 以上の整数 $r,n$ について
$$ \sum_{j=r}^n\binom jr=\binom{n+1}{r+1} $$
が成り立つ。$n< r$ のとき左辺は空和で $0$ とする。

帰納法による証明:$r$ を固定して $n$ について帰納法で示す。$n< r$ なら左辺は空和で $0$ であり、右辺も $n+1< r+1$ なので $0$ である。$n=r$ では両辺とも $1$ である。$n\ge r$ で成り立つとすると、Pascal の関係式 $\binom{n+1}{r+1}+\binom{n+1}r=\binom{n+2}{r+1}$ により
$$ \sum_{j=r}^{n+1}\binom jr=\binom{n+1}{r+1}+\binom{n+1}r=\binom{n+2}{r+1} $$
となる。$\square$

Pascal の三角形で、2 段目(一番上を 0 段目とする)の右端の 1 から 15 までの斜めの列を足すと、15 の右下の 35 になる Pascal の三角形で、2 段目(一番上を 0 段目とする)の右端の 1 から 15 までの斜めの列を足すと、15 の右下の 35 になる
図 1 は $r=2$、$n=6$ の場合である。三角形は $\binom ik$ を上から $i$ 段目(一番上を $0$ 段目とする)、左から $k$ 番目(左端を $0$ 番目とする)に置いている。足す数は右上から左下へ並び、和は最後の数の右下にある。左右を反転すれば、左上から右下へ足す形になる。$\binom jr=\binom j{j-r}$ だから、これは同じ恒等式の別の書き方である。

対称な形

$0$ 以上の整数 $s,m$ について
$$ \sum_{k=0}^m\binom{s+k}k=\binom{s+m+1}m. $$

thm-hs-main で $r=s$、$n=s+m$ とし、$j=s+k$ とおく。$\binom{s+k}s=\binom{s+k}k$、$\binom{s+m+1}{s+1}=\binom{s+m+1}m$ なので主張を得る。$\square$

たとえば $s=4$ で
$$ \binom40+\binom51+\binom62+\dots+\binom{4+m}m=\binom{5+m}m $$
である(Lev24 §4.5 の演習 21、p. 375 の形)。$m=2$ なら $1+5+15=21=\binom72$ である。

3 通りの証明

上の証明は帰納法だった。残りの 2 通りは、この等式が「なぜ」成り立つかを別の角度から見せる。

最大の元で分類する

数え上げによる thm-hs-main の証明:$n\ge r$ とする。$\{1,2,\dots,n+1\}$ の $(r+1)$ 元部分集合は全部で $\binom{n+1}{r+1}$ 個ある。その最大の元を $j+1$ とおくと $r\le j\le n$ である。最大の元が $j+1$ である部分集合は、残りの $r$ 個を $\{1,\dots,j\}$ から選んで得られ、選び方は $\binom jr$ 通りである。部分集合ごとに最大の元はただ 1 つ決まるので、$j$ について足すと全体の個数になる。$\square$

差分の和が打ち消し合う

差分による thm-hs-main の証明:$n< r$ なら両辺とも $0$ なので、$n\ge r$ とする。Pascal の関係式を $\binom jr=\binom{j+1}{r+1}-\binom j{r+1}$ と読み、$j=r,\dots,n$ について足すと、隣どうしの項が打ち消し合って
$$ \sum_{j=r}^n\binom jr=\binom{n+1}{r+1}-\binom r{r+1}=\binom{n+1}{r+1} $$
となる。最後に $\binom r{r+1}=0$ を使った。$\square$

この証明は、数列 $a_x:=\binom x{r+1}$ の差分 $a_{x+1}-a_x$ が $\binom xr$ であることを言っている。微分すると次数が下がり、積分すると次数が上がるのと同じように、$\binom xr$ は差分で $\binom x{r-1}$ に下がり、和で $\binom x{r+1}$ に上がる。和と差分のこの関係は 数列の和と差分 の定理「和と差分の基本定理」で一般に述べられている。$\binom xr$ は和の計算で $\dfrac{x^r}{r!}$ の役割を果たす。

格子路で見る

最大の元の分類は、格子路で図にすることもできる。

最後の上向きの辺で分類する

$n\ge r$ とする。点 $(0,0)$ から $(n-r,\,r+1)$ まで、右へ $1$ か上へ $1$ の辺だけで進む道を考える。辺は全部で $n+1$ 本で、そのうち上向きの $r+1$ 本の位置を決めれば道が決まるので、道は $\binom{n+1}{r+1}$ 本ある。
最後の上向きの辺が $(i,r)$ から $(i,r+1)$ へ進むとする($0\le i\le n-r$)。この辺の後は右へ進むだけなので、道はその辺の手前の部分で決まり、$(0,0)$ から $(i,r)$ までの道は $\binom{r+i}r$ 本ある。$i$ について足すと
$$ \sum_{i=0}^{n-r}\binom{r+i}r=\binom{n+1}{r+1} $$
となる。$j=r+i$ とおけば thm-hs-main である。道の形で見ると、「最後に上がる高さが $r$ から $r+1$ に固定され、その位置 $i$ だけが動く」ことが、$\binom jr$ の下の添字が動かないことの理由である。

上の添字を実数にする

実数 $x$ と $0$ 以上の整数 $k$ について
$$ \binom xk:=\frac{x(x-1)\cdots(x-k+1)}{k!} $$
と定める($k=0$ では $1$)。$x$ が $0$ 以上の整数のときは、はじめの定義と一致する。この定義のもとでも、$y$ を実数とすると
$$ \binom{y+1}{r+1}-\binom y{r+1}=\frac{y(y-1)\cdots(y-r+1)}{(r+1)!}\bigl((y+1)-(y-r)\bigr)=\binom yr $$
が成り立つ。したがって差分の証明はそのまま通る。

実数の上の添字

実数 $x$ と $0$ 以上の整数 $r,m$ について
$$ \sum_{k=0}^m\binom{x+k}r=\binom{x+m+1}{r+1}-\binom x{r+1}. $$
また、実数 $s$ と $0$ 以上の整数 $m$ について
$$ \sum_{k=0}^m\binom{s+k}k=\binom{s+m+1}m. $$

前半は上の差分の式を $y=x,x+1,\dots,x+m$ について足せばよい。後半の両辺は $s$ の多項式で、どちらも次数は $m$ 以下である。cor-hs-symmetric により、この 2 つの多項式はすべての $0$ 以上の整数 $s$ で値が一致する。無限個の点で一致する多項式は等しいので、すべての実数 $s$ で等しい。$\square$

前半の式の右辺には $\binom x{r+1}$ が残る。$x$ が $0$ 以上 $r$ 以下の整数のときはこれが $0$ であり、$x=r$ で thm-hs-main に戻る。

中央二項係数の和

$\binom{k-\frac12}k=\dfrac{(2k-1)(2k-3)\cdots1}{2^kk!}=\dfrac1{4^k}\binom{2k}k$ である(分子と分母に $2k(2k-2)\cdots2=2^kk!$ を掛ける)。prop-hs-real の後半を $s=-\frac12$ に使うと
$$ \sum_{k=0}^m\frac1{4^k}\binom{2k}k=\binom{m+\frac12}m. $$
右辺は $\binom{m+\frac12}m=\dfrac{(m+\frac12)(m-\frac12)\cdots\frac32}{m!}=(2m+1)\dfrac{(m-\frac12)(m-\frac32)\cdots\frac12}{m!}=\dfrac{2m+1}{4^m}\binom{2m}m$ と書き直せる。たとえば $m=2$ で左辺は $1+\frac12+\frac38=\frac{15}8$、右辺は $\frac5{16}\cdot6=\frac{15}8$ である。

例と応用

べき和

自然数の和と平方の和

$r=1$ とすると $\sum_{j=1}^nj=\binom{n+1}2=\dfrac{n(n+1)}2$ である。平方の和は、$j^2=2\binom j2+\binom j1$ と書き直してから足す:
$$ \sum_{j=1}^nj^2=2\binom{n+1}3+\binom{n+1}2=\frac{n(n+1)(2n+1)}6. $$
3 乗も同じで、$j^3=6\binom j3+6\binom j2+\binom j1$ から $\sum_{j=1}^nj^3=6\binom{n+1}4+6\binom{n+1}3+\binom{n+1}2$ である。$n=2$ なら $0+6+3=9=1+8$ である。

一般に、$j^m$ を $\binom j0,\binom j1,\dots,\binom jm$ の $1$ 次結合に書き直すことができ(下降階乗冪 の定理「下降階乗冪による展開」)、thm-hs-main を項ごとに使えば $\sum_{j=1}^nj^m$ は $n$ の $m+1$ 次多項式になる。その係数を Bernoulli 数で閉じた形に書いたものが Faulhaberの公式 である。

下降階乗冪の和

$r!\binom jr=j^{\underline r}:=j(j-1)\cdots(j-r+1)$ なので、thm-hs-main の両辺に $r!$ を掛けると
$$ \sum_{j=0}^nj^{\underline r}=\frac{(n+1)^{\underline{r+1}}}{r+1} $$
となる($j< r$ の項は $0$ である)。$\int_0^{n+1}x^r\,dx=\frac{(n+1)^{r+1}}{r+1}$ と同じ形であり、下降階乗冪 の系「下降階乗冪の和の公式」と同じ内容である。$r=2$、$n=4$ では $0+0+2+6+12=20=\frac{5\cdot4\cdot3}3$ である。

連続する整数の積の和

$k(k+1)(k+2)=6\binom{k+2}3$ なので、$j=k+2$、$r=3$ として thm-hs-main を使うと
$$ \sum_{k=1}^nk(k+1)(k+2)=6\sum_{j=3}^{n+2}\binom j3=6\binom{n+3}4=\frac{n(n+1)(n+2)(n+3)}4 $$
である。$n=3$ では $6+24+60=90=\frac{3\cdot4\cdot5\cdot6}4$ である。連続する $m$ 個の整数の積の和は、1 つ多い $m+1$ 個の積を $m+1$ で割った形になる。

図形数

三角数 $T_k=1+2+\dots+k=\binom{k+1}2$ を足した四面体数は、$r=2$ の場合から
$$ \sum_{k=1}^nT_k=\sum_{j=2}^{n+1}\binom j2=\binom{n+2}3 $$
である(角錐数)。もう 1 回足すと $\binom{n+3}4$ になる。$r$ を 1 つ上げるごとに、1 つ高い次元の図形数が現れる。同じ計算で、平面や空間を分ける領域の数も足し上げられる(空間を平面で分ける領域の数)。

重複組合せ

広義単調な列の個数

$N,s$ を $1$ 以上の整数とする。$1\le j_1\le j_2\le\dots\le j_s\le N$ を満たす整数の列 $(j_1,\dots,j_s)$ の個数は $\binom{N+s-1}s$ である。

$s$ について帰納法で示す。$s=1$ では $N=\binom N1$ 個である。$s\ge2$ とし、$s-1$ で正しいとする。$j_s=t$($1\le t\le N$)となる列は、$(j_1,\dots,j_{s-1})$ が $1\le j_1\le\dots\le j_{s-1}\le t$ を満たす列であることと同じだから、帰納法の仮定により $\binom{t+s-2}{s-1}$ 個ある。$i=t+s-2$ とおいて thm-hs-main を使うと、全体の個数は
$$ \sum_{t=1}^N\binom{t+s-2}{s-1}=\sum_{i=s-1}^{N+s-2}\binom i{s-1}=\binom{N+s-1}s $$
である。$\square$

この個数は $N$ 種類のものから重複を許して $s$ 個選ぶ方法の数である。証明の和は「いちばん大きいものが何か」で分類しており、最大の元で分類した prf-hs-counting と同じ考え方である。

順序統計の期待値

無作為な部分集合の最大の元

$1\le r\le n$ とし、$\{1,\dots,n\}$ の $r$ 元部分集合を等しい確率で 1 つ選ぶ。最大の元が $m$ である部分集合は $\binom{m-1}{r-1}$ 個あるので、最大の元の期待値は
$$ \frac1{\binom nr}\sum_{m=r}^nm\binom{m-1}{r-1}=\frac r{\binom nr}\sum_{m=r}^n\binom mr=\frac{r\binom{n+1}{r+1}}{\binom nr}=\frac{r(n+1)}{r+1} $$
である。途中で $m\binom{m-1}{r-1}=r\binom mr$ と thm-hs-main を使った。$n=5$、$r=2$ では、最大の元が $2,3,4,5$ の部分集合はそれぞれ $1,2,3,4$ 個あり、平均は $\frac{2+6+12+20}{10}=4=\frac{2\cdot6}3$ である。最小の元の平均については 二項定理と組合せの恒等式 の節「数学オリンピックの問題から」を見よ。

より一般の恒等式

Vandermondeの恒等式 の定理「上の数についての和」は、$0$ 以上の整数 $a,b$ と $n\ge a+b$ について
$$ \sum_{t=0}^n\binom ta\binom{n-t}b=\binom{n+1}{a+b+1} $$
と述べている。$b=0$ の場合が thm-hs-main である。数え上げでは、最大の元で分類する代わりに、小さい方から $a+1$ 番目の元で分類することに当たる。
母関数で見ると、列 $\bigl(\binom jr\bigr)_{j\ge0}$ の母関数に $\dfrac1{1-T}$ を掛けることが部分和をとることに当たる。thm-hs-main は $\dfrac{T^r}{(1-T)^{r+1}}\cdot\dfrac1{1-T}=\dfrac1T\cdot\dfrac{T^{r+1}}{(1-T)^{r+2}}$ という見かけ上は当たり前の等式の係数の比較である。ただし、二項係数 の命題「二項係数の母関数」はこの恒等式(同記事の命題「対角線の和」)を使って導かれているので、そちらの証明の順序では、これを証明として使うと循環になる。母関数で循環なく示すには、$(1+x)^j$ の和をとる。等比数列の和の公式から $\sum_{j=0}^n(1+x)^j=\dfrac{(1+x)^{n+1}-1}x$ であり、両辺の $x^r$ の係数を比べると thm-hs-main が出る。

反例と注意

恒等式の各条件を 1 つずつ外すと、次のように等式が成り立たなくなる。

外す条件式の例成り立たなくなること
和を $\binom rr$ から始める$\binom32+\binom42+\binom52=3+6+10=19$和は $\binom63=20$ でない。$\binom33=1$ だけ足りない
下の添字をそろえて足す$\binom40+\binom41=1+4=5$同じ段の数を足すと、右下の数 $\binom52=10$ にならない
上の添字が $0$ 以上の整数$\binom{1/2}1+\binom{3/2}1=2$$\binom{5/2}2=\frac{15}8$ と等しくない。差 $\frac18$ が残る

1 行目は次の形にまとめられる。

反例:途中から足すと差が残る

「$\sum_{j=a}^n\binom jr=\binom{n+1}{r+1}$ が $r\le a\le n$ で成り立つ」は $a>r$ で正しくない。thm-hs-main から $\sum_{j=r}^{a-1}\binom jr=\binom a{r+1}$ を引くと、正しい式は
$$ \sum_{j=a}^n\binom jr=\binom{n+1}{r+1}-\binom a{r+1} $$
である。$a>r$ なら $\binom a{r+1}\ge1$ なので、もとの主張は成り立たない。上の表の $r=2$、$a=3$、$n=5$ では $\binom33=1$ の差が出る。

3 行目の差 $\frac18$ は prop-hs-real の $x=\frac12$、$r=1$、$m=1$ の $-\binom{1/2}2=\frac18$ である。$\binom r{r+1}=0$ という消え方は、上の添字が $0$ 以上の整数のときの性質であって、実数の上の添字では一般に残る。
Pascal の三角形の斜めの和には、別の方向のものもある。そちらは二項係数でなく Fibonacci 数を与える。

反例:傾きの違う斜めの和

下の添字を $1$ 増やすごとに上の添字を $1$ 減らして足す $S_n:=\sum_{0\le k\le n/2}\binom{n-k}k$ を考える。$S_0=S_1=1$ であり、$n\ge2$ のとき Pascal の関係式を各項に使うと
$$ S_n=\sum_{0\le k\le n/2}\binom{n-1-k}k+\sum_{1\le k\le n/2}\binom{n-1-k}{k-1}=S_{n-1}+S_{n-2} $$
となる(第 1 の和で $k>(n-1)/2$ の項は $0$ であり、第 2 の和は $k-1$ を $k$ と置き直すと $S_{n-2}$ である)。よって $S_n$ は Fibonacci数 $F_{n+1}$ に等しい。たとえば $S_5=\binom50+\binom41+\binom32=1+4+3=8=F_6$ である(この式は Lucas が述べている。Dic05 p. 395)。足した数は $3$ 段目から $5$ 段目にあるが、和 $8$ は第 $6$ 段までの三角形のどこにも現れない。したがって「どの向きの斜めの和も、足し終えた数の次の段の数になる」という主張は成り立たない。そうなるのは、下の添字をそろえて足すときと、それを左右に反転した cor-hs-symmetric の向きに足すときである。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する