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