Consider the smallest number in each of the $n\choose r$ subsets (of size $r$) of $S=\{1,2,\ldots,n\}$... Consider the smallest number in each of the $n\choose r$ subsets (of size $r$) of $S=\{1,2,\ldots,n\}$.Show that the arithmetic mean of the numbers so obtained is ${n+1}\over{r+1}$.
I have no idea, how to solve it.It would be better if the solution has bijection. Please help!
 A: Here's a slightly different way of showing the result.  Let $\mu_{n,r}$ be the mean of the minimum elements of the subsets of size $r$ of $\{1, 2, \ldots, n\}$. We'll show that for each $n$ and for all $r \in \{1, \ldots, n\}$, $\mu_{n,r} = \frac{n+1}{r+1}$. We proceed by induction on $n$.
For the base case $n=1$ we must have $r=1$, and there is only the singleton $\{1\}$, so the mean is $\mu_{1,1} = 1 = \frac{1+1}{1+1}$.
Now assume the result holds for $n$, so $\mu_{n,k} = \frac{n+1}{k+1}$ for all $k \in \{1, \ldots, n\}$. Suppose $r \in \{1, \ldots, n+1\}$. If $r = n+1$, then the only subset of size $r$ is the whole set and the result holds since $\frac{n+2}{(n+1) + 1} = 1$. Similarly, if $r=1$ so we are considering all singletons, in which case
$$
\mu_{n+1,1} = \frac{1 + \cdots + n + n+1}{n+1} = \frac{(n+1)(n+2)}{2} \frac{1}{n+1} = \frac{n+2}{2}
$$
and the result holds. Thus it remains to prove the result for $r \in \{2, \ldots, n\}$.
Of the $\binom{n+1}{r}$ subsets of $\{1, 2, \ldots, n+1\}$, $\binom{n}{r-1}$ of them contain the element $n+1$ and $\binom{n}{r}$ of them do not.  The latter collection consists of all subsets of size $r$ from $\{1, 2, \ldots n\}$, so the mean of their minimum elements is $\mu_{n,r} = \frac{n+1}{r+1}$ by inductive hypothesis.
Note that in the former collection of subsets (those containing $n+1$), $n+1$ can't be the minimum element.  Thus the mean of their minimum elements will be the same as for all $r-1$ size subsets chosen from $\{1, 2, \ldots, n\}$, which is $\mu_{n,r-1} = \frac{n+1}{r-1 +1} = \frac{n+1}{r}$ by inductive hypothesis.  Thus $\mu_{n+1,r}$ is the weighted average
$$
\mu_{n+1,r} = \frac{\binom{n}{r-1} \frac{n+1}{r} + \binom{n}{r} \frac{n+1}{r+1}}{\binom{n+1}{r}} \, .
$$
Observing that $\binom{n}{r-1} \frac{n+1}{r} = \binom{n+1}{r}$ and $\binom{n}{r} \frac{n+1}{r+1} = \binom{n+1}{r+1}$, then
$$
\mu_{n+1,r} = \frac{\binom{n+1}{r} + \binom{n+1}{r+1}}{\binom{n+1}{r}} = \frac{\binom{n+2}{r+1}}{\binom{n+1}{r}} = \frac{n+2}{r+1}
$$
as desired.
A: Let $T_i$ denote the sum of the subsets whose smallest number is $i$
There are $\binom{n-i}{r-1}$ subsets whose smallest number is $i$.
Thus, $$T_i=i\cdot\binom{n-i}{r-1}$$
$$\sum_{i=1}^{n-r+1}T_i=1\cdot\binom{n-1}{r-1}+2\cdot\binom{n-2}{r-1}+\dots+(n-1)\cdot\binom{r-1}{r-1}$$
$$\sum_{i=1}^{n-r+1}T_i=\sum_{i=1}^{r-n+1}\binom{r-i}{r-1}+\sum_{i=1}^{r-n+2}\binom{r-i}{r-1}+\dots+\sum_{i=1}^{1}\binom{r-i}{r-1}$$
Using Hockey-Stick identity, we get:
$$\sum_{i=1}^{n-r+1}T_i=\binom{n}{r}+\binom{n-1}{r}+\dots+\binom{r}{r}$$
Hockey-Stick once more to get:
$$\sum_{i=1}^{n-r+1}T_i=\binom{n+1}{r+1}$$
We have a total of $\binom{n}{r}$ subsets.
Thus, the arithmetic mean is $\Large\frac{\binom{n+1}{r+1}}{\binom{n}{r}}=\frac{n+1}{r+1}$
A: Fix $r$ and 
denote the result as $f(n)$.
Clearly, $f(r)=1=\frac{r+1}{r+1}$. For $n>r$
there are $n-1\choose r-1$ subsets having $1$ as smallest element. The other ${n\choose r}-{n-1\choose r-1}$ are in fact subsets of $\{2,\ldots,n\}$ and hence their mean is $1+f(n-1)$. We obtain the recursion
$$ \begin{align}f(n)&=\frac{{n-1\choose r-1}+\left({n\choose r}-{n-1\choose r-1}\right)(1+f(n-1)}{n\choose r}\\&=1+\left(1-\frac{n-1\choose r-1}{n\choose r}\right)f(n-1)\\&=1+\left(1-\frac{r}{n}\right)f(n-1).\end{align}$$
From this we show immediately by induction that $f(n)=\frac{n+1}{r+1}$ for all $n\ge r$.
A: I am not posting a solution....i just a asking a question on the basis of the solution posted above
Can i take the induction statement that
$p(n):$ For all $r$ the mean of the minimum elements of the subsets of size r of $\{1,2,…,n\}$ is $\frac{n+1}{r+1}$ where $r\leq n$
In this case we are not dealing with a double induction.
