ヴァンデルモンドの畳み込みの3通りの証明

ヴァンデルモンドの畳み込みの右辺 ${}_{p+q}\mathrm{C}_n$ は $(x+1)^{p+q}$ を展開したときの $x^n$ の係数である。

この係数をもう1つ別の方法で求める。

$(x+1)^{p+q}\\ =(x+1)^p(x+1)^q\\ =\displaystyle\sum_{k_1=0}^p{}_{p}\mathrm{C}_{k_1}x^{k_1}\displaystyle\sum_{k_2=0}^q{}_{q}\mathrm{C}_{k_2}x^{k_2}$

$x^n$ の係数は $k_1+k_2=n$ となる $k_1,k_2$ に対応する項から出てくるので以下のように表される：

$\displaystyle\sum_{k_1=0}^n{}_p\mathrm{C}_{k_1}\cdot{}_{q}\mathrm{C}_{n-k_1}$

これは，ヴァンデルモンドの畳み込みの左辺なので，証明完了。

男 $p$ 人，女 $q$ 人，合計 $p+q$ 人の中から $n$ 人選ぶ場合の数を考える。

• 全体 $p+q$ 人から一挙に $n$ 人選ぶと ${}_{p+q}\mathrm{C}_n$ 通りで， 右辺の式になる。

• 男を何人選ぶかで場合分けして足し上げると左辺の式になる。具体的には，男が $k$ 人で女が $n-k$ 人，を $k=0,1,\dots,n$ まで足し上げると $\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}$

$q,n$ に関する数学的帰納法で証明する。 $n=0$ のときは $1=1$ より成立。

$q=0$ のときは，左辺も右辺も ${}_{p}\mathrm{C}_n$ となり成立。

$(q-1,n)$ および $(q-1,n+1)$ で成立すると仮定して $(q,n+1)$ の場合を考える。

$\displaystyle\sum_{k=0}^{n+1}{}_{p}\mathrm{C}_{k}\cdot{}_{q}\mathrm{C}_{n+1-k}\\ =\displaystyle\sum_{k=0}^{n+1}{}_{p}\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n+1-k}+\displaystyle\sum_{k=0}^{n+1}{}_{p}\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n-k}\\ =\displaystyle\sum_{k=0}^{n+1}{}_p\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n+1-k}+\displaystyle\sum_{k=0}^{n}{}_{p}\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n-k}\\ ={}_{p+q-1}\mathrm{C}_{n+1}+{}_{p+q-1}\mathrm{C}_{n}\\ ={}_{p+q}\mathrm{C}_{n+1}$

ここで，1行目から2行目への変形と，最終行への変形で二項係数の関係式（パスカルの三角形の性質）を用いた。3行目から4行目への変形で帰納法の仮定を用いた。