Sum of Squares of Binomial Coefficients/Combinatorial Proof
This article has been identified as a candidate for Featured Proof status. If you do not believe that this proof is worthy of being a Featured Proof, please state your reasons on the talk page. To discuss this page in more detail, feel free to use the talk page. |
Theorem
- $\ds \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$
Proof
Consider the number of paths in the integer lattice from $\tuple {0, 0}$ to $\tuple {n, n}$ using only single steps of the form:
- $\tuple {i, j} \to \tuple {i + 1, j}$
- $\tuple {i, j} \to \tuple {i, j + 1}$
that is, either to the right or up.
This process takes $2 n$ steps, of which $n$ are steps to the right.
Thus the total number of paths through the graph is equal to $\dbinom {2 n} n$.
Now let us count the paths through the grid by first counting the paths:
- $(1): \quad$ from $\tuple {0, 0}$ to $\tuple {k, n - k}$
and then the paths:
- $(2): \quad$ from $\tuple {k, n - k}$ to $\tuple {n, n}$.
Note that each of these paths is of length $n$.
Since each path is $n$ steps long, every endpoint will be of the form $\tuple {k, n - k}$ for some $k \in \set {1, 2, \ldots, n}$, representing $k$ steps right and $n-k$ steps up.
Note that the number of paths through $\tuple {k, n - k}$ is equal to $\dbinom n k$, since we are free to choose the $k$ steps right in any order.
We can also count the number of $n$-step paths from the point $\tuple {k, n - k}$ to $\tuple {n, n}$.
These paths will be composed of $n - k$ steps to the right and $k$ steps up.
Therefore the number of these paths is equal to $\dbinom n {n - k} = \dbinom n k$.
Thus the total number of paths from $\tuple {0, 0}$ to $\tuple {n, n}$ that pass through $\tuple {k, n - k}$ is equal to the product of:
- the number of possible paths from $\tuple {0, 0}$ to $\tuple {k, n - k}$, which equals $\dbinom n k$
and:
- the number of possible paths from $\tuple {k, n - k}$ to $\tuple {n, n}$, which equals $\dbinom n k$.
So the total number of paths through $\tuple {k, n - k}$ is equal to $\dbinom n k^2$.
Summing over all possible values of $k \in 0, \ldots, n$ gives the total number of paths.
Thus we get:
- $\ds \sum_{k \mathop = 0}^n \binom n k^2 = \binom {2 n} n$
$\blacksquare$