Jtdylktuy

I came across an exercise in which we are asked to prove the identity:

$${2nchoose n}=sum_{k=0}^n{nchoose k}^2$$

The exercise gives the hint:

$$left(1+xright)^{2n}=left[(1+x)^nright]^2$$

It's not too difficult to use the hint to prove the identity (the expressions in the identity are the coefficients of $x^n$ in the respective expansions of the expressions in the hint, which of course must be the same number), but I was wondering whether there is a neater equivalent-counting interpretation...

It's clear that ${2n choose n}$ is the number of ways in which we can choose half the elements in a set (where this is possible): how can we interpret $sum_{k=0}^n{nchoose k}^2$ equivalently?

Let $A,B$ be disjoint $n$-element sets; the number of $n$-element subsets of $Acup B$ is $binom{2n}n$. On the other hand, we can get any $n$-element subset of $Acup B$ in the following way: start with the set $A$; pick a number $k$ from $0$ to $n$; throw out $k$ elements of $A$ and replace them with $k$ elements of $B$. In other words, any $n$-element subset of $Acup B$ has the form $(Asetminus X)cup Y$ where $Xsubseteq A$, $Ysubseteq B$, $|X|=|Y|=k$ for some $kin{0,dots,n}$. The number of different sets we can get in this way is $sum_{k=0}^nbinom nkbinom nk$.

This is also a well know interpretation.

Let's think of a shortest way from $(0,0)$ to $(n,n)$ through lattice points and parallel to $x$-axis or $y$-axis.

The number of total way is ${2n choose n}$.

And each shortest way should pass one and only one of the diagonal points $(0,n), (1,n-1), ldots, (n,0)$.

The sum of all way is $sum_{k=0}^n{nchoose k}^2$.

Hence, both value are same.

Another interpretation: As Erick Wong stated in the comments,
$$binom{n}{k}^2 = binom{n}{k}binom{n}{n - k}$$
We can interpret
$$binom{2n}{n}$$
as the number of ways of selecting $n$ people from a group consisting of $n$ men and $n$ women. The expression
$$binom{n}{k}binom{n}{n - k}$$
counts the number of ways of selecting exactly $k$ men and $n - k$ women. Since $k$ may vary from $0$ to $n$, the RHS also counts the number of ways of selecting $n$ people from $n$ men and $n$ women. Hence,
$$binom{2n}{n} = sum_{k = 0}^{n} binom{n}{k}binom{n}{n - k} = sum_{k = 0}^{n} binom{n}{k}^2$$