This is exercise 2 from Section 3.9 of Probability and Random Processes by Grimmett and Stirzaker:
For a simple random walk $S$ with absorbing barriers at 0 and $N$, let $W$ be the event that the particle is absorbed at 0 rather than at $N$, and let $p_k = P(W|S_0 = k)$. Show that, if the particle starts at $k$ where $0 < k < N$, the conditional probability that the first step is rightwards, given $W$, equals $p p_{k+1}/p_k$. Deduce that the mean duration $J_k$ of the walk, conditional on $W$, satisfies the equation $$ p p_{k+1}J_{k+1} - p_k J_k + (p_k - p p_{k + 1}) J_{k - 1} = -p_k, \hspace{1cm} \mathrm{for\ } 0 < k < N. $$ Show that we may take as boundary condition $J_0 = 0$. Find $J_k$ in the symmetric case, when $p = 1/2$.
I was able to derive the difference equation as required, and also show that $p_k = 1 - k/N$ for the symmetric case. The difference equation then becomes $$ (N - k - 1)J_{k+1} - 2(N-k)J_k + (N - k + 1)J_{k - 1} = -2N + 2k, $$ for the symmetric case.
To derive an explicit formula for $J_k$ I had to resort to a computer simulation with $N = 10$ and plot $J_k$ as a function of $k$. This resulted in a graph which looked like a quadratic curve with maximum at $k$. So I guessed a solution of the form $A + B (N - k) + C (N - k)^2$ and was able to deduce from the boundary condition $J_0 = 0$, the constraint that the maximum is at $N = k$, and the difference equation itself that $A = N^2/3$, $B = 0$, and $C = -1/3$ which resulted in the formula $J_k = N^2 /3 - (N - k)^2 / 3$. The formula seems to agree with the computer simulations for $N = 10$ and a few other values of $N$ that I've tried.
My question is, how I can be sure that my guess is correct? I've seen various articles on the web and books (including the book in which this exercise appears in) where similar difference equations have been derived and the form of the solution has been plucked out of thin air as a guess. How can one be sure that the guesses are correct?
One approach is to simplify the recurrence relation to one that has constant coefficients. Define $Y_k = (N-k)J_k$ for $k=0,1,\ldots$. Then the relation becomes
$$Y_{k+1} - 2Y_k + Y_{k-1} = 2k-2N \qquad\qquad\qquad\qquad(1)$$
This is a linear non-homogeneous recurrence relation so we can use standard methods to solve it. Its characteristic equation is
$$0=r^2-2r+1 = (r-1)^2.$$
So $r=1$ is a double-root and the solution to the homogenous version of $(1)$ has form $A + Bk$.
For a particular solution to the non-homogeneous relation, note that RHS of $(1)$ has the same form as $A+Bk\;$ so we should try a particular solution of form $Y_k=Ck^2+Dk^3$. Substitute this into $(1)$ to give
\begin{align} 2k-2N &= C(k+1)^2 + D(k+1)^3 - 2Ck^2 - 2Dk^3 + C(k-1)^2 + D(k-1)^3 \\ &= 2C + 6Dk \\ \therefore\quad C=-N,\quad & D=1/3. \end{align}
So the general solution is: $Y_k=A+Bk-Nk^2+\frac{1}{3}k^3.$ Our boundary conditions are $Y_0=0$ and $Y_N=0$, and these imply that $A=0$ and $B=\frac{2}{3}N^2$. So we have
\begin{align} Y_k &= \frac{2}{3}N^2k - Nk^2 + \frac{1}{3}k^3 \\ \therefore\quad J_k &= Y_k/(N-k) \\ &= \frac{k}{3}(2N-k). \end{align}