No idea on how to start this question. Any help would be much appreciated.
A flea lives on a polyhedron with N vertices, labelled $1, . . . , N$. It hops from vertex to vertex in the following manner: if one day it is on vertex $i > 1$, the next day it hops to one of the vertices labelled $1, . . . , i−1$ with equal probability, and it dies upon reaching vertex $1$. Let $X_n$ be the position of the flea on day $n$. Show that the expected life of the flea is: $$\sum_{i=1}^{N-1} \frac{1}{i}$$
On
Added reference: This problem is discussed in Sheldon M. Ross's Introduction to Probability Models in section 4.5.2. "A Model for Algorithmic Efficiency".
For $i>1$ define $f_i(x)$ as the expected amount of time spent in state $i$, starting at $x$, i.e., $$f_i(x)=\mathbb{E}\left(\sum_{n=0}^\infty 1_{[X_n=i]}\,\bigg|\, X_0=x\right).$$
Since the flea can visit any state $i>1$ at most once, and state 1 is absorbing,
$f_i$ is the unique function with $f_i(i)=1$, $f_i(1)=0$, and is
otherwise harmonic, that is,
$$f_i(x) = \begin{cases} 0 & 1=x \\[5pt]
1 & \, i=x\\[5pt]
\sum_y p(x,y) f_i(y) & \mbox{otherwise} \end{cases}$$
Solving the equation above for this particular Markov chain gives
$$f_i(x) = \begin{cases} 0 & 1\leq x<i \\
1 & i=x\\
1/i & i<x \end{cases}$$
The flea's average lifetime is therefore $$\mathbb{E}\left(\sum_{n=0}^\infty 1_{[X_n>1]}\,\bigg|\, X_0=N\right)=\sum_{i>1} f_i(N) = {1\over 2}+{1\over 3}+\cdots+{1\over N-1}+1+0+0+\cdots.$$
From what I found I must assume the flea is initially on vertex $N$, in order that the expected lifetime comes out $\sum_{i=1}^{N-1} \frac1i.$ For each $k$ between $1$ and $N$ let $e(k)$ be the expected life of the flea, given it starts at vertex $k$. Then clearly we want $e(1)=0$ (immediate death, expected lifetime $0$), while also $e(2)=1$ since the flea gets only the one jump to death at vertex $1$. In general, suppose the flea is presently on vertex $k>1$. Then he gets with certainty his first jump, so that $e(k)=1+...$. His next jump being to one of the previous $k-1$ vertices with equal probability, we can see the relation $$e(k)=1+[e(1)+e(2)+\cdots +e(k-1)]/(k-1). \tag{1}$$ This gives the $e(k)$ recursively, and we find e.g. $e(3)=3/2,\ e(4)=11/6,\ e(5)=25/12.$ It so happens that these fractions match the results of summing the first $k-1$ reciprocals of natural numbers $1/1+1/2+\cdots+1/(k-1).$
So "all that's left" is to show that, provided we define the $e(k)$ by these reciprocal sums, then the $e(k)$ also satisfy the initial $e(1)=0$ [this works since an empty sum is $0$ by definition] as well as the recurrence equation $(1)$. I have filled some pages trying to do that with no immediate success, and have also tried to do it with generating functions, using the taylor expansion of $g(x)=-x \ln(1-x)/(1-x)$ whose coefficient of $x^n$ is the sum of the first $n-1$ terms of the harmonic series, but no luck so far.
Proof of recursion formula As suggested, define $s(k)=\sum_{j=1}^{k-1} \frac1j .$ It will be more convenient to state the recursion formula as $$s(n+1)=1+\frac1n \sum_{k=1}^n s(k).$$ Substituting for $s(k)$ here the above formula gives the following double sum for $s(n+1):$ $$s(n+1)=1+\frac1n \sum_{k=1}^n \sum_{j=1}^{k-1} \frac1j .$$ The key now is to reverse the order of summation. The restrictions imposed by the sum are that $1 \le j < k \le n$, and to reverse, we may take first $j$ going from $1$ to $n-1$, and then for any fixed $j$ the index $k$ ranges from $j+1$ to $n$. This means the re-written $s(n+1)$ becomes $$s(n+1)=1+\frac1n \sum_{j=1}^{n-1} \sum_{k=j+1}^{n} \frac1j .$$ Now the fraction $\frac1j$ is constant in the inner sum, where it appears $n-j$ times. So its contribution is $\frac{n-j}{j}=\frac nj -1.$ Thus the inner sum has been evaluated and we now have the single sum $$s(n+1)=1+\frac1n\sum_{j=1}^{n-1}[n/j-1].$$ Only a little algebra now brings this into the form $s(n+1)=1+1/2+\cdots +1/n$, completing the inductive proof that the defined formulas $s(n)$ in terms of the partial harmonic sums must agree with the values of $s(n)$ viewed as expected life spans of the flea if it starts at the vertex $n$ (see above for this part).