Take the 2-minute tour ×
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.

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!

share|improve this question
add comment

2 Answers 2

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.

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

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

share|improve this answer
add comment

Your Answer

 
discard

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.