Problem: (AIME) Consider all 1000 -element subsets of the set $\{1,2,3, \ldots, 2015\}$. From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$. Solution: First, the number of $1000$ element subsets of $\{1,2,3, \ldots, 2015\}$ is just ${2015 \choose 1000}$, so the denominator of the mean is ${2015 \choose 1000}$. Now, for the numerator, say the minimum element of our $1000$-element subset is $k$ for some $k$ such that $1 \leq k \leq 1016$. Then, we see that there are $2015-k$ elements to choose the rest of the $999$ elements from so the numerator of the mean is just $\sum_{k=1}^{1016}k{2015-k \choose 999}$. Now this is the hard part. How do we evaluate this? I'll present two ways. First, notice that this is very close to the hockey stick identity which states $\sum_{k = 0}^n{a + k \choose a} = {a+n +1 \choose a+1}$, so in our case we have $\sum_{k=1}^{1016}{2015-k \choose 999} = \sum_{k=1}^{1016}{998 + k \choose 999} = {2015 \choose 1000}$. However, we can break $\sum_{k=1}^{1016}k{2015-k \choose 999}$ into a bunch of binomial coefficient sums that reduce using this identity. In particular, we find that $1 \cdot\binom{2014}{999}+2 \cdot\binom{2013}{999}+3 \cdot\binom{2012}{999}+\cdots+1016 \cdot\binom{999}{999}$ is just $ \begin{gathered} \binom{2014}{999}+\binom{2013}{999}+\binom{2012}{999}+\binom{2011}{999}+\cdots+\binom{999}{999} \\ \binom{2013}{999}+\binom{2012}{999}+\binom{2011}{999}+\cdots+\binom{999}{999} \\ \binom{2012}{999}+\binom{2011}{999}+\cdots+\binom{999}{999} \\ \ddots \\ \binom{999}{999} . \end{gathered} $ Therefore, the numerator is equal to $ \binom{2015}{1000}+\binom{2014}{1000}+\cdots+\binom{1000}{1000} $ which is itself another hockey stick, and yields $\binom{2016}{1001}$. Thus the desired average is $\frac{{2016 \choose 1001}}{{2015 \choose 1000}} = \frac{2016}{1001}=\frac{288}{143} \implies p+q = 431$. Alternate: Another way to reduce $\sum_{k=1}^{1016}k{2015-k \choose 999}$ is via double counting (taking a step back to make two steps forward). Recall that $\sum_{k=1}^{1016}k{2015-k \choose 999}$ counts the number of subsets $A \subseteq \{1,2,3, \ldots, 2015\}$ for which $|A| = 1000$ and $\min A \in \{ 1,2,3,\dots, 1016 \}$. Let $\{ x_{1},x_{2},x_{3},\dots,x_{1000} \} \subseteq A$ with $x_{1} < x_{2} < \dots < x_{1000}$. Now consider $\{ x_{1}+1,x_{2}+1,x_{3}+1, \dots, x_{1000}+1 \} \subseteq \{ 2, 3,4\dots, 2016 \}$. Notice that there are $x_{1}$ ways to choose some $k$ such that $k < x_{1}+1$. In particular, say we choose $x_{1}$ to be the least element of a set $\{ x_{1},x_{2},x_{3},\dots,x_{1000} \}$ (there would have been $x_{1} {2015-x_{1} \choose 999}$ ways to do this). This also counts the numbers of ways to form a subset of $\{ 1,2, \dots, 2016 \}$ that includes $x_{1}+1$ and has only one element less than $x_{1}+1$ (there are ${2016 - (x_{1}+1) \choose 999} = {2015 -x_{1} \choose 999}$ ways to do pick the elements greater than $x_{1}+{1}$ and there are $x_{1}$ ways to select the element smaller than $x_{1}$). All of that is to say $x_{1} {2015-x_{1} \choose 999}$ counts the number of $1001$ element subsets of $\{ 1,2, \dots, 2016 \}$ where $x_{1}+1$ is the second smallest element for a fixed $x_{1}$. But this is just the same as counting all 1001-element subsets of $\{ 1,2,\dots, 2016 \}$. This means $\sum_{k=1}^{1016}k{2015-k \choose 999} = {2016 \choose 1001}$. The answer follows as before.