Problem 2

Let

n

and

r

be integers with

1 \le r \le n

, and consider all

\binom{n}{r}

subsets of

r

elements of the set

\{1,2,\dots,n\}

. Each such subset has a smallest element. Let

F(n,r)

denote the arithmetic mean of these smallest elements. Prove that

F(n,r) = \frac{n+1}{r+1}.

Step 3 of 6: Rearrange into telescoping rows

Previous step Next step

In plain words

Rewriting a weighted sum $\sum j\,a_j$ as a sum of tail sums $\sum_i \sum_{j\ge i} a_j$ is a standard trick that turns weights into repeated ranges, ready for the hockey-stick identity.

\sum_{S}\min(S) = \sum_{i=1}^{n-r+1}\Big(\binom{n-i}{r-1}+\binom{n-i-1}{r-1}+\cdots+\binom{r-1}{r-1}\Big)

Detailed analysis

Reading the triangular sum by columns instead of terms, the weight $j$ on $\binom{n-j}{r-1}$ can be absorbed by writing the same binomial coefficient once for each $i \le j$ , producing $n-r+1$ inner sums, each a run of consecutive binomial coefficients with the same lower index $r-1$ .