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'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|improve this question
1  
My first guess would be to try using generating functions. Have you tried that? –  AWertheim 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? –  Ron Jeremy 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. –  AWertheim 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. –  Ron Jeremy 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. –  Ron Jeremy May 24 '13 at 1:16

2 Answers 2

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|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 –  Goos 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|improve this answer

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.