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

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