It's obvious for $r=1$ and every $n$, and also for $r=2$ and $n=1$, and then it suffices to notice that $F$ satisfies the recurrence relation $F(n+1,r)=\frac{F(n,r)\cdot\binom nr+F(n,r-1)\cdot\binom n{r-1}}{\binom{n+1}r}\ (*)$: there are two types of groups of size $r$ in $\{1,2,\ldots,n+1\}$, namely those that contain $n+1$ and those which do not. The average of the smallest element over those which do not is $F(n,r)$ and there are $\binom nr$ of them, while the average of the smallest element over those which do contain $n+1$ is $F(n,r-1)$ and there are $\binom n{r-1}$ such groups, hence $(*)$.

$\sum_{k=1}^{n}{k \choose 1}{n-k \choose r-1}$ $=\sum_{k=1}^{n-(r-1)}{k}{n-k \choose r-1}$ $=\sum_{k=1}^{n-(r-1)}{n-k \choose r-1}+\sum_{k=2}^{n-(r-1)}{n-k \choose r-1}+...+\sum_{k=n-(r-1)}^{n-(r-1)}{n-k \choose r-1}$ $={n\choose r}+{n-1\choose r}+...+{r\choose r}$ $={n+1\choose r+1}$

OHO wrote: Quote: $ \sum_{k=1}^{n}{k \choose 1}{n-k \choose r-1}$ But we need to sum only for $ 1 \le k \le n-r+1$ i.e. we need $ \sum_{k=1}^{n-r+1}{k \choose 1}{n-k \choose r-1}$ Also, all the terms in the sum $ \sum_{k=n-r+2}^{n}{k \choose 1}{n-k \choose r-1}$ will be undefined because in $ {n-k \choose r-1}, n-k < r-1$ :

Ah! Never mind! I got it!!

A similar solution with a different idea: We know that the sum of the $ r$ element subsets of the given $ n$ element set is $ {n\choose r}F(n,r)$ by the given statement. Now the question asks us to prove $ F(n,r) = \frac {n + 1}{r + 1}$ which gives us an idea to consider an $ n + 1$ element set containing $ n$ elements from the given set. The additional element can be chosen as $ 0$ as we are dealing with the smallest number of each $ r$ element subset here. Nut me want to have a one to one correspondence with $ {0,1,2,3,...,n}$ with the given set through some function. Consider the $ r + 1$ element subsets of the set $ {0,1,2,3,...,n}$ and strike off the smallest number from each of the $ r + 1$ element subsets. Now, it is obvious that each $ r$ element subset of the given set $ {1,2,3,...,n}$ occurs $ k$ times where $ k$ is the least element in each of the $ r$ element subsets. Thus we can instead count the sum of the $ r$ element subsets of the given set as $ {n + 1\choose {r + 1}}$. This implies $ F(n,r) = \frac {{n + 1\choose {r + 1}}} { {n\choose r}} = \frac {n + 1}{r + 1}$.

In general, if $F(k,n,r)$ is the average of the $k$-th least elements of all the $r$-element subsets of $\{1,2,\dots , n\}$ is $$F(k,n,r)=k\frac{n+1}{r+1}.$$ Consider a regular $n+1$-gon inscribed in a circle. We take $r+1$ of the points, which split the circle into $r+1$ parts $\rho_i,~\forall 1 \leq i \leq n+1$. By symmetry, $\mathbb{E} \left [|\rho_i| \right]=\tfrac{n+1}{r+1}$. Cut the circle just after the $(r+1)$-th chosen point, and straighten the circle into a line segment, which has length $n+1$, so we have $r$ chosen points among $\{1,2, \dots , n\}$. Then the expected value of the minimal distance of a point to the endpoint of the segment (the origin) is $\mathbb{E} \left [|\rho_i| \right]=\tfrac{n+1}{r+1}$. Again by symmetry, the distance of the $k$-th chosen point to the origin is $$F(k,n,r)=k\frac{n+1}{r+1}.$$

jlammy wrote: In general, if $F(k,n,r)$ is the average of the $k$-th least elements of all the $r$-element subsets of $\{1,2,\dots , n\}$ is $$F(k,n,r)=k\frac{n+1}{r+1}.$$ Consider a regular $n+1$-gon inscribed in a circle. We take $r+1$ of the points, which split the circle into $r+1$ parts $\rho_i,~\forall 1 \leq i \leq n+1$. By symmetry, $\mathbb{E} \left [|\rho_i| \right]=\tfrac{n+1}{r+1}$. Cut the circle just after the $(r+1)$-th chosen point, and straighten the circle into a line segment, which has length $n+1$, so we have $r$ chosen points among $\{1,2, \dots , n\}$. Then the expected value of the minimal distance of a point to the endpoint of the segment (the origin) is $\mathbb{E} \left [|\rho_i| \right]=\tfrac{n+1}{r+1}$. Again by symmetry, the distance of the $k$-th chosen point to the origin is $$F(k,n,r)=k\frac{n+1}{r+1}.$$ that's true

