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.

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

Solving a set of recurrence relation:

$a_n=3b_{n-1} , b_n=a_{n-1}-2b_{n-1}$

In addition, It's known that: $a_1=2, b_1=1$.

So i started by isolating $b_n \to b_n=3b_{n-2}-2b_{n-1}$

So i get the current equation: $x^2+2x-3=0 \to(x+3)(x-1)=0$, Which means $b(n)=A_1+A_2(-3)^n$

So what now? I found an equation with 2 parameters but only 1 relating b: $b_1=1$.

Can i use $a_1=2$ aswell on the found equation?

share|cite|improve this question
You are doing fine. See the answer for the completion of your answer. – Mhenni Benghorbal May 6 '13 at 23:55
up vote 1 down vote accepted

Define generating functions $A(z) = \sum_{n \ge 0} a_{n + 1} z^n$ and similarly $B(z)$. Write your recurrences as: $$ \begin{align*} a_{n + 1} &= 3 b_n \\ b_{n + 1} &= a_n - 2 b_n \end{align*} $$ By properties of generating functions, your recurrences translate to: $$ \begin{align*} \frac{A(z) - a_1}{z} &= 3 B(z) \\ \frac{B(z) - b_1}{z} &= A(z) - 2 B(z) \end{align*} $$ Thus: $$ \begin{align*} A(z) &= \frac{2 + 7 z}{1 + 2 z - 3 z^2} = \frac{9}{4} \frac{1}{1 - z} - \frac{1}{4} \frac{1}{1 + 3 z} \\ B(z) &= \frac{1 + 2 z}{1 + 2 z - 3 z^2} = \frac{3}{4} \frac{1}{1 - z} + \frac{1}{4} \frac{1}{1 + 3 z} \end{align*} $$ Everything in sight is a geometric series: $$ \begin{align*} a_{n + 1} &= \frac{9}{4} - \frac{1}{4} (-3)^n \\ b_{b + 1} &= \frac{3}{4} + \frac{1}{4} (-3)^n \end{align*} $$

share|cite|improve this answer
(-1) This does not address the question, which is about a specific problem the user encountered when solving this problem. Sure, it's a complete solution to the whole assignment that completely ignores the user's own work, but JiminP's answer is much more to the point. – TMM May 6 '13 at 12:24
@TMM, if OP runs into a dead end, I consider showing an expedite path is more fruitful than helping them figure out how to batter down the wall. – vonbrand Apr 15 '14 at 12:04

Hint: You can calculate $b_2$ directly.

share|cite|improve this answer
Nice one, Funny that i didn't notice it. – StationaryTraveller May 6 '13 at 12:18

You are doing fine. You have

$$ b(n)=A_1+A_2(-3)^n. $$

Now, to determine $A_1$ and $A_2$, you need two initial conditions $b_1$ and $b_2$. Already, you have got one which is $b_1$. To find $b_2$ use the second equation

$$ b_n=a_{n-1}-2b_{n-1} \implies b_2 = a_1-2b_1 =2-2=0 \implies b_2=0. $$

Now, you can advance.

share|cite|improve this answer

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.