4
$\begingroup$

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?

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

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

$\endgroup$
2
  • $\begingroup$ (-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. $\endgroup$ – TMM May 6 '13 at 12:24
  • $\begingroup$ @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. $\endgroup$ – vonbrand Apr 15 '14 at 12:04
5
$\begingroup$

Hint: You can calculate $b_2$ directly.

$\endgroup$
1
  • $\begingroup$ Nice one, Funny that i didn't notice it. $\endgroup$ – StationaryTraveller May 6 '13 at 12:18
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.