- #1
davemoosehead
- 26
- 0
Homework Statement
[tex]{n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2}+...+{n+r \choose r} = {n+r+1 \choose r}[/tex]
We have to prove by counting both sides in a different way.
For example, consider [tex]{n \choose 0}^2 + {n \choose 1}^2+...+{n \choose n}^2 = {2n \choose n}[/tex]
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.