Sum of Squares of Binomial Coefficients/Combinatorial 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 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$