Solve double recursive sequence

Question

I want to find a closed form of $a_i$ sequence below:

$$a_i = \alpha a_{i-1} + \beta b_{i-1}$$ $$b_i = \gamma a_{i-1} + \delta b_{i-1}$$

I did some expansions and arrived to (assuming I have no errors) something that looks simpler:

$$a_i = f(i) + \sum_{j=1}^i j\delta^ja_j$$

But solving the second term is something I can not figure out as well.

Answer 1

Your problem can be written like this:

$$ \mathbf{x}_i = \begin{bmatrix} a_i \\ b_i \end{bmatrix} = \mathbf{A} \mathbf{x}_{i-1} \hspace{20mm} \mathbf{A} = \begin{bmatrix} \alpha & \beta \\ \gamma & \delta \end{bmatrix} $$

Assume you know $\mathbf{x}_0$. Then $\mathbf{x}_i = \mathbf{A}^i \mathbf{x}_0$.

Here are the first few values of $\mathbf{A}^n$. $$ \mathbf{A}^0 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \\ \mathbf{A}^1 = \begin{bmatrix} \alpha & \beta \\ \gamma & \delta \end{bmatrix} \\ \mathbf{A}^2 = \begin{bmatrix} \alpha^2 + \beta\gamma & \alpha\beta + \beta\delta \\ \alpha\gamma + \gamma\delta & \beta\gamma + \delta^2 \end{bmatrix} \\ $$

I believe that for arbitrary $\alpha, \beta, \gamma, \delta$, you will need to compute $\mathbf{A}^n$ explicitly. See this post on how to calculate square matrix powers. If your matrix $\mathbf{A}$ satisfies a recurrence relation, then you can obtain a closed-form solution.

Answer 2

The defining matrix $A$ has trace $T = \alpha + \delta$ and determinant $D = \alpha \delta - \beta \gamma .$ The Cayley-Hamilton Theorem says $$ A^2 - TA + DI = 0, $$ $$ A^2 = TA - DI. $$ In particular, $$ a_{i+2} = T a_{i+1} - D a_i $$