The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is:
A frog is sitting on the edge of a pond facing the opposite bank. In front of the frog, running along the pond's diameter, is a line of $N$ lilypads. This is a very athletic frog: it is able in a single leap to land on any of the $N$ lilypads in the pond or on the opposite bank (for a total of $N + 1$ possible destinations). The frog first considers all $N+1$ positions in front of it, chooses one randomly with uniform probability, and then jumps to this location. It then repeats the process of choosing a new random position from those remaining in front of it (never jumping backwards). This goes on until the frog eventually reaches the opposite bank.
The puzzle is twofold: First, if $N=10$, what is the expectation value of the number of jumps the frog will take to reach the other side of the pond? Second, find an explicit formula (NOT a recurrence relation!) for the expectation value of the number of jumps in general for $N$ lilypads.
(It's a great puzzle; if you haven't yet given it a shot, I'd highly recommend doing so before reading any possible spoilers in the rest of this post!).
To attempt this puzzle, I first calculated the first few terms by hand and then tried to generalize my result. I eventually came up with a recursive algorithm for the expectation value $f$:
def f(n, depth=1): if n == 0: return depth else: return (n * f(n - 1, depth) + f(n - 1, depth + 1)) / (n + 1)
However, the second part of the puzzle explicitly disallows recurrence relations as solutions, so I am trying to un-roll/solve the recurrence relation. There are already several questions on strategies for solving recurrence relations (see this and this), but none I can find on solving recurrence relations which are dependent on the depth of recursion. Any help on how to do this is appreciated.