Solving recursion (Gambler's ruin) 
Let $M_{i}$ denote the mean number of games until the gambler either goes broke or reaches a fortune of $N$, given that he starts with $i = 0,1,\ldots,N$.

I have shown that
$M_{0} = M_{N} = 0$ and $M_{i} = 1 + pM_{i+1} + qM_{i-1}$ for $i=1,\ldots,N-1$
I want to solve these equations to obtain
$$M_{i} = i(N-i)$$if $p=1/2$
or
$$M_{i} = \frac{i}{q-p} - \frac{N}{q-p}\cdot\frac{1 - (q/p)^{i}}{1- (q/p)^{N}}$$
if $p \neq 1/2$. 
I've tried verifying by direct substitution, but I don't think I'm substituting correctly. How can I solve these difference equations to show the desired result?
 A: Let $X_0=i$ and $\{X_n\}$ be iid with $\mathbb P(X_1=1)=1-\mathbb P(X_1=-1)=p$. Let $$S_n = \sum_{k=0}^n X_k $$ be the gambler's wealth at time $n$ and $$\tau=\inf\{n: S_n\in\{0,N\}\} $$ be the time until he stops. Define $$Z_n = \left(\frac qp\right)^{S_n}. $$
Then
\begin{align}
\mathbb E[Z_{n+1}\mid \mathcal F_n] &= \mathbb E\left[\left(\frac qp\right)^{S_n+X_{n+1}}\mid\mathcal F_n \right]\\
&= \left(\frac qp\right)^{S_n} + \left(\frac qp\right)^{-1}\mathbb P(X_{n+1}=-1) + \left(\frac qp\right)^1\mathbb P(X_{n+1}=1)\\
&= Z_n + \left(\frac pq\right)q + \left(\frac qp\right)p\\
&= Z_n + p + q\\
&= Z_n,
\end{align}
so that $Z_n$ is a martingale. Then by the optional stopping theorem we have
$$\mathbb E[Z_\tau] = \mathbb E[Z_0] = \left(\frac qp\right)^i. $$ It follows that
\begin{align}\mathbb E[Z_\tau] &= \left(\frac qp\right)^0\mathbb P(Z_\tau=0) + \left(\frac qp\right)^N\mathbb P(Z_\tau=N)\\
&= \mathbb P(Z_\tau=0) + \left(\frac qp\right)^N (1-\mathbb P(Z_\tau=0) )\\
&= \left(\frac qp\right)^i,\end{align}
and so
\begin{align} \mathbb P(Z_\tau=0) &= \frac{\left(\frac qp\right)^i - \left(\frac qp\right)^N}{1-\left(\frac qp\right)^N},\\
\mathbb P(Z_\tau=N) &= \frac{1 - \left(\frac qp\right)^i}{1-\left(\frac qp\right)^N}.\\
\end{align}
Therefore the gambler's expected total winnings are
\begin{align}
\mathbb E\left[\sum_{n=1}^\tau X_n \right] &= \mathbb E[S_\tau] - S_0\\
&= \mathbb E[S_\tau\mid Z_\tau=0]\mathbb P(Z_\tau=0) + \mathbb E[S_\tau\mid Z_\tau=N]\mathbb P(Z_\tau=N) - i\\
&= N\left(\frac{1 - \left(\frac qp\right)^i}{1-\left(\frac qp\right)^N}\right)-i
\end{align}
By Wald's identity, we have
$$\mathbb E\left[\sum_{n=1}^\tau X_n \right] = \mathbb E[\tau]\mathbb E[X_1], $$
and so $$\mathbb E[\tau] = \frac1{p-q}\left[N\left(\frac{1 - \left(\frac qp\right)^i}{1-\left(\frac qp\right)^N}\right)-i\right], $$
when $p\ne q$.
A: The recurrence relation
$$pM_{i+1} - m_i +qM_{i-1} = -1 \qquad\qquad (1)$$
is a non-homogeneous, second-order, linear recurrence relation with constant coefficients ($p,-1,q$) and can be solved by finding its "characteristic equation" as described here or here or in most texts on discrete mathematics.
Initially, consider the homogeneous relation
$$pM_{i+1} - m_i +qM_{i-1} = 0. \qquad\qquad (2)$$
The characteristic equation is $pr^2 - r + q = 0$ giving roots: $\;r=1 \text{ or } q/p$.
$$\\$$
Case $p=q$:
We have a double root $r=1$ so the general solution to $(2)$ is 
$$M_i = A + Bi\qquad\qquad (3)$$
The particular solution for $(1)$ would normally have form $M_i=C$ because RHS $(1)$ is constant, but in view of $(3)$ we instead try $M_i = Ci^2$ and substitute this into $(1)$ to give
$$-1 = pC(i+1)^2 - Ci^2 + qC(i-1)^2 = C \qquad\text{using $p=q=1/2$}.$$
So our particular solution is $M_i=-i^2$ and our general solution to $(1)$ is $M_i = A+Bi-i^2$.
$M_0 = 0 \implies 0=A.$
$M_N = 0 \implies 0 =BN-N^2\;$ so $\;B=N$.
So the solution to $(1)$ is
$$M_i = Ni-i^2.$$
$$\\$$
Case $p\neq q$:
We have distinct roots $r=1,\; q/p\;$ so the general solution to $(2)$ is 
$$M_i = A + B\left(q/p\right)^i \qquad\qquad (4)$$
Here we try the particular solution $M_i = Ci$ and substitute this into $(1)$ to give
$$-1 = pC(i+1) - Ci + qC(i-1) = C(p-q).$$
Therefore, $\; C=1/(q-p)\;$ and our general solution to $(1)$ is $M_i = A + B\left(q/p\right)^i + \dfrac{i}{q-p}$.
$M_0 = 0 \implies 0=A + B\;$ so $\;A=-B.$
$M_N = 0 \implies 0 = -B + B\left(q/p\right)^N + \dfrac{N}{q-p}\;$ so $\;B=\dfrac{N}{q-p}\cdot \dfrac{1}{1-\left(q/p\right)^N}$.
So the solution to $(1)$ is
\begin{align}
M_i &= - \dfrac{N}{q-p}\cdot \dfrac{1}{1-\left(q/p\right)^N} + \dfrac{N}{q-p}\cdot \dfrac{\left(q/p\right)^i}{1-\left(q/p\right)^N} + \dfrac{i}{q-p} \\
& \\
&= \dfrac{i}{q-p} - \dfrac{N}{q-p}\cdot \dfrac{1-\left(q/p\right)^i}{1-\left(q/p\right)^N}.
\end{align}
