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

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

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

• proof

  • 負の二項定理 eq4-1

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

  • 形式的べき級数の係数の部分和 eq4-2

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

  • eq4-3

    • $\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

  • パスカルの三角形的解釈

    • 
    • ホッケースティック恒等式|思考力を鍛える数学

二項係数の公式