recurrence solution to gambler's ruin From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$  given gambler is at $i$. 
$a_i = pa_{i+1} + (1 - p)a_{i-1} $
It's not clear from the text what steps are taken to solve for the general form $a_i$ (maybe Gaussian elimination). How do you solve the recurrence equation for $a_i$? If this can be found through the characteristic equation of a matrix $A$, then how do you construct $A$? As the problem is described, the first row has $a_0 = 0$, and last with $a_k = 1$.
 A: Hint: Rewrite our recurrence as 
$$pa_i+(1-p)a_i=pa_{i+1}+(1-p)a_{i-1}.$$
A little manipulation changes this to 
$$p(a_{i+1}-a_i)=(1-p)(a_i-a_{i-1}).$$
If $p \ne 0$, this can be rewritten as
$$a_{i+1}-a_i=\frac{1-p}{p}(a_i-a_{i-1}).$$
Let $b_i=a_i-a_{i-1}$. Then the $b_i$ satisfy the simple recurrence
$$b_{i+1}=\frac{1-p}{p}b_i.$$
A: We can rewrite the recurrence as $0=pa_{i+1} - a_i+(1-p)a_{i-1}$ and solve the characteristic equation $p\theta^{i+1}-\theta^i+(1-p)\theta^{i-1}=0.$ Ignoring $\theta=0$ we get $\theta=1,(1-p)/p.$ Thus, the probabilities satisfying the recurrence are of the form $a_i=c_1+c_2(\frac{1-p}{p})^i$ with $a_0=0$ and $a_k=1.$ Then we can solve the resulting system for $c_1,c_2.$ This link might help.

More explicitly: To find the roots of the characteristic equation of the recurrence, we solve $p\theta^2-\theta+(1-p)=0.$ We have two unique solutions $\theta_1=1,\theta_2=\frac{1-p}{p}.$ What the link tells us is that since these roots are distinct, the recurrence has general solution $a_i=c_1+c_2(\frac{1-p}{p})^i,$ where $c_1,c_2$ are constants. We can verify that $a_i=1^i=1$ is a solution, since $1=(p)(1)+(1-p)(1).$ Also, $$p(\frac{1-p}{p})^{i+1}+(1-p)(\frac{1-p}{p})^{i-1} = (\frac{1-p}{p})^i(1-p)+p(\frac{1-p}{p})^i=(\frac{1-p}{p})^i,$$ so indeed $(\frac{1-p}{p})^i$ is a solution.
Now, given $a_0=0$ and $a_k=1,$ we can solve for $c_1,c_2.$ First, $a_0 = 0$ implies $c_1+c_2(\frac{1-p}{p})^0=c_1+c_2=0$, or $c_1=-c_2.$ Second, $a_k=1$ implies $c_1-c_1(\frac{1-p}{p})^k=1,$ so $$c_1=\frac{1}{1-(\frac{1-p}{p})^k}=\frac{p^k}{p^k-(1-p)^k}.$$ We can see here that we should have $p\neq \frac{1}{2}.$
Thus, the solution should look something like: $$\frac{p^k}{p^k-(1-p)^k}-\frac{p^k}{p^k-(1-p)^k}(\frac{1}{1-p})^i.$$
I'm not sure I can help with a reference. To be honest, when I saw this in a class it was not well explained, and the text didn't help. Although maybe the wikipedia reference has something. Best of luck!
A: This is best solved using generating functions. Let $f(x) = \sum_{k=0}^\infty a_k x^k$. Now multiply the recurrence equation with $x^k$ and perform the summation:
$$
   f(x) - a_0 = \sum_{k=1}^\infty a_k x^k = \sum_{k=1}^\infty (p a_{k+1} + (1-p) a_{k-1}) x^k =
  \frac{p}{x} \sum_{k=1}^\infty  a_{k+1} x^{k+1} + (1-p) x \sum_{k=1}^\infty  a_{k-1}) x^{k-1} = \frac{p}{x} \left( f(x) - a_0 - a_1 x\right) + (1-p) x f(x)
$$
Now solve for $f(x)$:
$$
   f(x) = a_0 \frac{p-x}{(1-x)(1-(1-p)x)} + a_1 \frac{ p x}{(1-x)(1-(1-p)x)}  \\ = \left(\frac{\left(a_1-a_0\right) p}{1-\frac{1-p}{p} x}+\frac{a_0 (1-p)-a_1 p}{
   1-x}\right) \frac{1}{1-2p} \\ =
  \frac{1}{1-2p} \sum_{n=0}^\infty \left( \left(a_1-a_0\right) \frac{(1-p)^n}{p^{n-1}} + \left(a_0 (1-p)-a_1 p\right) \right)x^n \\
   = \sum_{n=0}^\infty  \left( a_0 \frac{p^{n-1}(1-p) - (1-p)^{n}}{(1-2p) p^{n-1}} + a_1 \frac{(1-p)^n - p^n}{(1-2p)p^{n-1}} \right) x^n
$$
where geometric series has been used. The case of $p =\frac{1}{2}$ requires taking a limit. Using L'Hospital's rule:
$$
     a_k\left(\frac{1}{2}\right) = a_1 n + a_0  (1-n) = a_0 + (a_1-a_0) n
$$
