expected life absorbing Markov Chain No idea on how to start this question. Any help would be much appreciated.
A ﬂea 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 ﬂea on day $n$. Show that the expected life of the flea is:
$$\sum_{i=1}^{N-1} \frac{1}{i}$$
 A: 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.$$
A: 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).
