# Combinatorial proof for a non obvious binomial identity

I think I got some serious problem with those combinatorial proofs. Why would the following be true ($1\leq r\leq k\leq n$):

$$\sum_\limits{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}?$$

It doesn't make sense to me. We could choose $r$-th element of our set and choose from lesser and greater elements but this is not what this formula gives.

There are of course $\binom{n}k$ ways to choose $k$ elements from the set $[n]=\{1,\ldots,n\}$. Now let’s count them in a different way. How many ways are there to choose a set $S$ of $k$ elements of $[n]$ so that $j$ is the $r$-th smallest element of the set?

• There are $j-1$ elements of $[n]$ less than $j$, so we have to choose $r-1$ of them to be the $r-1$ elements of $S$ that are less than $j$. We can do that in $\binom{j-1}{r-1}$ ways.

• There will be $k-r$ elements of $S$ that are bigger than $j$, and they must come from the $n-j$ elements of $[n]$ that are bigger than $j$, so there are $\binom{n-j}{k-r}$ ways to choose them.

Thus, there are

$$\binom{j-1}{r-1}\binom{n-j}{k-r}$$

ways to choose a $k$-element subset of $[n]$ whose $r$-th smallest element is $j$. Now just sum over the possible values of $j$ to get the identity.

• $r$-th smallest, ok, that absolutely makes sense. Why didn't I see this? Man, I hope it'll come to me one day. – Jules Jun 20 '16 at 22:45
• @Jules: Give it time: my experience has been that the more combinatorial arguments I see, the easier it is to come up with new ones. Some ideas just keep cropping up, and one gets a feel for where they might be useful. – Brian M. Scott Jun 20 '16 at 22:47
• Yup, that's called expert's knowledge in psychology, right :) Thank you for your help! – Jules Jun 20 '16 at 22:49
• @Jules: You’re welcome! – Brian M. Scott Jun 20 '16 at 22:49