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 4 of 6: Apply the hockey-stick identity to each row

Previous step Next step

\binom{n-i}{r-1}+\binom{n-i-1}{r-1}+\cdots+\binom{r-1}{r-1} = \binom{n-i+1}{r}

Detailed analysis

By the hockey-stick identity $\sum_{k=r-1}^{m}\binom{k}{r-1}=\binom{m+1}{r}$ , each inner run collapses to a single binomial coefficient $\binom{n-i+1}{r}$ .