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 5: Match the two counts

Previous step Next step

\sum_{k=1}^{n} k\binom{n-k}{r-1} = \sum_{k=1}^{n}\binom{k}{1}\binom{n-k}{r-1} = \binom{n+1}{r+1}

Detailed analysis

Summing the string count from Step 2 over all positions $k+1$ of the second $1$ counts every length- $(n+1)$ string with $r+1$ ones exactly once, so the total is $\binom{n+1}{r+1}$ ; but term by term this sum is exactly $\sum_k k\binom{n-k}{r-1}$ from Step 1, since $\binom{k}{1}=k$ .