Prove combinatorial Identity using a combinatorial argument.

Question

I have proved by induction on k that : $$ \binom{n}{n} + \binom{n+1}{n} + \binom{n+2}{n}+ ... + \binom{n+k}{n} = \binom{n+k+1}{n+1} $$

But now, I need to prove it using a combinatorial argument. Could someone give me a hint ? :/

Thank you !

Answer 1

We have $n+k+1$ different-flavoured doughnuts. We want to choose $n+1$ of them for a healthy breakfast, saving the remaining $k$ for lunch. The number of ways to do this is clearly $\binom{n+k+1}{n+1}$.

We count the number of choices in another way. Line up the doughnuts in a row.

Suppose that our choice includes the first doughnut on the left. Then there are $\binom{n+k}{n}$ ways to choose the others.

Suppose that our choice does not include the first doughnut on the left, but does include the second one. Then there are $\binom{n+k-1}{n}$ ways to choose the others.

Suppose that our choice does not include either of the first two, but does include the third one. Then there are $\binom{n+k-2}{n}$ ways to choose the others.

And so on. Finally, if the choice does not include any of the first $k$ doughnuts, but includes the $(k+1)$-th ,we must use all the rest, and there are $\binom{n}{n}$ ways to do it.

Add up. We get (backwards) the sum on the left.