How to solve a recurrence equation like this:


with the initial condition:


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!


4 Answers 4


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

  • $\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


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$


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


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

We can write this in the matricial form:




You must log in to answer this question.

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