# Help me solve this recurrence relation

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.

-
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
mtholyoke.edu/~mnoonan/smi/gf.pdf 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

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