1. ## Binomial coefficient

I want to proof

$\displaystyle \sum_{i=0}^{k}\left(\begin{array}{cc}m\\i\end{arra y}\right)\left(\begin{array}{cc}{n}\\{k-i}\end{array}\right)=\left(\begin{array}{cc}{m+n}\ \k\end{array}\right)$

Can anyone help?

2. Originally Posted by bram kierkels
$\displaystyle \sum_{i=0}^{k}\left(\begin{array}{cc}m\\i\end{arra y}\right)\left(\begin{array}{cc}{n}\\{k-i}\end{array}\right)=\left(\begin{array}{cc}{m+n}\ \k\end{array}\right)$
Clearly $\displaystyle 0\le k\le m+n$.
$\displaystyle \binom{m+n}{k}$ is the number of ways to select $\displaystyle k$ items from a set of $\displaystyle m+n$ items.
Let $\displaystyle A = \left\{ {1,2, \cdots ,m + n} \right\},\;B = \left\{ {1,2, \cdots ,k} \right\}\,\& \,C = A\backslash B$.
Can you see the sum as selecting $\displaystyle i$ items from $\displaystyle B$ and $\displaystyle k-i$ items from $\displaystyle C$?

3. Originally Posted by Plato
Clearly $\displaystyle 0\le k\le m+n$.
$\displaystyle \binom{m+n}{k}$ is the number of ways to select $\displaystyle k$ items from a set of $\displaystyle m+n$ items.
Let $\displaystyle A = \left\{ {1,2, \cdots ,m + n} \right\},\;B = \left\{ {1,2, \cdots ,k} \right\}\,\& \,C = A\backslash B$.
Can you see the sum as selecting $\displaystyle i$ items from $\displaystyle B$ and $\displaystyle k-i$ items from $\displaystyle C$?
I see what you mean. But shouldn't B have m elements? So that $\displaystyle B = \left\{ {1,2, \cdots ,m}\right\}$ and $\displaystyle C=A\backslash B$ becomes $\displaystyle \left\{ {m+1,m+2, \cdots ,m+n} \right\}$

4. Originally Posted by bram kierkels
So that $\displaystyle B = \left\{ {1,2, \cdots ,m}\right\}$
No that will not work,
What happens if $\displaystyle k>m$?
That gives an error in the summation.