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 6: Count subsets with a fixed minimum

Previous step Next step

In plain words

This mirrors Step 1 of Solution 1 but sets up a different summation strategy afterward.

\#\{S : \min S = j\} = \binom{n-j}{r-1}, \quad j=1,\dots,n-r+1

Detailed analysis

If $j$ is the least element of an $r$ -subset, the remaining $r-1$ elements come from the $n-j$ numbers larger than $j$ ; there are $\binom{n-j}{r-1}$ ways to choose them.