<s>[INST] A Problem Dealing with putting balls in bin and Expected Value - possible wrong answer Please consider the problem below. Is my answer correct. If is not correct then where did I go wrong?
Problem:
You keep tossing balls into $n$ bins until one of the bins has two balls. For each toss there is a $\frac{1}{n}$ probability that the ball you toss lands in any one of the bins. What is the expected number of tosses?
Answer:
Let $p_i$ be the probability that after $i$ tosses we have at least one bin
with two balls.
\begin{eqnarray*}
p_1 &=& 0 \\
p_2 &=& 1 - ( 1 - \frac{1}{n} ) = \frac{1}{n} \\
p_3 &=& 1 - (1 - \frac{1}{n})(1 - \frac{1}{n-1}) \\
p_3 &=& 1 - (\frac{n-1}{n})(\frac{n-1-1}{n-1}) \\
p_3 &=& 1 - (\frac{n-2}{n}) = \frac{2}{n} \\
p_4 &=& 1 - (1 - \frac{1}{n})(1 - \frac{1}{n-1})(1 - \frac{1}{n-2}) \\
p_4 &=& 1 - ( \frac{n-1}{n} )( \frac{n-2}{n-1} )( \frac{n - 2 -1}{n - 2} ) \\
p_4 &=& 1 - \frac{n-3}{n} = \frac{3}{n} \\
\end{eqnarray*}
Now for $1 <= i <= n$ we have: $p_i = \frac{i-1}{n}$.
\begin{eqnarray*}
E &=& 2p_2 + 3p_3 + 4p_4 + ... (n+1)p_{n+1} \\
E &=& \sum_{i = 1}^{n} \frac{i(i+1)}{n} = \frac{1}{2n} \sum_{i=1}^{n} i^2 + i \\
E &=& \frac{1}{2n}(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} ) \\
E &=& \frac{n+1}{4n} ( \frac{2n+1}{3} + 1 ) \\
\end{eqnarray*}
Here is an update to my answer:
Let $p_i$ be the probability that after $i$ tosses we have at least one bin
with two balls.
\newline
\begin{eqnarray*}
p_1 &=& 0 \\
p_2 &=& 1 - ( 1 - \frac{1}{n} ) = \frac{1}{n} \\
p_3 &=& 1 - (\frac{n-1}{n})( \frac{n-2}{n}) \\
p_3 &=& 1 - \frac{(n-1)(n-2)}{n^2} = \frac{n^2 - (n^2 - 3n + 2)}{n^2} \\
p_3 &=& \frac{3n-2}{n^2} \\
p_4 &=& 1 - (\frac{n-1}{n})(\frac{n-2}{n})(\frac{n-3}{n}) \\
p_4 &=& 1 - \frac{(n^2-3n+2)(n-3)}{n^3}\\
p_4 &=& 1 - \frac{n^3-3n^2+2n - 3n^2 +9n - 6}{n^3}\\
p_4 &=& \frac{3n^2-2n + 3n^2 - 9n + 6}{n^3}\\
p_4 &=& \frac{3n^2 + 3n^2 - 11n + 6}{n^3}\\
\end{eqnarray*}
\begin{eqnarray*}
E &=& 2p_2 + 3p_3 + 4p_4 + ... (n+1)p_{n+1} \\
\end{eqnarray*}
Now, am on the right track? That is, is what I have so far correct?
Thanks,
Bob
 [/INST] Various answers have been already provided, but let me show a different approach to get it.
At the first toss you have $p_1=0$ and you end up for sure with 1 one-ball bin.
At the second, either you hit the one-ball (prob. $p_2=1/n=(1-p_1)1/n$) or you end up with 2 one-ball bins (prob. $q_2=1-p_2=(n-1)/n$).
At this point, pay attention to the fact that 
$$ \bbox[lightyellow] {  
\pi _{\,k}  = {{k - 1} \over n}\quad \quad \mu _{\,k}  = 1 - \pi _{\,k}  = {{n - \left( {k - 1} \right)} \over n}
}$$

are transitional probabilities, i.e. conditional probabilities, and precisely:
   - $\pi _{\,k}$ is the prob. of having a "hit" at the $k$-th toss, given that you did not have any hit before;
   - $\mu _{\,k}$ is the prob. of not having a "hit" at the $k$-th toss, given that you did not have any hit before.
  while $p_k$ and $q_k$ are the overall probabilities that, starting with all bins empty,
   - we have a hit at (exactly) the $k$-th toss ($p_k$);
   - we have (exactly) $k$ one-ball bins at the $k$-th toss, i.e. no hit up to that toss  ($q_k$);   

