How to prove that $\sum_{i=0}^n\binom{n}{i}^2 =\binom{2n}{n}$ [duplicate]

This question already has an answer here:

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

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

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)$.

• I can't seem to get why it is sum of choosing i boys out of n multiplied by n-i girls. – Nikola Jul 10 '17 at 19:54
• 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. – Davood Khajehpour Jul 10 '17 at 19:58
• 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. – Davood Khajehpour Jul 10 '17 at 20:02
• 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. – Nikola Jul 10 '17 at 20:39

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