jlammy wrote: In general, if $F(k,n,r)$ is the average of the $k$-th least elements of all the $r$-element subsets of $\{1,2,\dots , n\}$ is $$F(k,n,r)=k\frac{n+1}{r+1}.$$

I tried to find another solution by using the same method as OHO did to solve jlammy's general problem but failed. Does anyone can help me with this? Thanks.

shinichiman wrote: jlammy wrote: In general, if $F(k,n,r)$ is the average of the $k$-th least elements of all the $r$-element subsets of $\{1,2,\dots , n\}$ is $$F(k,n,r)=k\frac{n+1}{r+1}.$$

I tried to find another solution by using the same method as OHO did to solve jlammy's general problem but failed. Does anyone can help me with this? Thanks. Here is a different solution,but it's not like what OHO did.

A Proof using Graph Theory: We consider the bipartite graph in which the black vertices are the $(r+1) $ element subsets of $[{0,...,n}] $,the white vertices are the $r $-element subsets of $[{1,2,...,n}] $ and a black vertex $X $ is adjacent to the white vertex $Y $ by deleting the smallest element from $X $. So,our bipartite graph has $\binom {n+1}{r+1} $ black vertices, $\binom {n}{r} $ white vertices and $\binom {n+1}{r+1}=\frac {n+1}{r+1}\binom {n}{r} $ edges. We note that,degree of a white vertex is the value of its least element. Thus the desired average minimum element is the average degree $\frac {(n+1)}{(r+1)} $ of a white vertex. And in this way we completed our thesis.

It's a generalization of this: https://artofproblemsolving.com/community/c5h1064887_smallest_element_of_subset

Agr_94_Math wrote: A similar solution with a different idea: We know that the sum of the $ r$ element subsets of the given $ n$ element set is $ {n\choose r}F(n,r)$ by the given statement. Now the question asks us to prove $ F(n,r) = \frac {n + 1}{r + 1}$ which gives us an idea to consider an $ n + 1$ element set containing $ n$ elements from the given set. The additional element can be chosen as $ 0$ as we are dealing with the smallest number of each $ r$ element subset here. Nut me want to have a one to one correspondence with $ {0,1,2,3,...,n}$ with the given set through some function. Consider the $ r + 1$ element subsets of the set $ {0,1,2,3,...,n}$ and strike off the smallest number from each of the $ r + 1$ element subsets. Now, it is obvious that each $ r$ element subset of the given set $ {1,2,3,...,n}$ occurs $ k$ times where $ k$ is the least element in each of the $ r$ element subsets. Thus we can instead count the sum of the $ r$ element subsets of the given set as $ {n + 1\choose {r + 1}}$. This implies $ F(n,r) = \frac {{n + 1\choose {r + 1}}} { {n\choose r}} = \frac {n + 1}{r + 1}$. Can u please make it more clear

AopsUser101 wrote: It's a generalization of this FTFY

Clearly, when $1$ is the smallest element, we can choose the remaining $(r-1)$ elements from $\{2,3,\cdots,n\}$ When $2$ is the smallest element, we can choose the remaining $(r-1)$ elements from $\{3,4,\cdots,n\}$ Continuing in this same fashion, the summation of the smallest elements from all possible subsets is

And obviously, the number of subsets is nothing but $$\sum_{i=1}^n \binom {n-i}{r-1}$$Therefore, we can write $$F(n,r)=\frac{\sum_{i=1}^{n} i\binom {n-i}{r-1}}{\sum_{i=1}^{n} \binom {n-i}{r-1}}$$ The numerator can be expressed as $$\binom {n-1}{r-1} + \left(\binom {n-2}{r-1} + \binom {n-2}{r-1}\right) + \left(\binom {n-3}{r-1} + \binom {n-3}{r-1} + \binom {n-3}{r-1}\right)+ \cdots$$$$=\sum_{i=1}^{n-r+1} \binom {n-i}{r-1} + \sum_{i=2}^{n-r+1} \binom {n-i}{r-1} + \cdots + \sum_{i=n-r+1}^{n-r+1} \binom {n-i}{r-1}$$Now using the Hockey Stick Identity we can write - $$=\binom {n}{r} + \binom{n-1}{r} + \cdots + \binom {r}{r}$$Use the Hockey Stick Identity again to get $$\binom {n+1}{r+1}$$ We can expand the denominator as - $$ \binom {n-1}{r-1} + \binom {n-2}{r-1} + \cdots + \binom {r-1}{r-1}$$By the same Identity again we can write - $$=\binom {n}{r}$$ $\therefore F(n,r)$ reduces to $$F(n,r)= \frac{ \binom {n+1}{r+1} }{ \binom {n}{r} }$$$$\implies \boxed { F(n,r)= \frac{n+1}{r+1} }$$ Q.E.D. $\square$

