# Prove the following combinatorial identity:

+1 vote
148 views
reshown Apr 21, 2016

How do I prove the following?

$$\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}^2 = \begin{pmatrix} 2n \\ n \end{pmatrix}$$

+1 vote
answered Apr 21, 2016 by (4,220 points)
selected Apr 22, 2016 by Luke

$$\sum_{r=0}^{2n}\binom{2n}{r}x^r = (1+x)^{2n} = (1+x)^n(1+x)^n$$
$$= [\sum_{k=0}^n \binom{n}{k}x^k]^2 = \sum_{k=0}^n \sum_{l = 0}^{n}\binom{n}{k} \binom{n}{l} x^{k+l}$$

Now this all seems very unrelated to the issue. But by equating the coefficients of $$x^r$$ you can notice that: $$\binom{2n}{r} = \sum_{0 \le k,l \le n \ : \ k+l = r} \binom{n}{k} \binom{n}{l} = \sum_{k=0}^n \binom{n}{k} \binom{n}{r-k}$$
In the case where $$r=n$$,
$$\binom{2n}{n} \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k}=\sum_{k=0}^n \binom{n}{k} \binom{n}{k}$$

There is also a 'wordier' proof: Suppose there are $$2n$$ members of parliament and exactly half belong to party $$A$$ and half belong to party $$B$$. How many ways are there to select a cabinet of $$r$$ ministers? The answer is $$\binom{2n}{r}$$. We can also arrive at this answer by considering the number of possibilities with the added constraint that $$k$$ (out of $$r$$) ministers come from party $$A$$, and then summing over $$k$$:
$$\sum_{k=0}^r \binom{n}{k} \binom{n}{r-k} = \binom{2n}{r}$$
answered Apr 21, 2016 by (1,620 points)

First, notice that  $$\binom{n}{k} = \binom{n}{n-k}$$.

Using this identity one can rewrite the LHS as $$\sum_{k=0}^n \binom{n}{k}^2 = \sum_{k=0}^n \binom{n}{k}\binom{n}{n-k}$$

Now $$\bf{Vandermonde's Theorem}$$ states that $$\sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$ where $$m,n,r \in \mathbb{N_0}$$

Applying this to $$\sum_{k=0}^n \binom{n}{k}\binom{n}{n-k}$$ results in

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

commented Apr 21, 2016 by (1,620 points)

Not sure why the hyperlink isn't working properly, since it works in the 'Preview' of my answer, so here it is: https://en.wikipedia.org/wiki/Vandermonde%27s_identity