This is one of the most difficult proofs in elementary combinatorics courses.
It helps to see it written correctly: \(\displaystyle \displaystyle{\sum\limits_{k = 0}^N {\left[\binom{N}{k}\right]^2}=\binom{2N}{N} }\)
The only reasonable proof is a set theorical proof. (I have seen one by induction but it is pages long.)
Here is the trick: think of \(\displaystyle \dbinom{N}{k}^2 \) as \(\displaystyle \dbinom{N}{k}\cdot\dbinom{N}{N-k} \).
Now then let \(\displaystyle P~\&~Q\) as two disjoint sets each containing \(\displaystyle N\) elenents.
So their union \(\displaystyle P\cup Q\) contains \(\displaystyle 2N\) elements.
Any subset \(\displaystyle T\subset P\cup Q\) that contains exactly \(\displaystyle N\) elements must contain \(\displaystyle k\) from \(\displaystyle P\) and \(\displaystyle N-k\) from \(\displaystyle Q\).
\(\displaystyle \binom{2N}{N}\) counts the number of \(\displaystyle N\) of \(\displaystyle N\) element subsets of a set that has \(\displaystyle 2N\) elements.
BUT THEN the sum counts all \(\displaystyle N\) subsets of \(\displaystyle P\cup Q\). DONE!
This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
By continuing to use this site, you are consenting to our use of cookies.