Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

The characteristic equation is

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

share|improve this answer
    
Yes, a little more algebraic manipulation of the characteristic equation yields the result. Silly me... –  Gadi A Jun 25 '11 at 18:35
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.