combinatorics - Prove ${n choose k}^2 = sum_{i=0}^{k}{n choose i}{n-i choose k-i}{n-k choose k-i}$ using a combinatorial argument

I've been studying for a final exam. I have gotten stuck on this one question that asks us to prove using a double-counting proof that
$${n \choose k}^2 = \sum_{i=0}^{k}{n \choose i}{n-i \choose k-i}{n-k \choose k-i}$$

I wish I could give an attempted answer, but I don't really know where to begin with this.Could someone please help me out?

Thank You

Answer

Let us think about what we know of that the left-side counts since it is a more natural expression. $\binom{n}{k}$ counts the number of ways of selecting $k$ objects from $n$ total, so $\binom{n}{k}^2$ counts the number of ways of selecting $k$ objects from one batch of $n$ objects and selecting another $k$ objects from a different batch of $n$ objects.

Let our hypothetical scenario be that we have two urns of $n$ labeled balls each, one urn containing red balls and one urn containing blue balls. Each ball will be labeled an integer $1$ through $n$ such that exactly one of each number appears in each urn.

The LHS counts then how many ways we can take $k$ red balls and $k$ blue balls.

---

Let us try to count this a different way so that it matches the RHS.

Let $i$ denote the number of numbers which match between the balls selected from the red urn and blue urn.

If there are $i$ numbers which match, let us pick which $i$ numbers those were. This can be accomplished in $\binom{n}{i}$ ways.

Once chosen, let us pick the remaining $k-i$ blue balls. This can be accomplished in $\binom{n-i}{k-i}$ ways.

Now that we have our selection of blue balls, let us pick the remaining $k-i$ balls from the red urn such that none of them match any of those numbers chosen for blue. This can be accomplished in $\binom{n-k}{k-i}$ ways.

Ranging over all possible values of $i$ yields the total number of ways to pick $k$ balls from each urn as $\sum\limits_{i=0}^k\binom{n}{i}\binom{n-i}{k-i}\binom{n-k}{k-i}$

Since both methods of counting find a count of the same scenario, the expressions must be equal. The LHS did it without regards to how many numbers on the balls chosen overlapped, whereas the RHS grouped the terms according to how many numbers on the balls chosen overlapped.