# Solving a set of recurrence relation:

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?

• You are doing fine. See the answer for the completion of your answer. – Mhenni Benghorbal May 6 '13 at 23:55

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*}

• (-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.

• 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.$$