We will give two different proofs of this fact. The first will be very similar to the previous example (counting subsets). The second proof is a little slicker, using lattice paths.
Proof.
Consider the question: “How many pizzas can you make using \(n\) toppings when there are \(2n\) toppings to choose from?”
Answer 1: There are \(2n\) toppings, from which you must choose \(n\text{.}\) This can be done in \({2n \choose n}\) ways.
Answer 2: Divide the toppings into two groups of \(n\) toppings (perhaps \(n\) meats and \(n\) veggies). Any choice of \(n\) toppings must include some number from the first group and some number from the second group. Consider each possible number of meat toppings separately:
0 meats: \({n \choose 0}{n \choose n}\text{,}\) since you need to choose 0 of the \(n\) meats and \(n\) of the \(n\) veggies.
1 meat: \({n \choose 1}{n \choose n-1}\text{,}\) since you need 1 of \(n\) meats so \(n-1\) of \(n\) veggies.
2 meats: \({n \choose 2}{n \choose n-2}\text{.}\) Choose 2 meats and the remaining \(n-2\) toppings from the \(n\) veggies.
And so on. The last case is \(n\) meats, which can be done in \({n \choose n}{n \choose 0}\) ways.
Thus the total number of pizzas possible is
\begin{equation*}
{n \choose 0}{n \choose n} + {n \choose 1}{n \choose n-1} + {n \choose 2}{n \choose n-2} + \cdots + {n \choose n}{n \choose 0}\text{.}
\end{equation*}
This is not quite the left-hand side … yet. Notice that \({n \choose n} = {n \choose 0}\) and \({n \choose n-1} = {n \choose 1}\) and so on, by the identity in Example 1.4.4. Thus we do indeed get
\begin{equation*}
{n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2\text{.}
\end{equation*}
Since these two answers are answers to the same question, they must be equal, and thus
\begin{equation*}
{n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}\text{.}
\end{equation*}
For an alternative proof, we use lattice paths. This is reasonable to consider because the right-hand side of the identity reminds us of the number of paths from \((0,0)\) to \((n,n)\text{.}\)
Proof.
Consider the question: How many lattice paths are there from \((0,0)\) to \((n,n)\text{?}\)
Answer 1: We must travel \(2n\) steps, and \(n\) of them must be in the up direction. Thus there are \({2n \choose n}\) paths.
Answer 2: Note that any path from \((0,0)\) to \((n,n)\) must cross the line \(x + y = n\text{.}\) That is, any path must pass through exactly one of the points: \((0,n)\text{,}\) \((1,n-1)\text{,}\) \((2,n-2)\text{,}\) …, \((n, 0)\text{.}\) For example, this is what happens in the case \(n = 4\text{:}\)
How many paths pass through \((0,n)\text{?}\) To get to that point, you must travel \(n\) units, and \(0\) of them are to the right, so there are \({n \choose 0}\) ways to get to \((0,n)\text{.}\) From \((0,n)\) to \((n,n)\) takes \(n\) steps, and \(0\) of them are up. So there are \({n \choose 0}\) ways to get from \((0,n)\) to \((n,n)\text{.}\) Therefore there are \({n \choose 0}{n \choose 0}\) paths from \((0,0)\) to \((n,n)\) through the point \((0,n)\text{.}\)
What about through \((1,n-1)\text{.}\) There are \({n \choose 1}\) paths to get there (\(n\) steps, 1 to the right) and \({n \choose 1}\) paths to complete the journey to \((n,n)\) (\(n\) steps, \(1\) up). So there are \({n \choose 1}{n \choose 1}\) paths from \((0,0)\) to \((n,n)\) through \((1,n-1)\text{.}\)
In general, to get to \((n,n)\) through the point \((k,n-k)\) we have \({n \choose k}\) paths to the midpoint and then \({n \choose k}\) paths from the midpoint to \((n,n)\text{.}\) So there are \({n \choose k}{n \choose k}\) paths from \((0,0)\) to \((n,n)\) through \((k, n-k)\text{.}\)
All together then the total paths from \((0,0)\) to \((n,n)\) passing through exactly one of these midpoints is
\begin{equation*}
{n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2\text{.}
\end{equation*}
Since these two answers are answers to the same question, they must be equal, and thus
\begin{equation*}
{n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}\text{.}
\end{equation*}
