Color Balls

Non-Coding Problem:
Given a bag of n balls each with a different color. Each time you pick up a pair of balls and paint both to one of their colors. What's the expected number of steps before all balls become the same color?

Analysis:
This is a problem from the "Green Cover Book". It's easy to see that we have the following transition probability.

Thus if we let \(\mu_i\) be the expected number of steps getting to one color when the bag has i distinct colors, then we have \[ \mu_i = 1 + \frac{i(i-1)}{n(n-1)} \mu_{i-1}+\left(1-\frac{i(i-1)}{n(n-1)}\right) \mu_i. \] From this we can use induction to prove that \[ \mu_i = \frac{i-1}{i} n(n-1). \] Therefore we have \[ \mu_n = (n-1)^2. \]