2
$\begingroup$

This question already has an answer here:

I need to simplify this thing: $$\sum_{k=0}^n{n\choose k}^2$$
I spent more than an hour thinking about it and the set of working solutions that sprang to my mind was unfortunately still empty. Then, I resorted to a book and came across this formula - the "Cauchy identity": $${m+n \choose k} = \sum_{s=0}^k{m \choose s}{n \choose k-s}$$ This already rang a bell - I return to the previous problem:
$$\sum_{k=0}^n{n \choose k}^2 = \sum_{k = 0}^n {n\choose k}{n \choose n-k}$$ Now, I assumed that $m=n$ (There was no restriction in the identity) and that $s=n$ again, no restriction.
Therefore, I got this simplification, being simultaneously my final answer:
$${2n \choose n}$$
Do you think that this solution works? If so, I am not trying to conceal the fact that I find this solution very unnatural and I would have never solved it were it not for the book. Is there a simpler way to do this? Maybe something on the combinatorial level?

$\endgroup$

marked as duplicate by José Carlos Santos, TheSimpliFire, gt6989b, Lord Shark the Unknown, A. Salguero-Alarcón Feb 23 '18 at 19:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Well you've got a hypothesis. If you want to be sure, why not plug in a few values and if everything seems correct, prove it with induction? $\endgroup$ – Mastrem Feb 23 '18 at 18:32
  • 1
    $\begingroup$ I thought that identiy was named after Vandermonde, ranther than Cauchy. $\endgroup$ – user228113 Feb 23 '18 at 18:35
  • 1
    $\begingroup$ @José Carlos Santos Sorry, where do you see an inductive proof, here? $\endgroup$ – Professor Vector Feb 23 '18 at 18:36
  • $\begingroup$ @ProfessorVector I don't. It is still an anawer to the question that was posted here. $\endgroup$ – José Carlos Santos Feb 23 '18 at 18:38
  • $\begingroup$ @JoséCarlosSantos I don't think that the thread you picked as a possible duplicate solves my problem. First of all, I got the expression ${2n \choose n}$ by coincidence. I am not supposed to prove it - I need to work the other way around. $\endgroup$ – Aemilius Feb 23 '18 at 18:41
3
$\begingroup$

A combinatorical proof could be like this:

Assume you have $2n$ balls and you want to choose $n$ of them. One way is straight-forward choosing $n$ from $2n$ by $\binom{2n}{n}$ ways

Also you can group them in 2 n-groups and choose k from the first one and n-k from the second one which gives us $\sum \binom{n}{k}\binom{n}{n-k}$ but since $\binom{n}{k}=\binom{n}{n-k}$ you could also write it as following: $$\sum \binom{n}{k}\binom{n}{n-k} = \sum \binom{n}{k}\binom{n}{k} = \sum \binom{n}{k}^2$$

So overall we have

$$ \binom{2n}{n} = \sum \binom{n}{k}^2 $$

$\endgroup$
1
$\begingroup$

Consider $(1+x)^{n} \cdot (1+x)^{n} = (1+x)^{2n}$. Now what is the coefficient before $x^{n}$?

$\endgroup$
  • $\begingroup$ Sorry, but I don't see what you are aiming at with your hint. Why did you multiply these two binomials? In the original problem, the thing that is being squared is the coefficient, not the entire sum. $\endgroup$ – Aemilius Feb 23 '18 at 19:25

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