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.

How to prove this combinatorial summation?

enter image description here

I expanded $C(m, i)$ and $C(n-1, n-i)$ and clubbed them together but it didn't yield anything useful. Please show me the approach only.

Is this the Chu-Vandermonde identity?

share|improve this question
    
I don't understand your notation. –  user29999 Jul 17 '12 at 15:29
    
Yes, it is the Chu-Vandermonde identity. –  Phira Oct 29 '12 at 21:10
add comment

2 Answers 2

Write in words what this means.

You have two collections. One of $m$ objects and another of $n$ objects. When you choose $n$ objects totally, then you would've chosen, say $i$ objects from the first $m$ and hence $n-i$ from the remaining $n-1$ elements.

Similarly choosing $i$ from the first $m$ and $n-i$ from the remaining $n-1$ gives a way of choosing $n$ objects totally!

share|improve this answer
add comment

The idea is the following: $C(m+n-1, n)$ is the number of ways to choose $n$ items from $m+n-1$ items. Well, you can do this by first picking $i$ items out of the first $m$ items ($C(m,i)$ ways to do this) and then choose $n-i$ items out of the remaining $n-1$ items. But of course $i$ could be anything between $1$ and $n$ (which leads me to think there is a typo in your question at the moment).

share|improve this answer
    
Oh, also, I didn't know what the Chu-Vandermonde identity was until you mentioned it. I believe (based on the Wikipedia article) that this is the Vandermonde identity. –  Aru Ray Jul 17 '12 at 15:34
add comment

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.