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 5: Encode the sum as a string-counting problem

Previous step Next step

In plain words

A well-chosen bijection turns an awkward weighted sum into a clean count of combinatorial objects.

\text{Consider binary strings of length } n+1 \text{ with exactly } r+1 \text{ ones.}

Detailed analysis

Look at binary strings of length $n+1$ containing exactly $r+1$ ones. For $1 \le k \le n$ , say the second $1$ occurs in position $k+1$ : there are $\binom{k}{1}$ ways to place the single earlier $1$ among the first $k$ positions, and $\binom{n-k}{r-1}$ ways to place the remaining $r-1$ ones after position $k+1$ .