Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Question

I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.

I already know the logical Proof:

$${n \choose k}^2 = {n \choose k}{ n \choose n-k}$$

Hence summation can be expressed as:

$$\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}$$

One can think of it as choosing $n$ people from a group of $2n$ (imagine dividing a group of $2n$ into $2$ groups of $n$ people each. I can get $k$ people from group $1$ and another $n-k$ people from group $2$. We do this from $k = 0$ to $n$.

Answer 1

The combinatorial explanation is straightforward. There's also a roundabout approach through what are called "generating functions." The binomial theorem tells us that

$$(1+x)^n(x+1)^n=\left(\sum_{a=0}^n\binom{n}{a}x^a\right)\left(\sum_{b=0}^n\binom{n}{b}x^{n-b}\right)=\sum_{c=0}^{2n}\left(\sum_{a+n-b=c}\binom{n}{a}\binom{n}{b}\right)x^c$$

The $x^n$ coefficient of the above occurs with $c=n$, wherein the coefficient is

$$\sum_{a+n-b=n}\binom{n}{a}\binom{n}{b}=\sum_{a=0}^n\binom{n}{a}^2.$$

However, the $x^n$ coefficient of $(1+x)^n(x+1)^n=(1+x)^{2n}$, again by the binomial theorem, is

$$\binom{2n}{n}. $$

Equating the two gives the result.

Answer 2

Considering that the product of polynomials can be expressed as follows $$\sum_{l=0}^{2n}(\sum_{k=0}^{l}(b_{k})(a_{l-k}))x^l=(a_0+a_1x+...+a_nx^n)(b_0+b_1x+...+b_nx^n)$$

In particular $$\sum_{l=0}^{2n}(\sum_{k=0}^{l}\binom{n}{k}\binom{n}{l-k})x^l=(1+x)^{n}(1+x)^{n}=(1+x)^{2n}=\sum_{l=0}^{2n} \binom{2n}{l}x^l$$

$$\sum_{l=0}^{2n}(\sum_{k=0}^{l} \binom{n}{k}\binom{n}{l-k})x^l=\sum_{l=0}^{2n} \binom{2n}{l}x^l$$ For any $l$ you have to

$$(\sum_{k=0}^{l} \binom{n}{k}\binom{n}{l-k})x^l=\binom{2n}{l}x^l$$

In particular for $l = n$

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

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

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

Q.E.D

Answer 3

By double count Imagine you want to make teams with n people and you have n boys and n girl you can make this by choosing n people between 2n people that is $2n \choose n$ but another way to count this is by choosing how many boys you want in each step for example if you want to have 3 boys, then there are ${n \choose 3}*{n \choose n-3}={n \choose 3}^2$ ways to do this, think it for a little you can choose from 0 to n boys in your teamn then the number of teams with n people is $\sum_{k = 0}^n {n \choose k}^2$

Answer 4

You are separating the $\binom{2\times 7}{7}$ paths from the up-left corner to the low-right corner ( where only moves allowed are one down or one right depending on when they cross the green diagonal ( each path crosses it exactly once).