Combinatorial Proof of Binomial Coefficient Identity, summing over the upper indices 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.
 A: 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$. 
A: 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.
