이항계수 제곱합 공식
공식 1
$$ \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} $$
■
Bóna, M. (2025). Introduction to enumerative and analytic combinatorics: p28. ↩︎