# Solving a difference equation (Gambler's ruin)

I want to solve following difference equation:

$a_i = \frac13a_{i+1} + \frac23a_{i-1}$, where $a_0=0$ and $a_{i+2} = 1$

My approach: Substituting $i=1$ in the equation,
$3a_1 = a_2 + 2a_0$
$a_2 = 3a_1$
Similarly substituting $i = 2, 3 ...$
$a_3 = 7a_1$
$a_4 = 15a_1$
...

Generalizing,
$a_i = (2^i - 1)a_1$

I am not sure how to get rid of $a_1$ to get the final answer of $\frac{(2^i - 1)}{(2^{2+i} - 1)}$

• Hint: write it as $\,a_{n+1} = 3 a_n - 2a_{n-1} \iff a_{n+1} -a_{n} = 2( a_n - a_{n-1})\,$, so $\,a_{n+1} -a_{n}\,$ is a geometric progression with common ratio $\,2\,$. Find $\,a_{n+1} -a_{n}\,$, then find $\,a_n\,$ by telescoping, then use the boundary conditions to determine the constants. – dxiv Mar 1 '18 at 0:02
• Thank @dxiv . GP gives $a_{i+1} -a_i = 2^ia_1$. Or, $a_{i+2} -a_{i+1} = 2^{i+1}a_1$. Or, $a_i = 1-2^ia_1$. This is somehow different from what I got above. I have already applied both boundary conditions. – Gerry Mar 1 '18 at 20:54
• GP gives ... No, that should rather be $\,a_{n+1}-a_{n}=2^n(a_1-a_0)\,$. Then, by telescoping, $a_{n+1}-a_{0}=(2^n+2^{n-1}+\ldots+2^1 + 1)(a_1-a_0)=\ldots$ – dxiv Mar 2 '18 at 0:22

## 2 Answers

The standard method to solve recurrence equations is to set as trial solution

$$a_i=x^i \implies x^i = \frac13x^{i+1} + \frac23 x^{i-1}\implies x =\frac13 x^2+\frac23\implies x^2-3x+2=0$$

then find $x_1$ and $x_2$ then the general solution is

$$x_i = ax_1^i+bx_2^i$$

with $a$ and $b$ determined by initial conditions.
Solving, $x_1=1, x_2=2$
Substituting, $x_i = a + 2^ib$
Using boundary conditions and solving through, $a = \frac{-1}{(2^{i+2}-1)}$ and $b = \frac{1}{(2^{i+2}-1)}$
Plugging back these into general solution equation and rearranging: $a_i = \frac{(2^{i}-1)}{(2^{i+2}-1)}$

• Well done! then my hint was useful! – user Mar 1 '18 at 21:06
• Thanks gimusi. This is very helpful – Gerry Mar 1 '18 at 22:05
• @Gerry I'm very happy for that., Thanks, Bye. If you want a good reference take also a look here youtube.com/watch?v=PNrqCdslGi4 – user Mar 1 '18 at 22:08

If you proceed this way, $a_1$ is an unknown, to be solved for by substituting in the boundary condition at the other endpoint and solving for $a_1$. (This is actually a fairly common trick, for instance it is also used to derive the invariant distribution of a birth-death process by writing all the $\pi_i$'s in terms of $\pi_0$ and then choosing $\pi_0$ based on the normalization requirement.)