Welcome to the hotseat. We've prepared a guide if you'd like to read more about how it works.

Prove the following combinatorial identity:

+1 vote
asked Apr 21, 2016 in Calculus and Pure Mathematics by Luke (350 points)
reshown Apr 21, 2016 by Luke

How do I prove the following?

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

2 Answers

+1 vote
answered Apr 21, 2016 by simon_rigby (4,220 points)
selected Apr 22, 2016 by Luke
Best answer
$$\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}$$
0 votes
answered Apr 21, 2016 by Pandy (1,530 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 Pandy (1,530 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