# Math Help - Hard proof.

1. ## Hard proof.

Prove the following identity:

(m choose k) = sum from k = 0 to n of (n choose k) (m - n choose n - k).

Thanks.

2. Originally Posted by cgiulz
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 $\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.