I'm trying to prove that $$\binom{2n}{n}
=\sum_{i=0}^{n}\binom{n}{i}^2
=\sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}\text{.}$$
Okay, I understand, why $\binom{2n}{n}=\sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}$. For the left-hand side, among $2n$ people, we select $n$ people. On the right-hand side, the committee can consist of $i$ boys and $n-i$ girls, for $i\in\{0,1,2,\dots,n\}$. We select $i$ boys and $n-i$ girls for each $i$.
My Question: I don't understand how $\sum_{i=0}^{n}\binom{n}{i}^2$ is an equivalent expression. I believe $\sum_{i=0}^{n}\binom{n}{i}^2=\sum_{i=0}^{n}\binom{n}{i}\binom{n}{i}$. How does this equate to the two expressions on either side? Can some give me an intuitive/"story-like" explanation (just like what I did above)?
Best Answer
${n \choose i}={n \choose n-i}$ you can prove that by different ways : one of this ways is as follow: the number$ {n \choose i}$ is just the number of all northeastern lattice paths from $ O = (0, 0) $ to P = $(i, n - i)$. Similarly, the number ${n \choose n-i}$ is just the number of all northeastern lattice path from $ O = (0, 0) $ to $P =(n-i, i)$. These two numbers must be the same since reflection through the $x = y $ diagonal .
(i invited you to research about northeastern lattice path .it is simple , but it's powerful tool)
so you can put ${n \choose i}^2={n \choose i}.{n \choose i}={n \choose n-i}{n \choose i}$