How do I prove the following?

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

Login

+1 vote

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

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}$$

- All categories
- BUS 1003H - Introduction to Financial Risk (30)
- BUS 2016H - Financial Mathematics (33)
- BUS 3018F - Models (40)
- BUS 3024S - Contingencies (11)
- BUS 4028F - Financial Economics (12)
- BUS 4027W - Actuarial Risk Management (1)
- BUS 2029H - Research Project (2)
- Mphil (1)
- Calculus and Pure Mathematics (3)
- Statistics (10)

...

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