# Solving a simple recurrence relation

I have the following recurrence relation:

$a_0=1$

$a_{n}=pa_{n+1}+qa_{n-1}$

Where $p+q=1$. This relation arises in analyzing a "gambler's ruin" situation.

It is claimed that the general solution is $A+B(q/p)^i$ but I fail to see why (trying the usual method of solving the characteristic equation does not seem to work for me).

Also, and this is maybe even more interesting to me - what is the solution if the relation is finite, i.e. if we have $a_{k}=a_{k-1}$ for some $k$ and onwards?

-

$$x = px^2 + q$$
which indeed has roots $1$ and $\dfrac{q}{p}$.
If we have $a_k = a_{k-1}$ form certain point onwards, then apply the formula to terms before the turning point and pick the last term to which the formula applies to the rest.
@Gadi: A simple way to see that: $x=1$ is a root. Product of roots is $\frac{q}{p}$ (constant/coefficient of x^2), so other root is $\frac{q}{p}$. No manipulations required. –  Aryabhata Jun 25 '11 at 18:37