ホッケースティック恒等式と負の二項定理

こういうの、どれくらい常識なのかわからなくて困るなそんなに新規性はないです

ホッケースティック恒等式
$k$ , $n$ を非負整数とします。このとき等式
$\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}$
をホッケースティック恒等式などと言います。第二引数が fix されてる和がとれて、嬉しい！

この赤い丸で囲んだ場所の和が等しいことを主張していて、その形をパスカルの三角形に書くとホッケースティックのような形をしています。私はホッケースティックなんて見たことないのでホッケースティックのような形といえばホッケースティック恒等式の形ですが……
証明は易しく、 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ （パスカルの三角形で隣り合う数を足したものがその下の数になっていること）を使って数学的帰納法を回すのが一番楽だと思います。組合せ的解釈で証明する方法もあって、知りたければ ABC154F - Many Many Paths の公式解説を読んでください。読んでないので嘘かも。

負の二項定理
$k$ は非負整数とします。適当に二項係数の定義域を拡張してあげれば一般の整数でも成り立ちます。
$\frac{1}{(1-x)^{k+1}} = \sum_{n=0}^{\infty}\binom{n+k}{k}x^n$
です。形式的べき級数だと思っていますが、 $|x| < 1$ で収束するので普通のべき級数だと思ってもいいです。第二引数が fix されてて、嬉しい！
証明は、maspy さんいつもありがとうございます。

それらの関係
見るからに似ていますね。まずは負の二項定理の方が強そうな見た目をしているので、
負の二項定理 $\Rightarrow$ ホッケースティック恒等式
以下 $P$ :形式的べき級数に対して $[x^n]P$ を $P$ の $x^n$ の係数とします。
負の二項定理より
$[x^{n-k}]\frac{1}{(1-x)^{k+1}} = \binom{n}{k}$ 。
$\frac{1}{1-x}$ をかけることは累積和をとることに対応していたから、
$[x^{n-k}]\left(\frac{1}{1-x}\frac{1}{(1-x)^{k+1}}\right) =[x^n]\frac{1}{(1-x)^{k+2}} =\sum_{i=0}^n\binom{i}{k}$ 。
これと
$[x^{n-k}]\frac{1}{(1-x)^{k+2}} = \binom{n+1}{k+1}$
を比較することで
$\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}$
を得ます。
ホッケースティック恒等式 $\Rightarrow$ 負の二項定理
実は逆もほぼ同様です。
$k$ に関する数学的帰納法を使います。
$[x^{n}]\frac{1}{(1-x)^{k+1}} = \binom{n+k}{k}$
が成り立ったとして、 $\frac{1}{1-x}$ は累積和より、
$[x^{n}]\frac{1}{(1-x)^{k+2}} = [x^{n}]\left(\frac{1}{1-x}\frac{1}{(1-x)^{k+1}}\right) = \sum_{i=0}^n\binom{i+k}{k} = \sum_{i=k}^{n+k}\binom{i}{k}$
ここでホッケースティック恒等式を使えば
$\sum_{i=k}^{n+k}\binom{i}{k} = \binom{n+k+1}{k+1}$
より、示されました。
これは絵を描くとおもしろくて、

累積和をとると係数列が右下にずれるようになってるんですね～すごくない？全然気づかなかった

おわり
おわり