n empty balls and an observer 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. 
 A: There is no inconsistency between the claimed result and the value you think you get in the case $r=1$, since the result says "at most", and $\frac{n-1}{2}$ is certainly at most $n-1$.
Also, $\frac{n-1}{2}$ isn't correct for $r=1$. For example, if $n=2$ the expected value is precisely $1$ (there is one uncoloured circle, and the observer can see both circles), and for $n=3$ the expected value is $\frac 53$, since if the black circle is in the middle (probability $1/3$) the observer can only see one uncoloured circle, but otherwise (s)he can see both.
A: 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}}} $
