combinatorics - Find a combinatorial proof for $binom{n+1}{k} = binom{n}{k} + binom{n-1}{k-1} + ... + binom{n-k}{0}$

Let $n$ and $k$ be integers with $n \geq k \geq 0$. Find a combinatorial proof for

$$\binom{n+1}{k} = \binom{n}{k} + \binom{n-1}{k-1} + \cdots + \binom{n-k}{0} .$$

My approach:
I was thinking to use the binomial formula as in $$2^n = \sum{\binom{n}{k}1^k1^{n-k}} .$$
I also tried to use Pascal's Identity $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$.

Answer

I think you can try to interpret this identity using the following real-life problem:

Imagine you have a plate of $n+1$ treats: $k$ of them are chocolate pieces, and the rest are Brussels sprouts. In how many ways can you eat all of them, one by one? Assume the chocolate pieces are indistinguishable from each other, and so are Brussels sprouts.

The answer is, of course, $\binom{n+1}{k}$. However, let's count differently, depending on what you eat first:

• You bravely go straight on to a Brussels sprout, before eating any chocolate. There are $\binom{n}{k}$ ways to do that, as there will be $n$ treats left and $k$ of them are chocolate pieces;


• You first eat one piece of chocolate, and then go on to eating a Brussels sprout: there are $\binom{n-1}{k-1}$ ways to do that, as there will be $n-1$ treats left, $k-1$ of them chocolate;


• You first eat two pieces of chocolate, then go on to a Brussels sprout: similarly, it can be done in $\binom{n-2}{k-2}$ ways;


• You first eat three pieces of chocolate...

etc. until:

• You eat $k-1$ chocolate pieces first, then one Brussels sprout. Then, only one of the remaining $n-(k-1)$ treats is a chocolate, and the number of ways to do that is $\binom{n-(k-1)}{1}$;


• You eat all the chocolate pieces first, and then you eat all of the Brussels sprouts: it can be done in only one way, which can also be written as $1=\binom{n-k}{0}$.

Generally, if you eat first $m$ pieces of chocolate ($0\le m \le k$) before getting on with your first Brussels sprout, there are $\binom{n-m}{k-m}$ ways to do it: after eating the initial chocolate pieces and the Brussels sprout, there will be $n-m$ treats left on the plate, $k-m$ of them being chocolate, so you can eat them in $\binom{n-m}{k-m}$ ways.

Altogether all those numbers must add to our original result $\binom{n+1}{k}$, i.e.

$$\binom{n+1}{k}=\binom{n}{k}+\binom{n-1}{k-1}+\binom{n-2}{k-2}+\cdots+\binom{n-(k-1)}{1}+\binom{n-k}{0}=\sum_{m=0}^k\binom{n-m}{k-m}$$