# 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.

## 2 Answers

$\newcommand{\angles}{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}{\,\mathrm{Li}_{#1}} \newcommand{\ol}{\overline{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}{\underline{#1}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\sum_{k=0}^{n}{(2n)! \over k!^{2}\pars{n - k}!^{2}}} = \sum_{k=0}^{n}{n! \over k!\pars{n - k}!}\,{n! \over k!\pars{n - k}!}\,{\pars{2n}! \over n!\,n!} = {2n \choose n}\ \underbrace{\ \sum_{k = 0}^{n}{n \choose k}^{2}}_{\ds{2n \choose n}\ }\ =\ \color{#f00}{{2n \choose n}^{2}} \end{align}

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