Exercise
Suppose that we toss balls into b bins until some bin contains two balls. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses?
Answer
It seems that this is quite a simple question, and every answers I have found through Google asks me to refer to the Birthday Paradox #Average number of people.
Yet the section specifically deals with the same problem, which directly tells me the final answer(the expected number) is $$1 + \sum_{k=1}^{b}\frac{b!}{(b-k)!*b^k}$$
But the thing is that I don't understand where this form is from? Is there a more detailed explanation?
My thought
Assume $S_k$ means after $k_{th}$ tosses, there exists two balls in one same bin. As a result, $$P(S_k) = \frac{b!*(k-1)}{(b-k+1)! * b^k} (2 \le k \le b+1)$$
Thus, the expected number is $$\sum_{k=2}^{b+1}P(S_k) * k$$
which is $$\sum_{k=2}^{b+1}\frac{b!*(k-1)*k}{(b-k+1)! * b^k}\\=\sum_{k=1}^{b}\frac{b!*k*(k+1)}{(b-k)! * b^{k+1}}$$
Considering that $$\sum_{k=2}^{b+1}P(S_k)=\sum_{k=2}^{b+1}\frac{b!*(k-1)}{(b-k+1)! * b^k}=\sum_{k=1}^{b}\frac{b!*k}{(b-k)! * b^{k+1}}=1$$
I could simplify the former expect number as $$1+\sum_{k=1}^{b}\frac{b!*k^2}{(b-k)! * b^{k+1}}$$
But this form does not seem to me the same as what shows in wiki (or at least not as simplified), even though I have checked a few small numbers(2,3) showing that they are equal (!!I have just checked these two values, I am not sure for a bigger b. So please note that they are possibly not the same). However, I fail to understand how to simplify my form further as in wiki, or it simply uses another way to approach that answer? Any ideas?
