Combinatorics: please proof (nCn)^2+(nC1)^2+...+(nCn)^2=2nCn

aw3som3 said:
please proof (nCn)^2+(nC1)^2+...+(nCn)^2=2nCn
Click to expand...
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!
 
Last edited:
You must log in or register to reply here.
Top