組み合わせの積の総和 - 興味の赴くままに

数式で説明しようとするとなんか詰まったので書き残し. 次を示す.

$\displaystyle \sum_{\ell=0}^k {}_{m}\mathrm{C}_{\ell} \cdot {}_{n}\mathrm{C}_{\ell-k} = {}_{m+n}\mathrm{C}_{k} \tag{1}$

気持ちは $m+n$ 個から $k$ 個選ぶ組み合わせの総数は, 最初の $m$ 個から $\ell$ 個選び残りの $n$ 個から $k-\ell$ 個選ぶ組み合わせを考えて, $\ell$ を $0\leq \ell \leq k$ で走らせて和を取ればよい, というもの. 組み合わせの定義 ${}_n\mathrm{C}_r = \dfrac{n!}{r! (n-r)!}$ に基づいて帰納法でやろうとしたがうまくいかなかった. 二項定理 $\displaystyle (x+y)^n = \sum_{k=0}^n {}_n\mathrm{C}_k x^k y^{n-k}$ を用いるとうまくいった...不思議. (二項定理の証明について気になる方は次などを参照：二項定理の意味と係数を求める例題・２通りの証明 | 高校数学の美しい物語)

次のように $m, n \in\mathbb{N}$ に対し, $(1+x)^m(1+x)^n$ を考えて二項定理を適用する:

$\begin{align} (1+x)^m(1+x)^n &= \left(\sum_{k_1= 0}^m {}_m\mathrm{C}_{k_1} x^{k_1} \right)\left( \sum_{k_2= 0}^n {}_{n}\mathrm{C}_{k_2} x^{k_2} \right) \\ &=\sum_{k_1= 0}^m\sum_{k_2= 0}^n {}_{m}\mathrm{C}_{k_1} \cdot {}_{n}\mathrm{C}_{k_2}x^{k_1+k_2} \\ &=\sum_{k=0}^{m+n} \left(\sum_{k_1+k_2=k} {}_{m}\mathrm{C}_{k_1} \cdot {}_{n}\mathrm{C}_{k_2} \right) x^k \\ &=\sum_{k=0}^{m+n} \left(\sum_{\ell=0}^k {}_{m}\mathrm{C}_{\ell} \cdot {}_{n}\mathrm{C}_{k-\ell}\right) x^k. \tag{2} \end{align}$