2
$\begingroup$

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?

  • 0
    Yes, it is the Chu-Vandermonde identity.2012-10-29

2 Answers 2

1

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!

0

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

  • 0
    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.2012-07-17