# Thread: Binomial coefficient

1. ## Binomial coefficient

I want to proof

$\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
$\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 $0\le k\le m+n$.
$\binom{m+n}{k}$ is the number of ways to select $k$ items from a set of $m+n$ items.
Let $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 $i$ items from $B$ and $k-i$ items from $C$?

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

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