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.

Please provide a combinatorial proof for the following:

Prove the identity $$\sum_{i=0}^{k}{m+k-i-1 \choose k-i}{n+i-1 \choose i}={m+n+k-1 \choose k}$$

Hint: use idea of "selection with repetition".

share|improve this question
1  
Do you mean $$\sum_{i=0}^k\binom{m+k-i-1}{k-i}\binom{n+i-1}{i}=\binom{m+n+k-1}{k}\quad?$$ What did you try to do? –  Martin Jan 29 '13 at 12:23
    
Yes I that's the question. For the R.S I said that its counts the no. of ways to select k objects from m+n objects with repetition, but am not sure how to interpret the summation side. –  Sarah Jan 29 '13 at 12:37
    
It looks like a homework problem. –  Joe Z. Jan 30 '13 at 3:51
    
@JoeZeng: or an exercise in a book. It's hard to second guess. In cases like this, without further information, we usually accept what the author says. –  robjohn Feb 4 '13 at 2:09

1 Answer 1

up vote 5 down vote accepted

Imagine you have $m$ red objects and $n$ blue objects, and you want to select $k$ objects with possible repetitions. This can be done (as you stated yourself in the comment) in

$$\binom{m+n+k-1}{k}$$

different ways.

On the other hand, among these $k$ selected objects, there could be exactly $k$ red ones and $0$ blue ones, there could be $k-1$ red and $1$ blue, etc. Each of these cases are mutually exclusive, and there are

$$\binom{m+(k-i)-1}{k-i} \binom{n+i-1}{i}$$

ways to choose exactly $k-i$ red objects and $i$ blue objects. Sum over all $i$ and you get your identity.

share|improve this answer
    
thank you for your help! –  Sarah Jan 29 '13 at 13:39
    
@Sarah: You're welcome! And since you're new here, don't forget to upvote answers and questions you find useful (and not just answers to your own questions). If you're really happy with a particular answer, you can "accept" it, but it's usually a good idea to wait awhile before doing that -- even better answers can appear later. –  mrf Jan 29 '13 at 13:43
    
Yes for sure! But how do I upvote? –  Sarah Jan 29 '13 at 13:47
    
@Sarah: Look at the grey arrows in the left column. Clicking the up-arrow gives an upvote, and likewise, the down-arrow gives a downvote. The number attached to each post is the difference between upvotes and downvotes. –  mrf Jan 29 '13 at 13:49

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.