How Can We Prove This Combinatorial Identity?

[Pietjuh]

Hello everyone!

I'm trying to prove the following identity, but I'm not very lucky in finding the proof:

$${{n+k-1}\choose{n-1}} = \sum_{i=1}^k {k-1\choose i-1}{n\choose i}\,\, 1\leq k \leq n$$

I've tried to interpret this as a combinatorial problem, and I know the left hand side is the number of k-repeatingcombinations (don't really know the english word for it. The dutch word is k-herhalingscombinaties). But how i can transfer this to the sum on the right hand side...

Can someone help me a bit with this?

 

[matt grime]

Do it by inductiom, although there is an obvious combinatorial interpretation:

consider a set of n+k-1 objects partitioned as

1,2,..,n | n+1,...,n+k-1

how many ways are there of picking n-1 things from this?

we can pick r fromthe k-1 on the right of the partition and n-1 -r from the ones one the left, thus

$$\binom{n+k-1}{n-1} = \sum_{r=0}^{k-1} \binom{k-1}{r}\binom{n}{n-1-r}$$

just reclall that choosing n-1-r from n is the same as choosing r+1 and nor shift the summation so it is indexed by i from 1 to k not r from 0 to k-1

 

[Gokul43201]

LHS = C(n+k-1,n-1) = C(n+k-1,k) {using the identity C(n,k) = C(n, n-k)}

This is simply the number of ways of choosing k objects out of n+k-1 objects.

Find an alternative way of doing this same thing. For instance, consider the collection of objects to be consisting of 2 piles. One pile has n objects and the other pile has k-1 objects. Pick up some i objects from the first pile and the remaining k-i objects from the second pile. Calculate the number of ways of doing this and you will see that this is merely a term on the RHS. Sum through all values of i to generate the complete RHS.

Edit : Just saw matt's post...and this is essentially doing the same thing. If you wish read through both and see how they are equivalent.