Sum of Squares of Binomial Coefficients/Algebraic Proof
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
- 1953: L. Harwood Clarke: A Note Book in Pure Mathematics ... (previous) ... (next): $\text I$. Algebra: The Binomial Theorem: Relations between coeffficients