Solving a set of recurrence relation:

Question

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?

Answer 1

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

Answer 2

Hint: You can calculate $b_2$ directly.

Answer 3

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.