There is an interesting puzzle in YouTube video Can you solve The Frog Problem?. I'll try to give an equivalent formulation here.
A frog is on one side of the pond and wants to get on the other side. There are $n$ lily leaves ahead in a line, the $n$-th leave laying on the other end of the pond and being the destination. Whatever the position the frog is at any time, it will only go ahead and the probability to land on one of the leaves left in front of it (including the destination) is uniform. So, for example, if there are 10 leaves ahead, there is a probability of $\frac{1}{10}$ that it will land on any of them.
What is the expected value for the number of jumps it will take the frog to arrive to the destination leaf? The answer cannot be a recursive expression.
I think I have a solution, I'll report it as an answer below.
Best Answer
We will call $J_n$ the expected value for the jumps when there are $n$ leaves ahead. We set also $J_0 = 0$, which is consistent with the fact that if the frog has no leaf ahead it needs to do exactly $0$ jumps to arrive at destination.
We will name/number the leaves according to their distance from the destination. So the destination will be leaf $0$, the one immediately before $1$ and so on up to leaf $n-1$ that is the one in front of the frog. There are in total $n$ leaves and the probability to jump on any of them with one leap is $\frac{1}{n}$ according to the puzzle indications.
When the frog takes this first leap, it will land on leaf $k$, with $k \in \{0, ... n-1\}$ and, from that point, the expected value of remaining leaps will be $J_k$. Considering that these events are mutually exclusive, we get the following:
$$J_n = \sum_{k=0}^{n-1}\frac{1}{n}(1 + J_k)$$
where the $1$ represents the first leap to reach position $k$. As there are $n$ elements in the sum, it can be rearranged as:
$$J_n = 1 + \frac{1}{n} \sum_{k=0}^{n-1}J_k$$
which is indeed a bit too recursive. With simple arithmetics we can further rearrange it as follows:
$$n(J_n - 1) = \sum_{k=0}^{n-1}J_k$$
This relation is generic and can be also rewritten with $n-1$ instead of $n$:
$$(n-1)(J_{n-1} - 1) = \sum_{k=0}^{n-2}J_k$$
Subtracting the two relations we get:
$$n(J_n - 1) - (n-1)(J_{n-1} - 1) = \sum_{k=0}^{n-1}J_k - \sum_{k=0}^{n-2}J_k = J_{n-1}$$
that is:
$$n(J_n - 1) = (n-1)(J_{n-1} - 1) + J_{n-1} = nJ_{n-1} - (n-1)$$ $$J_n - 1 = J_{n-1} - \frac{n-1}{n}$$ $$J_n = J_{n-1} + \frac{1}{n}$$
Still recursive, but at least the $n$-th element is expressed in terms of $n-1$-th element only.
Now considering that $J_0 = 0$ the relation above can be collapsed to:
$$J_n = \sum_{k = 1}^{n}\frac{1}{k}$$
which is the answer to the puzzle.