Exploring the Relationship Between Combinatorics and Choosing Committees

[davemoosehead]

Homework Statement

$${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.

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.

 

[tiny-tim]

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

Hi davemoosehead!

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?

 

[davemoosehead]

Hi davemoosehead!

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?

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?

 

[tiny-tim]

Yes …

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

 

[davemoosehead]

Yes …

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

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}$$

 

[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)?

 

[davemoosehead]

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)?

If the first 6 are not selected, then you would have (n+r+1-6 C n+1) ?

I'm having a hard time following what you are saying.

 

[tiny-tim]

If the first 6 are not selected, then you would have (n+r+1-6 C n+1) ?

Yes, but if the first one selected is number 7 (ie the previous 6 are not selected)?