Zero-seeking device on a uniform distribution This is a surprisingly difficult problem in a stochastic processes textbook that I'm reading. It's meant to be solved through a Markov chain.

A zero-seeking device operates as follows: If it is in state $m$ at time $n$, then at time $n+1$, its position is uniformly distributed over the states $0,1,\ldots,m-1$. Find the expected time until the device first hits zero starting from state $m$.

My first instinct for solving this problem was to use first-step analysis. Such an approach led me to a sequence of $m+1$ linear equations. Let $v_i = \mathbb{E}(X_{T}=0|X_0=m)$. Then we have the following:
$$v_m = \frac{1}{m}v_{m-1}+\frac{1}{m}v_{m-2}+\ldots+\frac{1}{m}v_{1}+1$$
$$v_{m-1}=\frac{1}{m-1}v_{m-2} + \frac{1}{m-1}v_{m-3}+\ldots+\frac{1}{m-1}v_1+1$$
$$\vdots$$
$$v_1=1$$
$$v_0=0$$
I've tried approaching this problem by implementing the differenced expectation, $\nabla v_i=v_i-v_{i-1}$, but that didn't lead me anywhere. I also see that we can build up the individual $v_i$s starting from $v_1$, but I don't know how to evaluate $v_m$ for some arbitrary $m$. How would you guys approach this problem?
Edit: Ok I heard from my professor that the correct way to approach this problem was to recognize that $v_m = \frac{1}{m} + v_{m-1}$. Now my question is this how I'm ever supposed to come to that realization. It doesn't seem obvious from the equations below.
 A: Let $T$ be the hitting time of $0$. Let $v_m = E[T \mid X_0=m]$. (I think you had a typo when setting this up.)
You have the base case $v_0 = 0$, and for $m > 0$ you have
$$v_m = E[T \mid X_0 = m] = \sum_{k=0}^{m-1} E[T \mid X_0=m, X_1=k] P(X_1 = k \mid X_0 = m)
= \frac{1}{m} \sum_{k=0}^{m-1} (1 + v_k)
= 1 + \frac{1}{m} \sum_{k=0}^{m-1} v_k.$$
Some rearranging yields
\begin{align}
v_m &= \frac{1}{m} v_{m-1} + 1 + \frac{1}{m} \sum_{k=0}^{m-2} v_k
\\
&= \left(\frac{1}{m} + \frac{1}{m(m-1)} \sum_{k=0}^{m-2} v_k\right) + 1 + \frac{1}{m} \sum_{k=0}^{m-2} v_k
\\
&= \frac{1}{m} + 1 + \frac{1}{m-1} \sum_{k=0}^{m-2} v_k
\\
&= \frac{1}{m} + v_{m-1},
\end{align}
which is your professor's hint.
A: You can set it up as a difference equation with a time-varying non-homogeneous part. I can't find a good closed form for the solution, but you can express it as a sum of $m$ terms. Consider two cases: either $X_1=m-1$, or $X_1<m-1$.
A: If $$v_m = \frac{1}{m} \left(v_{m-1} + \cdots + v_1\right) + 1,$$ then $$m( v_m - 1) = v_{m-1} + \cdots + v_1,$$ hence
$$m(v_m - 1) - (m-1) (v_{m-1} - 1) = (v_{m-1} + \cdots + v_1) - (v_{m-2} + \cdots + v_1) = v_{m-1}.$$
This yields
$$mv_m = (m-1)v_{m-1} + v_{m-1} + 1 = vm_{m-1} + 1,$$
thus
$$v_m = v_{m-1} + \frac{1}{m},$$
as claimed.
