# Homework Help: Combinatorics problem

1. Jan 31, 2010

1. The problem statement, all variables and given/known data

$${n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2}+...+{n+r \choose r} = {n+r+1 \choose r}$$

We have to prove by counting both sides in a different way.

For example, consider $${n \choose 0}^2 + {n \choose 1}^2+...+{n \choose n}^2 = {2n \choose n}$$
The RHS can be described as a way to choose a committee of size n from n women and n men.
Then, the LHS is the number of ways to choose a committee of size n with 0 women and n men + number of ways to choose 1 woman and n-1 men, etc.

3. The attempt at a solution
The confusing part for me on this problem is that the amount you choose from doesn't stay the same. I'm having trouble thinking of a scenario where the pool you choose from increases as you choose more.

One observation I've made is that (for the LHS) the amount you DON'T choose is always the same, n.

2. Jan 31, 2010

### tiny-tim

The RHS is the number of ways of choosing n+1 from n+r+1, and as you say the LHS is different numbers of ways of choosing n …

so where does the extra one come in?

3. Jan 31, 2010

I've been thinking about this all afternoon, and still cannot come up with anything. It's given me a new way of looking at it though which makes it look less intimidating.

So you're saying think of it in terms of what we're not choosing (n+1), rather than what we are choosing (r). So..
$${n \choose n} + {n+1 \choose n} + {n+2 \choose n}+...+{n+r \choose n} = {n+r+1 \choose n+1}$$
would this be equivalent?

4. Jan 31, 2010

### tiny-tim

Yes …

and now concentrate on where the first one (of n+1) is.

5. Jan 31, 2010

If we lined up all the n+r+1 things, the first one of $${n+1 \choose n}$$ would be the one after the last one of $${n+1 \choose 1}$$

6. Feb 1, 2010

### tiny-tim

uhh?

No, I meant eg how many selections are there (of n+1 from n+r+1) in which the first one selected is number 7 (ie the previous 6 are not selected)?

7. Feb 3, 2010