📂レンマ

二項係数の二乗和の公式

公式 ¹

$$ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^{2} $$

導出

二項定理: $$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$

$\left( 1 + x \right)^{2n}$ を展開すると次のようになる。 $$ \left( 1 + x \right)^{2n} = \left( 1 + x \right)^{n} \left( x + 1 \right)^{n} = \left( \sum_{i=0}^{n} \binom{n}{i} 1^{i} x^{n-i} \right) \left( \sum_{j=0}^{n} \binom{n}{j} x^{j} 1^{n-j} \right) $$ 左辺で $x^{n}$ の係数は $\binom{2n}{n}$ なので、右辺で $x^{n}$ の係数を求めればよい。右辺で $x^{n}$ は $x^{n-i} x^{j}$ のうち $k = i = j$ であるすべての項の和として表されるので、次が成り立つ。 $$ \begin{align*} & \binom{2n}{n} x^{n} \\ =& \sum_{k=0}^{n} \binom{n}{i} x^{i} \binom{n}{j} x^{n-j} \\ =& \sum_{k=0}^{n} \binom{n}{k} x^{k} \binom{n}{k} x^{n-k} \\ =& \sum_{k=0}^{n} \binom{n}{k}^{2} x^{n} \end{align*} $$ ここで $x^{n}$ を外して係数だけ比較すれば求めていた公式が得られる。 $$ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^{2} $$

■