combinatorics - Prove ${{n+1} choose {m+1}} = sum_{k=m}^{n}{k choose m}$ using a purely combinatorial argument.

Prove ${{n+1} \choose {m+1}} = \sum_{k=m}^{n}{k \choose m}$ using a purely combinatorial argument.

I don't think I understand how to do a combinatorial proof. I know the left side expands to:

$${{n+1} \choose {m+1}} = \frac{(n+1)!}{(m+1)!(n+1-m-1)!} = \frac{(n+1)!}{(m+1)!(n-m)!}$$

For the right side:

$$\sum_{k=m}^{n}{k \choose m} = {{k+1} \choose {m+1}} = \frac{(k+1)!}{(m+1)!(k+1-m-1)!} = \frac{(k+1)!}{(m+1)!(k-m)!}$$

Which is similar to what I got on the top.

Where do I go from here?

Answer

What you have started there would be an algebraic, rather than a combinatorial argument.

In a typical "combinatorial" argument we look at some set of things, and count the number of element in it in two different ways, yielding two different expressions for the result. Since it is the same things being counted, we now know that the two different expressions have the same value.

In this particular case, it is natural to look at "how many $(m+1)$-element subsets of $\{1,2,3,\ldots,n,n+1\}$ are there?", since that is one definition of the left-hand side $\binom{n+1}{m+1}$. We'd then try to come up with a different way to count those $(m+1)$-element subsets that naturally leads us to conclude that there must be $\sum_{k=m}^{n}\binom km$ of them.

Hint. Consider grouping the subsets according to what the largest element of each subset is.