Sum of Squares of Binomial Coefficients/Algebraic Proof

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$


Proof

Consider the Binomial Theorem:

\(\ds \forall n \in \Z_{\ge 0}: \, \) \(\ds \paren {1 + x}^n\) \(=\) \(\ds \sum_{j \mathop = 0}^n \dbinom n j x^j\)
\(\ds \) \(=\) \(\ds \dbinom n 0 x^0 + \dbinom n 1 x^1 + \dbinom n 2 x^2 + \cdots + \dbinom n {n - 1} x^{n - 1} + \dbinom n n x^n\)
\(\text {(1)}: \quad\) \(\ds \) \(=\) \(\ds \dbinom n n x^0 + \dbinom n {n - 1} x^1 + \dbinom n {n - 2} x^2 + \cdots + \dbinom n 1 x^{n - 1} + \dbinom n 0 x^n\) Symmetry Rule for Binomial Coefficients


Let $m$ be the coefficient of $x^n$ in the expansion of $\paren {1 + x}^{2 n} = \paren {1 + x}^n \times \paren {1 + x}^n$.

For all $k \in \set {0, 1, \ldots, n}$, by matching up the coefficient of $x^k$ with that of $x^{n - k}$ in $(1)$, we have:

$m = \ds \sum_{k \mathop = 0}^n \dbinom n k^2$

But from the Binomial Theorem, this given by:

$m = \dbinom {2 n} n$

Hence the result.


Sources