# Combinatorial Proof of Binomial Coefficient Identity, summing over the upper indices [duplicate]

Consider the sum $\displaystyle\sum_{j=r}^{n+r-k} \binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}$

I am looking to show this identity combinatorially. Is the general idea perhaps to remove j from n and k from r then pick some 'middle' element, and form a final subset of size r-1? The bounds on the sum are a big roadblock for me.

• This question is a duplicate of several questions, but not of the one that is linked to. That question involves the classical Vandermonde identity, with summation over the lower index. Here the summation is over the upper index, and there are shifts $-1$. Also classical Vandermonde is a polynomial identity in its (fixed) upper indices, this one is not polynomial at all. The two are related, but it is not even easy to see how exactly. And in any case the combinatorial explanations for the two identities are rather different. – Marc van Leeuwen Apr 25 '13 at 13:28
• Here is a question of which this one is a duplicate: math.stackexchange.com/q/326107. Useful answers are also at math.stackexchange.com/questions/73015 and math.stackexchange.com/q/76819. – Marc van Leeuwen Apr 25 '13 at 13:48
• One more hit for a true duplicate: math.stackexchange.com/questions/98495/… – Marc van Leeuwen May 7 '13 at 11:57

Take $n$ objects $1,2,3,\dots, n$, and choose $k$ of them in $\binom{n}{k}$ ways.
Alternatively, suppose the $r$-th largest selection is in position $j$. Then there are $\binom{j-1}{r-1}$ ways to choose the smallest $r-1$ objects and $\binom{n-j}{k-r}$ ways to choose the largest $k-r$ objects.
Now to combine for all possible values the $r$-th selection can be, we have to fit the first $r$ in positions $j$ and under, so $j \geq r$. Similarly, we have to fit the remaininkg $k-r$ in positions $j+1$ through $n$, which gives $k - r \leq n - (j+1) + 1$, or $j \leq n + r - k$.
Classify the $k$-element subsets of $\{1,2,\dots,n\}$ according to their $r$-th element. That element will always be at least $r$ (obviously) and at most $n-(k-r)$ (because there are $k-r$ more elements in the subset after the $r$-th element). If you call the $r$-th element $j$, then $j$ is in the range given for your sum. Furthermore, the factor $\binom{j-1}{r-1}$ counts the possibilities for the $r-1$ elements of your subset that precede the $r$-th element, while the other factor $\binom{n-j}{k-r}$ counts the possibilities for the $k-r$ later elements of your subset.