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

Question

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.

Answer 1

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\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}

Answer 2

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.