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$.

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!
