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

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