Sum of Squares of Binomial Coefficients/Combinatorial Proof

Theorem

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

where $\displaystyle \binom n i$ is a binomial coefficient.

Proof

Consider the number of paths in the integer lattice from $(0,0)$ to $(n,n)$ using only single steps to the right and single steps up.

This process takes $2n$ steps, of which $n$ are steps to the right.

Thus the total number of paths through the graph is equal to $\displaystyle \binom {2 n} n$.

Now let us count the paths through the grid by first counting the paths from $(0,0)$ to $(k,n-k)$, and then the paths from $(k,n-k)$ to $(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 $(k,n-k)$, representing $k$ steps right and $n-k$ steps up.

Note that the number of paths through $(k,n-k)$ is equal to $\displaystyle \binom 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 $(k,n-k)$ to $(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 $\displaystyle \binom n {n-k} = \displaystyle \binom n k$.

Thus the total number of paths from $(0,0)$ to $(n,n)$ that pass through $(k,n-k)$ is equal to:

the product of the number of possible paths from $(0,0)$ to $(k,n-k) = \displaystyle \binom n k$

and:

the number of possible paths from $(k,n-k)$ to $(n,n) = \displaystyle \binom n k$.

So the total number of paths through $(k,n-k)$ is equal to $\displaystyle \binom n k^2$.

Summing over all possible values of $k \in 0, \ldots, n$ gives the total number of paths.

Thus we get:

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

$\blacksquare$