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?