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 5: Simplify the binomial ratio

Previous step Next step

\frac{\binom{n+1}{r+1}}{\binom{n}{r}} = \frac{\frac{(n+1)!}{(r+1)!(n-r)!}}{\frac{n!}{r!(n-r)!}} = \frac{n+1}{r+1}

Detailed analysis

Expanding both binomial coefficients with factorials and cancelling $n!/(n-r)!$ and $r!/(r+1)!=1/(r+1)$ leaves exactly $\frac{n+1}{r+1}$ , proving the claimed formula for $F(n,r)$ .