# Combinatorial approach to a binomial sum identity?

So I'm trying to prove the following:

$$\sum\limits_{k=0}^{n} {k \choose a} {n-k \choose b} = {n+1 \choose a+b+1}$$

And I'm a little caught on how to get started. It doesn't seem like a straightforward manipulation of the binomial theorem, so I was wondering if there was a nice way to visualize this in a combinatorial way -- i.e. I see that we'd be multiplying the ways of finding a subset of size a from a set of size $k$ and the ways of finding a subset of size $b$ from a set of size $n-k$, and this should equal the ways of finding a subset of size $a+b+1$ from a set of size $n+1$. I was wondering if this type of story could be extended to prove this, or if another approach was more advantageous.

This is a homework problem, tried to put as much of my thought process down as possible.

Suppose you have $n + 1$ positions and $a + b + 1$ markers. Put one marker in the $(k+1)^{\text{st}}$ position and place $a$ markers to the left and $b$ markers to the right (with no two markers occupying the same position). How many ways are there of doing this?
• k is arbitrary so we'd have to do it for each k. But fixing one, you'd have (trying not to look at the left side as much as possible, I swear) $k \choose a$ markers (assuming you had a typo) times $n-k \choose b$ markers. – Schwinger Sep 23 '14 at 4:05
• Not $\binom{k}{a}$ markers, but $\binom{k}{a}$ ways of choosing the $a$ markers. Can you see how this helps? – Michael Albanese Sep 23 '14 at 4:09