Consider $n$ empty circles in a row. An observer sits in one of the $n−1$ gaps between them. A random subset of r circles is colored black. Show that the expected number of empty circles the observer sees is at most $ \frac{2(n − r)}{(r + 1)}$. (The observer can see through empty circles but not through black ones.) Hint: Instead of coloring r circles color $r + 1$ of them black first and then make a random black circle empty again.
The end result seems dubious to me, let alone attempting to prove it. Even for the case of $r = 1$, I think I should get $\frac{n-1}{2}$. I say this because the number of empty balls the observers sees must be the number of balls in-between two black balls (or one black ball in the case the observer is at the two ends of the line up). Could you explain to me why this is not the case? I already saw the proof from the book but I don't believe this result is correct.
Exact value
Let count that expectation. Let $X$ be a random variable that counts circles, that observer sees. Let $X_k$, for $k \in \{1,...,n-1\}$ be a random variable that counts circles, that observer sees, provided he is at $k$'th gap (by $k$'th gap, I mean there are $k$ circles to the left). Now, every $X_k = L_k + R_k$, where $L_k$, $R_k$ counts number of circles to the left/right.
Note that: $ \mathbb E[X] = \frac{1}{n-1}\sum_{k=1}^{n-1} \mathbb E[X_k] = \frac{2}{n-1} \sum_{k=1}^{n-1} \mathbb E[L_k]$. (due to symmetry)
So we have to count $\mathbb E[L_k]$. There are exactly $k$ circles to the left, and $n-k$ circles to the right (which aren't to be seen). We colour exactly $r$ of them.
Note that $L_k = Y_{k,1} + ... Y_{k,k}$, where $Y_{k,i}$ is $0-1$ random variable, which is $1$ when observer sees $i$'th circle, and $0$ otherwise.
Then $\mathbb E[X] = \frac{2}{n-1} \sum_{k=1}^{n-1} \sum_{i=1}^{k} \mathbb E[Y_{k,i}] = \frac{2}{n-1} \sum_{k=1}^{n-1} \sum_{i=1}^{k} \mathbb P(Y_{k,i} = 1)$.
For $Y_{k,i} =1$ to happen, the circles with numbers $\{i,...,k\}$ can't be coloured. So we can't choose $k-i+1$ circles to colour. That means there is $n-k+i-1$ cirlces left to choose from, and we want to colour exactly $r$, that clearly means that $i \ge r+k+1-n$.
So if those condition are satisfied, then $\mathbb P(Y_{k,i}=1) = \frac{{n-k+i-1}\choose{r}}{{n}\choose{r}}$.
So we end up with :
$ \mathbb E[X] = \frac{2}{(n-1){{n}\choose{r}}} \sum_{k=1}^{n-1} \sum_{i=1}^{k} {{n-k+i-1}\choose{r}} = \frac{2}{(n-1){{n}\choose{r}}} \sum_{k=1}^{n-1} ( \sum_{i=0}^{k} {{n-k+i-1}\choose{r}} - {{n-k-1}\choose{r}}) $.
Now, we'll use that $\sum_{k=0}^d { {n+k}\choose{m} } = {n+d+1 \choose m+1} - {n \choose m+1}$ (Calculate the sum $\sum_{k=0}^d\binom{n+k}{m}$). By that we get:
$\mathbb E[X] = \frac{2}{(n-1){{n}\choose{r}}} \sum_{k=1}^{n-1}( {(n-k-1)+k+1 \choose r+1} - {(n-k-1) \choose r+1} - k{{n-k-1}\choose{r}}) = $
$= \frac{2}{(n-1){{n}\choose{r}}} \sum_{k=1}^{n-1} ( {n \choose r+1} - {n-k-1 \choose r+1} - k{{n-k-1}\choose{r}}) = \frac{2(n-1){n \choose r+1}}{(n-1){{n}\choose{r}}} - \sum_{k=1}^{n-1}({(n-k-1) \choose r+1} + k{{n-k-1}\choose{r}}) $
So, HERE you can have your bound, because $\frac{2(n-1){n \choose r+1}}{(n-1){{n}\choose{r}}} = \frac{2n!(n-r)!r!}{(r+1)!n!(n-r-1)!} = \frac{2(n-r)}{r+1} $
But we'll try to calculate the rest. We still have $\sum_{k=1}^{n-1}({(n-k-1) \choose r+1} + k{{n-k-1}\choose{r}})$ left. By taking $s = (n-k-1), s \in \{0,...,n-2\}, k=n-s-1$, we have:
$\sum_{k=1}^{n-1}({(n-k-1) \choose r+1} + k{{n-k-1}\choose{r}}) = \sum_{s=0}^{n-2}({s \choose r+1} + (n-s-1){{s}\choose{r}})$.
Notice that due to our formula (second term is zero), we have:
$\sum_{s=0}^{n-2}({s \choose r+1} + (n-s-1){{s}\choose{r}}) = {n-1 \choose r+2} + n {n-1 \choose r+1} - \sum_{s=0}^{n-2}(s+1){{s}\choose{r}}) = {n-1 \choose r+2} + n {n-1 \choose r+1} - \sum_{s=0}^{n-2}(r+1){{s+1}\choose{r+1}} = {n-1 \choose r+2} + n {n-1 \choose r+1} - (r+1){n \choose r+2} $
Plugging it into what we get earlier:
$\mathbb E[X] = \frac{2(n-r)}{r+1} - \frac{2({n-1 \choose r+2} + n {n-1 \choose r+1} - (r+1){n \choose r+2})}{(n-1){{n}\choose{r}}} $