Binomial coefficient

**bram kierkels** · February 7th 2010, 02:17 AM

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?

**Plato** · February 7th 2010, 08:14 AM

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$ ?

**bram kierkels** · February 8th 2010, 01:56 AM

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\}$

**Plato** · February 8th 2010, 06:10 AM

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.

Thread: Binomial coefficient

LinkBack

Thread Tools

Display

Binomial coefficient

Similar Math Help Forum Discussions

Sum with binomial coefficient

binomial coefficient.

Binomial Theorem or Binomial Coefficient

How to do binomial coefficient

Binomial Coefficient

Search Tags