Expected cover time for a line graph

Let G be a line graph, so V = {1, 2, 3, ..., n} and E = {(1, 2), (2, 3), (3, 4), ..., (n-1, n)}

Let e_i = h_i1 be the expected number of steps for a random walk starting at vertex i to reach vertex 1

We need to solve the recurrence equations:

e₁ = 0
e_i = e_i-1/2 + e_i+1/2 + 1 for 1 < i < n
e_n = e_n-1 + 1

We can solve this by defining d_i = e_i - e_i-1, which results in the recurrence d_i+1 = d_i -2 for 2 < i < n. Applying the initial condition e₁ = 0 gives the solution d_i = e₂ - 2(i-2), which gives

e_i = (i-1)e₂ - i² + 3i -2

Plugging this into the third equation above and solving gives

e_i = (i - 1)(2n - 3) - i² + 3i - 2

This is monotonically increasing from 1 to n, and e_n = (n - 1)²

Reference: This is using techniques similar to those found in

Elementary probability Theory with Stochastic Pocesses
Kai Lai Chung
Springer-Verlag, 1974