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 2 of 6: Write the weighted sum explicitly

Previous step Next step

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

Detailed analysis

Multiplying the count from Step 1 by $j$ and summing over $j=1,\dots,n-r+1$ gives the total of all least elements, written out as a triangular sum of binomial coefficients.