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'm trying to solve the recurrence relation

$$a_n = (\lambda +\mu)a_{n+2}+\mu a_{n+3}.$$

with initial relationships of:

$\lambda a_1 = \mu a_2$

$(\lambda +\mu)a_2 = \mu a_3.$

I found a site online which suggests using the roots of a, in this case, cubic polynomial to solve it, but the roots are of course really complex and since I don't know what $\lambda$ and $\mu$ are they don't simplify very much. Is there another way to go about this? Thanks.

share|cite|improve this question
My first guess would be to try using generating functions. Have you tried that? – Alex Wertheim May 24 '13 at 0:24
I haven't and unfortunately I'm a novice at combinatorics, is there a good site to learn this real quick? – esproff May 24 '13 at 0:25 looks like a good resource. However, what is the context of the problem? If this is for a class and generating functions haven't been mentioned, for example, that might suggest that there is an easier way to do this. Generating functions were my first inclination after the standard characteristic polynomial but that might be using a sledgehammer on a nail. – Alex Wertheim May 24 '13 at 0:30
It's for a class on stochastic processes, this is just one step in a larger problem, so who knows what's required to solve it. – esproff May 24 '13 at 0:31
I don't think generating functions are going to work as for finite recurrences they just reduce to the polynomial trick. – esproff May 24 '13 at 1:16
up vote 1 down vote accepted

For completeness, add $a_0$. Setting up the recurrence for $n = 0$ gives: $$ \begin{align*} \mu a_3 + (\lambda + \mu) a_2 &= a_0 \\ 2 (\lambda + \mu) a_2 &= a_0 \\ \end{align*} $$ This gives enough to get the recurrence going: $$ \begin{align*} a_1 &= \frac{a_2}{\lambda} = \frac{a_0}{2 \lambda (\lambda + \mu)} \\ a_2 &= \frac{a_0}{2 (\lambda + \mu)} \end{align*} $$ Whatever you do, the result will be the same, unless you change the constants to simplify the recurrence. Use Wilf's "generatingfunctionology" techniques. Define $A(z) = \sum_{n \ge 0} a_n z^n$. From the recurrence: $$ \mu \frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} + (\lambda + \mu) \frac{A(z) - a_0 - a_1 z}{z^2} = A(z) $$ Solving for $A(z)$ gives a rather horrible expression: $$ A(z) = \frac{a_0}{2 \lambda (\lambda + \mu)} \frac{2 \lambda^2 \mu + 2 \lambda \mu^2 + (2 \lambda^3 + 4 \lambda^2 \mu + 2 \lambda \mu^2 + \lambda \mu + \mu) z + (\lambda + \mu) z^2} {\mu + (\lambda + \mu) z - z^3} $$

share|cite|improve this answer
You can of course extract the $n$th coefficient of $A(z)$ by using partial fraction decomposition. But this requires finding the roots of a cubic polynomial over $\mathbb{C}$, which is exactly what the OP wanted to avoid :D – 6005 May 29 '13 at 4:45
@Goos, whatever OP does it will turn out equivalent to pulling the roots... – vonbrand May 29 '13 at 11:39

The site online probably wanted you to write $$ \mu \left[ \begin{array}{c} a_{n+3} \\ a_{n+2} \\ a_{n+1} \end{array} \right] = \left[ \begin{array}{ccc} -\lambda - \mu & 0 & 1 \\ \mu & 0 & 0 \\ 0 & \mu & 0 \end{array} \right] \left[ \begin{array}{c} a_{n+2} \\ a_{n+1} \\ a_{n} \end{array} \right] $$ and then diagonalize the matrix using eigenvalues to compute a general formula. This is extremely gross, but I don't see any better way.

share|cite|improve this answer

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.