I have a problem that reduces to solving the following recurrence relation:
$$X(2, 1) = 1, \ \ \ X(n, 0) = 0, \ \ \ X(n, k \geq n) = 0$$ $$X(n, 0 < k < n) = \frac{k-1}{n-1} X(n-1, k-1) + \left(1 - \frac{k}{n-1}\right) X(n-1, k)$$
When I am given the final answer, it's easy for me to prove that it's correct -- I can do it either by induction, or by simply plugging it in and showing the two sides are equal.
However, what I don't know is how to systematically derive the final answer in the first place.
How do I solve this recurrence relation?