# Show that $\sum_{k=0}^n \frac{(2n)!}{{k!^2(n-k)!}^2}= \binom{2n}{n}^2$

Show that $$\sum_{k=0}^n \frac{(2n)!}{k!^2(n-k)!^2} = \binom{2n}{n}^2.$$

I tried canceling $2n!$ from both sides then moving $k!$ to right but still not sure how to proceed.


Note that \begin{align} {2n \choose n} &= \bracks{x^{n}}\pars{1 + x}^{2n} = \bracks{x^{n}}\braces{\pars{1 + x}^{n}\pars{1 + x}^{n}} \\[3mm] & = \bracks{x^{n}}\sum_{k = 0}^{n}\,\sum_{k' = 0}^{n}{n \choose k} {n \choose n - k'}x^{k + k'} = \sum_{k = 0}^{n}{n \choose k}{n \choose n - k} \end{align}

• +1. I think it would be better as an underbrace, not an overbrace :) – 6005 Jul 16 '16 at 18:38
• @6005 Done. Thanks. – Felix Marin Jul 16 '16 at 18:42
• Thanks for the help! I've been trying the wrong steps. Great Job! – bob Jul 16 '16 at 18:46
• @jim Glad to be helpful. Thanks. – Felix Marin Jul 16 '16 at 18:47
• Also, to show that $\sum_{k=0}^n \binom{n}{k}^2 =\binom{2n}{n}$, we can look at $(1+x)^n(1+x)^n = (1+x)^{2n}$. The coefficient of $x^n$ in the left-hand side is $\sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} = \sum_{k=0}^n \binom{n}{k}^2$ and the coefficient of $x^n$ in the right-hand side is $\binom{2n}{n}$. – user19405892 Jul 16 '16 at 18:48

For a combinatorial approach, the right-hand side counts ways of splitting $2n$ people into two groups of size $n$, twice; i.e., we assign half of the group $0$ and half of them $1$, and we assign half of them $a$ and half of them $b$. All together, each person now is labeled either '$0a$', '$0b$', '$1a$', or '$1b$'.

On the left-hand side, the $k$th term is $\binom{2n}{k,k,n-k,n-k}$: it counts the number of ways to split $2n$ people into $k$ people with '$0a$', $k$ people with '$1b$', $n-k$ people with '$0b$', and $n-k$ people with '$1a$'. This is summed up over all possible $k$.

Note that no matter how the $2n$ people are assigned into halves of $0/1$ and $a/b$ on the right-hand side, there will be the same number of '$0a$'s as '$1b$'s. Thus this will correspond to some $k$ term on the left-hand side, so the two counts are the same, and so the equality is proved.

• I have no idea why this answer was downvoted: it’s an excellent answer. – Brian M. Scott Jul 16 '16 at 19:46
• @BrianM.Scott Thank you. Probably someone who either has not heard of combinatorial proofs or does not understand how it constitutes a proof. – 6005 Jul 17 '16 at 0:00