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

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

$ \sum_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k}

proof

$ 1/(1-x)^{d+1} = \sum_{n=0}^\infty \binom{n+d}{d}x^n

$ \displaystyle \sum_{i=0}^{k} [x^{i}]F = [x^{k}] \frac{1}{1-x}F

$ \binom{n + m}{m} = \binom{n + m}{n}

$ \sum_{i=0}^k \binom{n+i}{i} = \sum_{i=0}^{k} [x^{i}] \sum_{m=0}^\infty \binom{n+m}{m}x^m ... 係数の部分和

$ \sum_{i=0}^{k} [x^{i}] \sum_{m=0}^\infty \binom{n+m}{m}x^m = [x^{k}] \frac{1}{1-x}\sum_{m=0}^\infty \binom{n+m}{m}x^m ... by eq4-2

$ [x^{k}] \frac{1}{1-x}\sum_{m=0}^\infty \binom{n+m}{m}x^m = [x^{k}] \frac{1}{1-x}\sum_{m=0}^\infty \binom{n+m}{n}x^m ... by eq4-3

$ [x^{k}] \frac{1}{1-x}\sum_{m=0}^\infty \binom{n+m}{n}x^m = [x^{k}] \frac{1}{1-x} \frac{1}{(1-x)^{n+1}} ... by eq4-1

$ [x^{k}] \frac{1}{1-x} \frac{1}{(1-x)^{n+1}} = [x^{k}] \frac{1}{(1-x)^{n+2}} ... 整理

$ [x^{k}] \frac{1}{(1-x)^{n+2}} = [x^{k}] \sum_{m=0}^\infty \binom{m+n+1}{n+1}x^n ... by eq4-1

$ [x^{k}] \sum_{m=0}^\infty \binom{m+n+1}{n+1}x^n = \binom{k+n+1}{n+1} ... 形式的べき級数の係数

$ \binom{k+n+1}{n+1} = \binom{k+n+1}{k} ... by eq4-3

https://gyazo.com/cb5165171cd65ea576c0bb8ccad20320