Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to prove that $$\sum_{0\le i\le k} \binom{n}{i}.\binom{m}{k-i} = \binom{m+n}{k}.$$ I got the constants $m!$ and $n!$ out of the sum but I couldn't proceed.

share|improve this question
2  
This is Vandermonde's identity; there are several proofs at the Wikipedia page. –  Douglas S. Stones Oct 25 '12 at 21:32
    
@DouglasS.Stones Just what I was looking for. –  user31280 Oct 25 '12 at 21:34
1  
Proof by induction works fine, too. I had to prove this, too. But the algebraic proof on the wikipedia page wasnt my favorite. –  André Oct 25 '12 at 22:16
add comment

3 Answers

up vote 5 down vote accepted

To select $k$ peaces of fruit from $m$ apples and $n$ pears, you can also first select a number $0\le i\le k$ of apples you want, select $i$ aplles and $k-i$ pears.

share|improve this answer
add comment

How can you chose $k$ objects from $m+n$?

You chose some ($i$) from the first $m$ and then chose $k-i$ from the second. And $0 \leq i \leq k$...

share|improve this answer
add comment

Notice that $\binom{m+n}{k}$ is the number of ways of choose $k$ elements between $m+n$ given elements. Then you can think these $m+n$ elements separated in two blocks of $m$ and $n$ elements. So, if you choose
$i$ elements in the block of the $n$ elements and $k-i$ in the block of the $m$ elements, you choose $k$ elements between the $m+n$ given elements.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.