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.
$\endgroup$5 Answers
$\begingroup$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.)
$\endgroup$ $\begingroup$Write the system in matrix form. Then try to diagonalize the matrix.
$\endgroup$ $\begingroup$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.
$\endgroup$ 2 $\begingroup$Write without subtractions in indices (I like lovercase letters for members of the sequences, please bear with me): \begin{align} a_{n + 1} &= b_n + c_n \\ b_{n + 1} &= a_{n + 1} + c_n \\ c_{n + 1} &= b_{n + 1} + c_n \\ d_{n + 1} &= e_n + g_n \\ e_{n + 1} &= d_{n + 1} + f_n \\ f_n &= g_n + c_n \\ g_{n + 1} &= e_{n + 1} + f_n \end{align} Define a slew of generating functions like $A(z) = \sum_{n \ge 0} a_n z^n$, multiply each recurrence by $z^n$ and sum over $n \ge 0$, then recognize e.g. $$ \sum_{n \ge 0} a_{n + 1} z^n = \frac{A(z) - a_0}{z} $$ This sets up a beautiful linear system of equations for the generating functions, which your tame computer algebra system (in my case maxima) solves for you: $$ E(z) = \frac{e_0 + (c_0 - 7 e_0 + 2 g_0) z + (b_0 + 13 e_0 - 8 g_0) z^2 + (b_0 - c_0 - 3 e_0 + 2g_0) z^3} {(1 - 4 z + z^2)^2} $$ Split into partial fractions (this gets ugly, zeros of the denominator are $2 \pm \sqrt{3}$) and use the generalized binomial theorem to read off the coefficients.
$\endgroup$ $\begingroup$@utdiscant: Did you solve it yet? Please show me your methods because I also met a similar problem above.
$\left\{\begin{matrix}
S_{n}=S_{n-1}+T_{n-1}\\
T_{n-1}=C_{n-3}+D_{n-4}\\
C_{n-3}=E_{n-4}+F_{n-4}\\
E_{n-4}=K_{n-5}+T_{n-5}\\
F_{n-4}=E_{n-7}+D_{n-7}\\
D_{n-7}=H_{n-8}+F_{n-8}\\
H_{n-8}=S_{n-11}+C_{n-11}\\
K_{n-5}=S_{n-7}+C_{n-8}
\end{matrix}\right.$
Now, I'm trying to solve it by matrix form but it is so hard. Particularly, find generating matrix and characteristic polynomial.
