Gambler's ruin recursive solution Suppose we have 2 players A and B, A starting with $a$ coins and B starting with $n-a$ coins. Assuming every game is independent, every time A wins, they win $2$ coins and every time they lose they lose 1 coin. What is the probability that A wins the game ?
I can solve this using a difference equation, but I was wondering if there is a way to write down the recurrence equation in a way that you can solve this without using difference equations. So far I could only come up with the following:
Considering $W_{a}$ the probability of A winning the game given they start with a coins.
Boundary equations are $W_{0} = 0$ and $W_{N} = 1$
$$W_{a} = pW_{a+2} + qW_{a-1}$$
$$(p+q)W_{a} = pW_{a+2} + qW_{a-1}$$
$$p(W_{a+2} - W_{a}) = q(W_{a} - W_{a-1})$$
$$W_{a+2} - W_{a} = \frac{q}{p}(W_{a} - W_{a-1})$$
If you extend this to a few terms, you can notice:
$$W_{3} - W_{1} = \frac{q}{p}(W_1 - W_0)$$
$$W_{4} - W_{2} = \frac{q}{p}(W_2 - W_1)$$
$$W_{5} - W_{3} = \frac{q}{p}(W_3 - W_2)$$
$$...$$
$$W_{a} - W_{a-2} = \frac{q}{p}(W_{a-2} - W_{a-3})$$
$$W_{a+1} - W_{a-1} = \frac{q}{p}(W_{a-1} - W_{a-2})$$
$$W_{a+2} - W_{a} = \frac{q}{p}(W_{a} - W_{a-1})$$
If you sum everything up, the terms cancel out and you're left with:
$$W_{a+2} + W_{a+1} - W_{2} - W_{1} = \frac{q}{p}W_{a}$$
Is there a way to find $W_{a}$ out of this or the difference equation is the only way to solve this ?

(Note that we need $W_{n + 1} = 1$ as an additional boundary condition.)
Your idea is good; I’ll write it more compactly as follows:
$$0 = \sum_{i=1}^a (W_i - pW_{i+2} - qW_{i-1}) = pW_1 + pW_2 + qW_a - pW_{a+1} - pW_{a+2}.$$
We can generalize it by throwing in a $c^i$ coefficient, where $c$ is any root of $p - c^2 + c^3q = 0$ so that the sum still telescopes:
\begin{multline*}
0 = \sum_{i=1}^a c^i (W_i - pW_{i+2} - qW_{i-1}) \\
= \frac{p}{c}W_1 + pW_2 + qc^{a+1}W_a - pc^{a-1}W_{a+1} - pc^aW_{a+2}.
\end{multline*}
Knowing one root $c = 1$, we can factor $p - c^2 + c^3q = (1 - c)(p + cp - c^2q)$ to find the other two roots. This gives us three linear equations in five unknowns $W_1, W_2, W_a, W_{a+1}, W_{a+2}$. If we substitute $a = n - 1$, we can use our knowledge of $W_n = W_{n+1} = 1$ to solve for $W_1, W_2, W_{n-1}$. Then for general $a$, we can use our knowledge of $W_1, W_2$ to solve for $W_a, W_{a+1}, W_{a+2}$.
