Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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.)

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

@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.

share|cite|improve this answer
I ended up solving it in another way, by finding a different set (size 3) of recurrence relations which I could solve instead. – utdiscant Oct 2 '13 at 14:55
Could you share textbooks which talk about your method with me? – piglearnmaths Oct 3 '13 at 7:40
If you can get to a recurrence relation with only a single variable by substituting, you can for example use some of these tricks – utdiscant Oct 4 '13 at 11:05

Your Answer


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.