Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following recurrence relation:



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|cite|improve this question
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|cite|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
@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


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.