# Solving a set of recurrence relations

I have the 7 following reccurence relations:

$A_n = B_{n-1} + C_{n-1}$

$B_n = A_n + C_{n-1}$

$C_n = B_n + C_{n-1}$

$D_n = E_{n-1} + G_{n-1}$

$E_n = D_n + F_{n-1}$

$F_n = G_n + C_n$

$G_n = E_n + F_{n-1}$

which I would like to solve, with the goal of eventually finding an explicit form of $E_n$. I started out by looking at only $A_n$, $B_n$ and $C_n$, and found a formula for $A_n$.

$A_n = 1/3 \sqrt{3} (2+ \sqrt{3})^n - 1/3 \sqrt{3} (2 - \sqrt{3})^n$

but I cant seem to find the right trick this time.

-

Substitute and eliminate. You already know how to solve a recurrence on one function; eliminate functions from the system until you get to only one, by substituting one function for another.

For example, substitute $B_{n-1}$ into the definition of $C_n$ to get $$C_n = A_{n-1} + C_{n-2} + C_{n-1}.$$ $B$ has been eliminated, and we're one step closer to having an equation involving just $C$.

By inspection, $A$, $B$, and $C$ are mutually defining, and separately $D$, $E$, $F$, $G$ are mutually defining except for $C$. So solve for $C$ first, using $A$ and $B$, then continue on with just $D$, $E$, $F$, $G$.

This is very similar to Gaussian elimination, but you have the extra subscripts to deal with in $C_{n-1}$, $C_{n-2}$, etc.

-
I have been trying this approach for a while now, but I do not seem to be getting any closer to a solution. The problem is when I have two equations left, then they could be for example: E_n = 2E_{n-1} + F_{n-2} and F_n = E_n + F_{n-1} + C_n. Here I need to eliminate F, but since the equation have both F_n and F_{n-1} I can't simply do this. – utdiscant Feb 12 '11 at 21:32
From that last relation for $F_n$ you can 'solve' for $E$ (in terms of $F$ and $C$, then substitute into the first relation. Then you'll have a relation on just $F$ and $C$. Since you already have a complete non-recursive solution for $C$, you'll be able to solve for $F$. – Mitch Feb 12 '11 at 21:39

Here's what I would do:

let $A(z) = \sum_{n=0}^\infty A_n z^n$ be the generating function'' of $A_n$. Define $B(z), C(z)$.

Then multiply the recurrence $A_n = B_{n-1} + C_{n-1}$ by $z^n$ to get

$$A_n z^n = B_{n-1} z^n + C_{n-1} z^n$$

and sum over $z^n$ to get

$$\sum_{n=1}^\infty A_n z^n = \sum_{n=1}^\infty B_{n-1} z^n + \sum_{n=1}^\infty C_{n-1} z^n.$$

The left-hand side is $A(z) - A_0$ and the right-hand size is $z B(z) + z C(z)$; so you get $A(z) - A_0 = zB(z) + zC(z)$. Notice that I had to write $A(z) - A_0$ because you have not provided the initial conditions.

You can do the same with the second and third equations and solve the resulting three-by-three system, which shouldn't be too hard. This will give you $A(z)$. Now you just need to find the coefficients in $A(z)$; you can do this by writing $A(z)$ in terms of partial fractions. For a written-out example of this, see Section 1.3 of generatingfunctionology by Wilf. (Link goes to the full text, available online.)

-

Write the system in matrix form. Then try to diagonalize the matrix.

-