Combinatorial Identity

1. Jun 22, 2005

Pietjuh

Can someone help me how to deal with this identity that i must prove?

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

I've tried to figure out what the combinatorial meaning of the right hand side is, but I didn't succeed :(

2. Jun 22, 2005

PhilG

I think it will help to rewrite it in the form:

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