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 1 of 5: Write the total of the smallest elements

Previous step Next step

In plain words

Instead of averaging directly, group subsets by their minimum value and count how many subsets share each possible minimum.

\sum_{S} \min(S) = \sum_{k=1}^{n} k\binom{n-k}{r-1}

Detailed analysis

For a fixed $k$ , the number of $r$ -subsets of $\{1,\dots,n\}$ whose least element equals $k$ is $\binom{n-k}{r-1}$ , since the other $r-1$ elements must be chosen from the $n-k$ numbers exceeding $k$ . Multiplying by $k$ and summing over all possible smallest values gives the sum of the least elements over every $r$ -subset.