Solving a difference equation (Gambler's ruin)

Question

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

Answer 1

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

Answer 2

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