Prove the following identity:
(m choose k) = sum from k = 0 to n of (n choose k) (m - n choose n - k).
Thanks.
Imagine there are two piles of balls. One has n balls, another one has m-n balls. Now you want to choose k balls from them. So you must decide how many balls you choose from the first pile. Suppose you choose k balls, then there would be $\displaystyle \left(\begin{array}{cc}n\\k\end{array}\right)\left (\begin{array}{cc}m-n\\n-k\end{array}\right)$kinds of method. Then calculate the sum for all the k.