2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1. I think it would be better as an underbrace, not an overbrace :) $\endgroup$ – 6005 Jul 16 '16 at 18:38
  • $\begingroup$ @6005 Done. Thanks. $\endgroup$ – Felix Marin Jul 16 '16 at 18:42
  • $\begingroup$ Thanks for the help! I've been trying the wrong steps. Great Job! $\endgroup$ – bob Jul 16 '16 at 18:46
  • $\begingroup$ @jim Glad to be helpful. Thanks. $\endgroup$ – Felix Marin Jul 16 '16 at 18:47
  • 1
    $\begingroup$ 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}$. $\endgroup$ – user19405892 Jul 16 '16 at 18:48
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.