1
$\begingroup$

This question already has an answer here:

How can I prove that $\sum_{i=0}^n\binom{n}{i}^2 =\binom{2n}{n}$

Thanks in advance!

$\endgroup$

marked as duplicate by Semiclassical, Arthur, Yujie Zha, Dhruv Kohli - expiTTp1z0, carmichael561 Jul 10 '17 at 17:28

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.

3
$\begingroup$

Consider $n$ girls and $n$ boys. We want to choose a n-person from them to make a team. We will prove the statement by double-counting this amount.



Clearly we have $C(n,2n)$ choices.



On the other hand we can assume that there are $i$ boys in the team, where $0 \leq n$, choose $i$ arbitrary but fix it, we have $C(i,n)$ choices for chosing boys, and $C(n-i,n)$ choices for chosing girls, so we have:

$C(n,2n) = \sum_{i=0}^n C(i,n)C(n-i,n)$,

but notice that we have $C(i,n)=C(n-i,n)$. So the disired equality holds:

$C(n,2n) = \sum_{i=0}^n C(i,n)C(i,n)$.

$\endgroup$
  • $\begingroup$ I can't seem to get why it is sum of choosing i boys out of n multiplied by n-i girls. $\endgroup$ – Nikola Jul 10 '17 at 19:54
  • 1
    $\begingroup$ Every team you have choosen, it may contains exactly $0$ boys, or it may contains exactly $1$ boys, or it may contains exactly $2$ boys,...., or it may contains exactly $n-1$ boys, or it may contains exactly $n$ boys. $\endgroup$ – Davood Khajehpour Jul 10 '17 at 19:58
  • $\begingroup$ In any of the above cases, respectively; we have exactly $n$ girls in the team, or exactly $n-1$ girls in the team, or exactly $n-2$ girls in the team, ..., or exactly $1$ girls in the team, or exactly $0$ girls in the team. $\endgroup$ – Davood Khajehpour Jul 10 '17 at 20:02
  • 1
    $\begingroup$ Aha, I think I get it now. It's like a further partitioning to boys and girls, but the ways it can become are many, so I guess we are using rule of sum here. $\endgroup$ – Nikola Jul 10 '17 at 20:39
1
$\begingroup$

Rewrite one $\binom{n}{i}$ factor as $\binom{n}{n-i}$, then note both sides count ways to choose $n$ elements from a set of size $2n$.

$\endgroup$

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