Solving this quant interview question

Question

I found this exercise:

For $R$ a map taking $n \in \mathbb{N}$ to $0,1,\ldots, n-1$ randomly with uniform distribution.

Defining a random sequence $x_0 = 10^{100}$ and $x_{i+1} = R(x_n)$ until $x_i=0$. What is the expected length $L(x_0 = 10^{100})$ of this sequence?

I have translated in into a recursion, for $L(0) = 1$ and $$L(n) = 1 + \frac{1}{n} \sum \limits_{i=0}^{n-1} L(i).$$

And this is where I am stuck. I am thinking of a way of expanding the $L(i)$ in the sum, until expressing everything as $L(0)$. Am I on the right track?

Answer 1

I managed to solve it thanks to the help of @DougM.

Simplifying the multi level induction by: $$(n+1)L(n+1) - nL(n) = 1 + L(n)$$ $$L(n+1) = L(n) + \frac{1}{n+1},$$ with the seed $L(1) = 2$ we get the general term $L(n) = 1+ H_n$ where $H_n$ is the harmonic numbers series.