Proof with combinatorial argument for $\binom{n}{k+1} = \binom{n-1}k+ \binom{n-2}k +...+ \binom{k}k$

Question

Show with combinatorial argument that this is equal :

$$\dbinom{n}{k+1} = \dbinom{n-1}{k}+ \dbinom{n-2}{k} +...+ \dbinom{k}{k}$$

I have no idea how to do that so it would be really helpful if anyone knows some way.

Answer 1

Suppose we want to distribute $n - k - 1$ identical balls into $k + 2$ distinct boxes. With stars and bars, there are $\binom{n - k - 1 + k + 1}{k + 1} = \binom{n}{k + 1}$ ways to do this.

We can also first distribute $0 \le i \le n - k - 1$ balls into the first box and then distribute remaining the balls into the remaining $k + 1$ boxes. The number of ways to do this is, using stars and bars for the remaining balls and boxes, is

$$\binom{(n - k - 1) + k}{k} + \binom{(n - k - 2) + k}{k} + \dots + \binom{(n - k - n) + k}{k}$$ $$= \binom{n - 1}{k} + \binom{n - 2}{k} + \dots + \binom{k}{k}$$

Since both ways of counting are equivalent, we have

$$\binom{n}{k + 1} = \binom{n - 1}{k} + \binom{n - 2}{k} + \dots + \binom{k}{k}$$