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".

  • 1
    $\begingroup$ 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? $\endgroup$ – Martin Jan 29 '13 at 12:23
  • $\begingroup$ 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. $\endgroup$ – Sarah Jan 29 '13 at 12:37
  • $\begingroup$ It looks like a homework problem. $\endgroup$ – Joe Z. Jan 30 '13 at 3:51
  • $\begingroup$ @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. $\endgroup$ – robjohn Feb 4 '13 at 2:09

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


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.

  • $\begingroup$ @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. $\endgroup$ – mrf Jan 29 '13 at 13:43
  • $\begingroup$ Yes for sure! But how do I upvote? $\endgroup$ – Sarah Jan 29 '13 at 13:47
  • $\begingroup$ @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. $\endgroup$ – mrf Jan 29 '13 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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