Proving Combinatorial identity

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
Homework Helper
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

Last edited:
Gokul43201
Staff Emeritus