4
$\begingroup$

How to solve a recurrence equation like this:

$(a_{n+1},b_{n+1})=(3a_n+5b_n,a_n+3b_n)$

with the initial condition:

$(a_1,b_1)=(3,1)$

The only way I can think of to solve an equation like this is to use generating functions. However, since there are actually two variables ($a_n$ and $b_n$), I don't know if generating functions applies on the question.

Any help or hint would be appreciated. Thanks in advance!

$\endgroup$

4 Answers 4

6
$\begingroup$

We have a system of homogeneous first order linear difference equations. Define $A \in \mathbb{R}^{2 \times 2}$ by $$ A = \begin{pmatrix} 3 & 5 \\ 1 & 3 \end{pmatrix}$$ Then we have the following difference equation: $$\begin{equation} \begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 3 & 5 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}, \quad n \in \mathbb{N} \end{equation}$$ A solution is given by $$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = A^{n-1} \begin{pmatrix} a_1 \\ b_1 \end{pmatrix}$$ Can you find a nice expression for $A^{n-1}$?

$\endgroup$
2
  • $\begingroup$ Should that be A^(n-1) instead of A^n in the last equation? And I think diagonalization should give a nicer expression for A^n. Thank you for your terrific answer! $\endgroup$ Jan 15, 2015 at 22:06
  • $\begingroup$ Yes, you are right, it should be $A^{n-1}$. Edited. $\endgroup$ Jan 15, 2015 at 22:10
5
$\begingroup$

Hint

Let $X_n=(a_n,b_n)^T$then we have $X_{n+1}=AX_n$ where

$$A=\begin{pmatrix}3&5\\1&3\end{pmatrix}$$ We diagonalize $A$: $A=PDP^{-1}$ so

$$X_{n+1}=AX_n\iff Y_{n+1}=P^{-1}X_{n+1}=DP^{-1}X_n=DY_n$$ so we solve the last equality and hence we get $X_n=PY_n$

$\endgroup$
3
$\begingroup$

$b_{n+1}-3b_{n}=a_{n}$(from second part). Add into first part you get: $b_{n+2}-3b_{n+1}=3(b_{n+1}-3b_{n})+5b_{n}$

$\endgroup$
1
$\begingroup$

You have:$$a_{n+1}=3a_n+5b_n$$ $$b_{n+1}=a_n+3b_n$$

We can write this in the matricial form:

$$\begin{pmatrix}3&5\\1&3\end{pmatrix}\begin{pmatrix}a_n\\b_n\end{pmatrix}=\begin{pmatrix}a_{n+1}\\b_{n+1}\end{pmatrix}$$

So:$$\begin{pmatrix}3&5\\1&3\end{pmatrix}^{n-1}\begin{pmatrix}a_1\\b_1\end{pmatrix}=\begin{pmatrix}a_n\\b_n\end{pmatrix}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .