>>73
Your post was kind of difficult to read so I will try to summarise the problem and solution in my own words. I also think you made a typo, so my reccurance relation looks very slightly different to yours, but the solution is the same.


\textbf{Problem}

You have two boxes, box #1 and box #2. You also have a bag with an unlimited number of balls. At time 0, box #1 has one ball and box #2 has one ball.

In every iteration:
- Choose a ball at random from the set of balls that are in the boxes.
- Take a new ball from the bag and put it into the box where the chosen ball was.

So at time \math{t}, there are \math{t+2} balls in both boxes. Each box has between \math{1} and \math{t+1} balls (inclusive).

Let \math{p_{t,k}} denote the probability that box #1 has exactly k balls at time t.

So by the initial conditions:
- \math{p_{0,k}=1} if \math{k=1}
- \math{p_{0,k}=0} otherwise

Derive a closed form expression for \math{p_{t,k}}.


\textbf{Solution}

We know that at time \math{t-1} there were \math{(t-1)+2=t+1} balls in both boxes.

At time \math{t}, how can box #1 come to contain \math{k} balls? There are two cases:
- at time \math{t-1} it had \math{k-1} balls and was chosen
- at time \math{t-1} it had \math{k} balls and was not chosen

This leads to the following reccurence relation

\eqn{p_{t,k} = p_{t-1,k-1}\frac{k-1}{t+1} + p_{t-1,k}\frac{t+1-k}{t+1}}

which has the solution by induction on \math{t}

\eqn{p_{t,k} = \frac{1}{t+1}}

where \math{1<=k<=t+1}.

Base case for \math{t=1} is trivial.

\eqn{p_{t,k}}

\eqn{ = p_{t-1,k-1}\frac{k-1}{t+1} + p_{t-1,k}\frac{t+1-k}{t+1}}

\eqn{ = \frac{1}{(t-1)+1}\frac{k-1}{t+1} + \frac{1}{(t-1)+1}\frac{t+1-k}{t+1}}

by inductive assumption and because \math{t>=1} so no problems with dividing by 0

\eqn{ = \frac{k-1}{t(t+1)} + \frac{t+1-k}{t(t+1)}}

\eqn{ = \frac{k-1+t+1-k}{t(t+1)}}

\eqn{ = \frac{t}{t(t+1)}}

\eqn{ = \frac{1}{t+1}}

which is what we wanted.


Now for some values of \math{k}, namely \math{1} and \math{t+1} this is somewhat an obvious result because in these cases, we have to look at the probability of choosing one box repeatedly which is just \math{\frac{t!}{(t+1)!}=\frac{1}{t+1}}, but for the other cases it is not so obvious. Drawing a tree diagram helps verify the result, I did it up to \math{t=3}.

Cool problem overall anon :)