# How to prove $\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}}r = \frac{b}{r + 1}$?

The context for this is that I was trying to solve the problem 3.11.13 (c) from the Grimmett & Stirzaker textbook :

(b) An urn contains b blue and r red balls. Balls are removed at random until the first blue ball is drawn. Show that the expected number drawn is (b + r + 1)/(b + 1).

(c) The balls are replaced and then removed at random until all the remaining balls are of the same colour. Find the expected number remaining in the urn.

Let's write this expectation : $$E[T]$$

So I translated the problem into something more amenable. I consider that we draw all $$r+b$$ balls successively and line them up from left to right. I noticed that given that the remaining color is blue, the probability of having a certain number $$k$$ of blue balls left in the urn is the same as the probability (say $$\mathbb{P}(T=k|B)$$ ) for the $$r+b-k$$-th ball to be red and all balls to the right to be blue. The order doesn't matter in drawing without replacement situations so it is as if the first ball we drew was red and the next $$k$$ balls after that were blue, therefore we have :

$$\mathbb{P}(T=k |B) = \frac{r+b}{b} \frac{r}{r+b} \frac{b}{r+b-1} \dots \frac{b-(k-1)}{r+b-1-(k-1)}$$.

So by the obvious notation we get : $$E[T] = \frac{b}{r+b}E[T|B] + \frac{r}{r+b}E[T|R]$$

Long story short we obtain :

$$\frac{b}{r+b} E[T|B] = \sum_{i=1}^b k \frac{r}{r+b} \frac{b}{r+b-1} \dots \frac{b-(k-1)}{r+b-1-(k-1)} = \sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}}$$

I took a peek at the answer I'm supposed to get, so I know that $$\frac{b}{r+b} E[T|B]$$ is supposed to be equal to $$\frac{b}{r+ 1}$$, but I don't know how to simplify it.

tl;dr,

I'm trying to prove that :

$$\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}} = \frac{b}{r + 1}$$

Anyone can help?

EDIT:

The hockey-stick identity was the way to go (had no idea it was a thing).

We rearrange $$\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}}$$ to get : $$\sum_{k=1}^b \frac{b! (r+b-k)!}{(b-k)! (r+b)!} = \frac{1}{\binom{b+r}{r}}\sum_{k=1}^b \binom{r+b-k}{r} = \frac{1}{\binom{b+r}{r}}\sum_{k=r}^{r+b-1} \binom{k}{r}$$

Which yields $$\frac{b}{r+1}$$ using the hockey-stick identity!

• Here's how to ask a good question. Follow these guidelines to get help in this forum. It's particularly important that you share your own work and thoughts on the problem to show that you have made a serious effort by yourself before asking for help, and you're not just trying to get others to solve it for you. Jan 26 at 9:03
• Here you go I've added some context to my question to prove that I'm not trying to use people's kindness to get a good grade on my homework. Jan 26 at 9:50

There shouldn't be an $$r$$ in the sum, i.e. the result should be
$$\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}} = \frac{b}{r+1}$$