9
$\begingroup$

If we have the two recurrence relations $$a_n = 3a_{n-1} + 2b_{n-1}$$ $$b_n = a_{n-1} + 2b_{n-1}$$ with $a_0 = 1$ and $b_0 = 2$.

My solution is that we first add two equations and assume that $f_n = a_n + b_n$. The result is $f_n = 4f_{n-1}$. This can be solved easily and the solution is $f_n = a_n + b_n = 4^nf_0=4^n(3)$. We subtract the two equations from each other and we get $a_n - b_n = 2a_{n-1}$. By adding these two results we get $2a_n = 2a_{n-1} +4^n (3) $.

$a_n = a_{n-1} + (3/2) 4^n$ is annihilated by $(E-1)(E-4)$. Thus, the Generic solution is $a_n = \sigma + \beta4^n$. The constants $\sigma, \beta$ satisfy the equations: $a_0 = 1 = \sigma + \beta$ and $a_1 = 7 = \sigma + 4\beta$. Thus, the final solution is $a_n = -1 + (2) 4^n$ and $b_n = 4^n + 1$. Is this right? Thank you!

$\endgroup$
  • $\begingroup$ is this for cs330 at IIT? $\endgroup$ – bs7280 Mar 12 '15 at 5:52
8
$\begingroup$

The procedure is right. There is no real need to wonder about correctness, since substituting the answers arrived at shows that they do satisfy the system.

Alternately, we can express the recurrence in matrix form, and use tools from linear algebra to find the solution.

For a lower level manipulation that works well, we can subtract as you did to get $$a_n-b_n=2a_{n-1},\quad\text{or equivalently}\quad b_n=a_n-2a_{n-1}.\tag{$1$}$$

Bump the indices in the first given recurrence to get $a_{n+1}=3a_n+2b_n$. Now use $(1)$ to substitute for $b_n$, and we get a second-order recurrence for the sequence $(a_n)$.

Remark: The lower level manipulation that we did does not depend on happy numerical "accidents." If we have a system $a_n=pa_{n-1}+qb_{n-1}$, $b_n=ra_{n-1}+sb_{n-1}$, use the two equations to eliminate say $b_{n-1}$, bump the indices as we did, and substitute.

$\endgroup$
  • $\begingroup$ So, I just have one question. Can you clarify what $(E-1)(E-4)$ is? Thank you $\endgroup$ – tekman22 Apr 22 '13 at 16:02
  • $\begingroup$ I did use that notation in the above answer. It is an operator-theoretic version of the "characteristic equation" method. $\endgroup$ – André Nicolas Apr 22 '13 at 16:10
4
$\begingroup$

Use generating functions, $A(z) = \sum_{n \ge 0} a_n z^n$ and similarly $B(z)$. Write: $$ \begin{align*} a_{n + 1} &= 3 a_n + 2 b_n \\ b_{n + 1} &= a_n + 2 b_n \end{align*} $$ By properties of generating functions: $$ \begin{align*} \frac{A(z) - a_0}{z} &= 2 A(z) + 2 B(z) \\ \frac{B(z) - b_0}{z} &= A(z) + 2 B(z) \end{align*} $$ With the given initial values: $$ \begin{align*} A(z) &= - \frac{1 + 2 z}{1 - 5 z + 4 z^2} = - \frac{1}{1 - z} + 2 \cdot \frac{1}{1 - 4 z} \\ B(z) &= \frac{2 - 5 z}{1 - 5 z + 4 z^2} = \frac{1}{1 - z} + \frac{1}{1 - 4 z} \end{align*} $$ From here: $$ \begin{align*} a_n &= -1 + 2 \cdot 4^n \\ b_n &= 1 + 4^n \end{align*} $$

$\endgroup$
  • 1
    $\begingroup$ This seems like more general method, which will always work (with linear recurrences). $\endgroup$ – Somnium Dec 27 '16 at 22:07

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.