Analyzing Randomly Descending Sequences

Finals week just ended for me so I'm hoping to post some new cool math problems in the next few days.  In this blog post, I present a math problem that is very easy to understand what it is asking, but not so easy to solve.  Regardless, I will present my solution, which yielded a very interesting result.

You construct a sequence \( k_1, k_2, ..., k_m \) by randomly picking an integer from the set \( 0 \leq k_1 < n \).  After picking \( k_1 \), you repeat the process by picking \( k_2 \) randomly from \( 0 \leq k_2 < k_1 \) and repeat the process until you can no longer pick any numbers (when \( k_m = 0 \)).  Find a function for \( f(n) \), where \( f(n) \) is the expected value of the length of this sequence.

If \( n = 3 \), then the possible sequences are  \( \{ [0], [1,0], [2,0], [2,1,0] \} \), but these don't all occur with equal probability: \( P([0]) = \frac{1}{3}, P([1,0]) = \frac{1}{3}, P([2,0]) = \frac{1}{6}, P([2,1,0]) = \frac{1}{6} \).  Using these probabilities, we can easily compute \( f(3) \):
$$
f(3) = \frac{1}{3} \cdot 1 + \Big(\frac{1}{3} + \frac{1}{6}\Big) \cdot 2 + \frac{1}{6} \cdot 3 = \frac{11}{6}
$$  By similar analysis, we can see \( f(0) = 0, f(1) = 1, \) and \( f(2) = \frac{3}{2} \).  Do you recognize a pattern?  I didn't see it right away, but let's keep going and see what we can come up with.

This problem is inherently recursive, and we can write a recurrence relation for \( f(n) \).  The possible values for \( k_1 \) are \( k_1 \in \{ 0, 1, ..., n-1 \} \).  In each case the problem reduces to \( f(k_1) \), but we must average the results over all the possibilities.  Here is a recurrence relation for \( f(n) \):
$$
f(n) = 1 + \frac{1}{n} \sum_{k=0}^{n-1} f(k)
$$ In this equation, the \( +1 \) represents the cost of reducing the problem in size (when we choose \( k_1 \), that adds 1 item to our sequence).  The summation is the average of the expected values all the possible sub problems that can arise from the current position.  Let's rearrange the recurrence relation and try to make some simplifications.
$$
n (f(n) - 1) = \sum_{k=0}^{n-1} f(k) = f(n-1) + \sum_{k=0}^{n-2} f(k)
$$ Notice that we can also write \( f(n-1) \) in a similar manner.
$$
(n-1) (f(n-1) - 1) = \sum_{k=0}^{n-2} f(k)
$$ We can replace the summation in the top formula with the summation in the bottom formula to get a nice
recurrence relation for \( f(n) \) in terms of \( f(n-1) \).
$$
n (f(n) - 1) = f(n-1) + (n-1) (f(n-1) - 1)
$$ After some algebraic manipulation, we can see that
$$
f(n) = f(n-1) + \frac{1}{n}
$$ Additionally, we have the initial condition that \( f(0) = 0 \), so we have
$$
f(n) = \sum_{i=1}^n \frac{1}{i} = H_n
$$ This is the exact construction for the harmonic numbers!  Although I was unable to answer the original question and find a function for \( f(n) \) in closed form, this is an equally exciting result.