📂Lemmas

The formula for the sum of squares of binomial coefficients

Formula ¹

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

Derivation

Binomial theorem: $$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$

Expanding $\left( 1 + x \right)^{2n}$ gives: $$ \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) $$ Since the coefficient of $x^{n}$ on the left-hand side is $\binom{2n}{n}$, it suffices to determine the coefficient of $x^{n}$ on the right-hand side. On the right-hand side, $x^{n}$ is expressed as the sum of all terms among $x^{n-i} x^{j}$ that are $k = i = j$, therefore the following holds. $$ \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*} $$ Now, by factoring out $x^{n}$ and comparing coefficients, we obtain the desired formula. $$ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^{2} $$

■