Σ(x=0,1,2,...,r) C(m,x) C(n,r-x) = C(m+n,r) の数式での証明

syetaniさん

m+n=Nとおいて、改めて式を
Σ(x=0,1,2,...,r) C(m,x) C(N-m,r-x) = C(N,r)
と書く。

Nに関する帰納法で証明する。
N以下のすべての自然数について
C(N,r)＝Σ(x=0,1,2,...,r) C(m,x) C(N-m,r-x)
が成り立つと仮定する。
C(N+1,r)=C(N,r)+C(N,r-1)
なので（この証明はC(N,r)=N!/(r!(N-r)!)から容易）
仮定より
C(N+1,r)=Σ[x=1,2,…,r]C(m,x)C(N-m,r-x)+Σ[x=1,2,…,r-1]C(m,x)C(N-m,r-x-1)
=（Σ[x=1,2,…,r-1]C(m,x){C(N-m,r-x)+C(N-m,r-x-1)}）+C(m,r) （x=1,…,r-1の項についてC(m,x)でくくる）
=（Σ[x=1,2,…,r-1]C(m,x){C(N-m+1,r-x}）+C(m,r)
=Σ[x=1,2,…,r]C(m,x){C(N-m+1,r-x}