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*}