# Homework Help: Binomial identity

1. Dec 4, 2007

### Pietjuh

1. The problem statement, all variables and given/known data
Prove that the following binomial identity holds:

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

3. The attempt at a solution

One of the methods i've tried is to use induction on the variable n, but while trying this I got stuk on rewriting the binomial coefficients.... can someone give me a hint if I can use another simple binomial identity for this?

Another thing I have tried to do is to look at the generating function of the left hand side, and then try to rewrite this to a generating function for the right hand side, but that didn't succeed either....

Can someone point me a little bit in the right direction?

2. Dec 4, 2007

### morphism

Try finding two ways to count the number of ways you can choose k balls from a box containing n red balls and k-1 red balls.

Also note that
$${k-1 \choose i-1} = {k-1 \choose k-i}$$