Thus it shall be made clear that
 - $\pi_k \ne p_k$ and $\mu_k \ne q_k$ notwithstanding that in the first two tosses they coincide;
 - $q_k \ne 1-p_k$, because $1-p_k$ is the probability to have a hit at a toss different from $k$, while $1-q_k$ is the probability to have a hit after the $k$-th toss;   
So
$$
\left\{ \matrix{
  q_{\,3}  = \mu _{\,1} \mu _{\,2} \mu _{\,3}  = \left( {1 - \pi _{\,1} } \right)\left( {1 - \pi _{\,2} } \right)\left( {1 - \pi _{\,3} } \right) = q_{\,2} \left( {1 - \pi _{\,3} } \right) =  \hfill \cr 
   = {{n\left( {n - 1} \right)\left( {n - 2} \right)} \over {n^{\,3} }} = {{n^{\,\underline {\,3\,} } } \over {n^{\,3} }}  \hfill \cr 
  p_{\,3}  = \left( {1 - \pi _{\,2} } \right)\pi _{\,3}  = \left( {1 - \pi _{\,1} } \right)\left( {1 - \pi _{\,2} } \right)\pi _{\,3}  = q_{\,2} \pi _{\,3}  =  \hfill \cr 
   = q_{\,2}  - q_{\,3}  = {{n - 1} \over n}{2 \over n} \hfill \cr 
  p_{\,3} \quad  \ne \quad 1 - q_{\,3}  \hfill \cr}  \right.
$$
and in general
$$ \bbox[lightyellow] {  
\left\{ \matrix{
  q_{\,k}  = {{n^{\,\underline {\,k\,} } } \over {n^{\,k} }}\quad \left| {\;0 \le k} \right. \hfill \cr 
  p_{\,k}  = q_{\,k - 1}  - q_{\,k}  = q_{\,k - 1} {{k - 1} \over n} = {{\left( {k - 1} \right)\,n^{\,\underline {\,k - 1\,} } } \over {n^{\,k} }}\quad \left| {\;1 \le k} \right. \hfill \cr}  \right.
}$$
where $x^{\,\underline {\,k\,} }$ represents the Falling Factorial
From that we obtain
$$
\left\{ \matrix{
  q_{\,0}  = q_{\,1}  = 1 \hfill \cr 
  q_{\,m}  = 0\quad \left| {\;n < m} \right. \hfill \cr 
  \sum\limits_{1\, \le \;k} {p_{\,k} }  = \sum\limits_{1\, \le \;k\; \le \,n + 1} {p_{\,k} }  = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\left( {q_{\,k - 1}  - q_{\,k} } \right)}  = q_{\,0}  - q_{\,n + 1}  = 1 \hfill \cr}  \right.
$$
since it is clear that at toss $n+1$ we have a hit for sure, if we did not have before ($\pi_{n+1}=1$).
Coming to the computation of the expected value, we have
$$ \bbox[lightyellow] {  
\eqalign{
  & E(k;\,n) = \sum\limits_{1\, \le \;k\; \le \,n + 1} {k\,p(k,n)}  = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\,{{k\left( {k - 1} \right)\,n^{\,\underline {\,k - 1\,} } } \over {n^{\,k} }}}  =   \cr 
  &  = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\left( {k\,q(k - 1,n) - k\,q(k,n)} \right)}  =   \cr 
  &  = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\left( {\left( {k - 1} \right)\,q(k - 1,n) - k\,q(k,n) + q(k - 1,n)} \right)}  =   \cr 
  &  =  - \left( {n + 1} \right)q(n + 1,n) + \sum\limits_{1\, \le \;k\; \le \,n + 1} {q(k - 1,n)}  = \sum\limits_{0\, \le \;k\; \le \,n} {q(k,n)}  \cr} 
}$$
where the change of notation is obvious.
It coincides with answer already given by C. Blatter.
Now, $q(k,n)$ can be written as
$$
q(k,n) = {{\,n^{\,\underline {\,k\,} } } \over {n^{\,k} }} = k!\left( \matrix{
  n \cr 
  k \cr}  \right)\left( {{1 \over n}} \right)^{\,k}  = \prod\limits_{0\, \le \;j\; \le \,k - 1} {\left( {1 - {j \over n}} \right)}
  = {{\,\Gamma (n + 1)} \over {n^{\,k} \,\Gamma (n - k + 1)}}
$$
but unfortunately I could not find (and doubt there is) a closed formula for the sum.
An asymptotic approximation for large $n$ could however be constructed, following various
approaches, depending on the goals that you may have.
</s>