First we quote a useful Lemma: \begin{align} \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-2}{r-1} + \dots + \binom{r-1}{r-1} \end{align}Since it is the same as taking the smallest one in each turn in that way. Thus, the desired average is \[\frac{1\binom{n-1}{r-1} + 2\binom{n-2}{r-1} + \dots + n-r+1\binom{r-1}{r-1}}{\binom{n}{r}}\]. But note that because of (1) we can take as many of that binomials as we please resulting in \[1\binom{n-1}{r-1} + 2\binom{n-2}{r-1} + \dots + n-r+1\binom{r-1}{r-1}=\binom{n+1}{r+1}\]Now by simple algebraic manipulations we can arrive to \[\frac{\binom{n+1}{r+1}}{\binom{n}{r}}=\frac{n+1}{r+1}\] I would argue that it isn't a very difficult, though very a slippery one.

Isn't this just the general formula for 2015 AIME I #12? We get $1$ will be included $\binom{n-1}{r-1}$ times, $2$ will be included $\binom{n-2}{r-1}$ times, and so on until $n-r+1$ will be included $\binom{r-1}{r-1}$ times. So we have \[F(n,r)=\frac{1\cdot \binom{n-1}{r-1}+2\cdot \binom{n-2}{r-1} +\cdots+(n-r+1)\binom{r-1}{r-1}}{\binom{n}{r}}\] By the Hockey Stick Identity, the numerator is just $\binom{n}{r}+\binom{n-1}{r}+\cdots+\binom{r}{r}=\binom{n+1}{r+1}=\frac{(n+1)!}{(r+1)!(n-r)!}$. The denominator is $\frac{n!}{r!(n-r)!}$. When we divide, the $(n-r)!$'s cancel out. So we are left with $\frac{(n+1)!r!}{(r+1)!n!}=\frac{n+1}{r+1}$, as desired.

The number of sets with smallest element $i$ is $\binom{n-i}{r-1}$, so the sum of the smallest elements is $\sum_{i=1}^{n-r+1}i\binom{n-i}{r-1}$. Then by the hockey stick identity: \begin{align*} F(n,r)&=\frac1{\binom nr}\sum_{i=1}^{n-r+1}i\binom{n-i}{r-1}\\ &=\frac1{\binom nr}\sum_{i=1}^{n-r+1}\sum_{j=i}^{n-r+1}\binom{n-j}{r-1}\\ &=\frac1{\binom nr}\sum_{i=1}^{n-r+1}\binom{n-i}r\\ &=\frac1{\binom nr}\sum_{i=r}^n\binom ir\\ &=\frac{\binom{n+1}{r+1}}{\binom nr}\\ &=\frac{\frac{(n+1)!}{(r+1)!(n-r)!}}{\frac{n!}{r!(n-r)!}}\\ &=\frac{n+1}{r+1} \end{align*}as desired.

By considering cases on which element is the smallest, the answer is \begin{align*} \text{Average} &= \frac{\sum_{i=1}^n i{n-i \choose r-1}}{{n \choose r}} \\ &= \frac{\sum_{i=1}^n \sum_{j=i}^n {n-j \choose r-1}}{{n \choose r}} \\ &= \frac{\sum_{i=1}^n \sum_{j=i}^{n-r+1} {n-j \choose r-1}}{{n \choose r}} \\ &= \frac{\sum_{i=1}^n {n-i + 1 \choose r}}{{n \choose r}} \\ &= \frac{{n+1 \choose r+1}}{{n \choose r}}\\ &=\boxed{\frac{n+1}{r+1}}. \end{align*}

Note that the sum of the smallest elements is \begin{align*} &1\cdot \binom{n-1}{r-1} + 2 \cdot \binom{n-2}{r-1} + \cdots (n-r) \cdot \binom{r}{r-1} + (n-r+1)\cdot \binom{r-1}{r-1} \\ &= \left(\binom{n-1}{r-1}+\cdots \binom{r-1}{r-1} \right) + \left(\binom{n-2}{r-1}+\cdots \binom{r-1}{r-1} \right) + \cdots \left(\binom{r-1}{r-1}+\cdots \binom{r-1}{r-1} \right)\\ &= \binom{n}{r} + \binom{n-1}{r} + \cdots \binom{r}{r} = \binom{n+1}{r+1} \end{align*} Thus, the average is \[\frac{\binom{n+1}{r+1}}{\binom{n}{r}} = \frac{(n+1)! r! (n-r)!}{(r+1)! (n-r)! n!} = \frac{n+1}{r+1}\]and we're done. $\blacksquare$

storage: if $1$ is chosen as the minimum element then the number of ways forming subsets such that $1$ is the least element, is $\binom{n-1}{r-1}$ so we have desired $F(n,r)=\frac{\sum_{i=1}^{r-1}\binom{i}{1}\cdot \binom{n-i}{r-1}}{\binom{n}{r}}$ so from hockey stick identity we have $F(n,r)=\frac{\binom{n+1}{r+1}}{\binom{n}{r}}=\frac{n+1}{r+1}$ $\blacksquare$

IMO 1981/2, rephrased wrote: There are $n$ students at MOP. The director wants to interview one of $r$ students, but he does not know who is who so he keeps asking different people until he find one of the $r$ students. Prove that the expected number of students he has to ask is $(n+1)/(r+1)$ each non-selected person has a $1/(r+1)$ chance of being asked before all selected people, hence $1+(n-r)/(r+1)=(n+1)/(r+1) \blacksquare$