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 5 of 6: Apply the hockey-stick identity once more

Previous step Next step

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

Detailed analysis

Summing the collapsed rows from Step 4 over $i=1,\dots,n-r+1$ gives $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}$ , and the hockey-stick identity again collapses this to $\binom{n+1}{r+1}$ .