Prove that $C(r, r) + C(r+1, r) +dotsb+C(n, r) = C(n+1, r+1)$ using combinatoric arguments.

Prove that $C(r, r) + C(r+1, r) +\dotsb+C(n, r) = C(n+1, r+1)$ using combinatoric arguments.

I know we can use an analogy of picking people to form a committee, but I can't see how to prove it.

Answer

We have $n+1$ different doughnuts lined up in a row. In how many ways can we choose $r+1$ of them for breakfast? It can be done in $\binom{n+1}{r+1}$ ways. Now let us count another way.

We could pick the leftmost one, and then choose $r$ from the remaining $n$. This can be done in $\binom{n}{r}$ ways.

Or else we could skip the first, pick the second, and then $r$ from the remaining $n-1$. This can be done in $\binom{n-1}{r}$ ways.

And so on. Finally, we could skip all up to the one $r+1$ from the end, choose it, and then choose $r$ from the remaining $r$. This can be done in $\binom{r}{r}$ ways.

Add up. We get our sum of binomial coefficients, regrettably backwards.

Remark: One could alternately talk about committees. Too bureaucratic for my taste, I have been on too many Department committees.