1

Let $$a_n = x_1a_{n-1}+x_2b_{n-1} \\b_n = x_3a_{n-1}+x_4b_{n-1}$$. Given the set $(x_1 , x_2,x_3, x_4)$ is it possible to find a general formular for $a_n,b_n$.

Ross Millikan
  • 374,822
mtheorylord
  • 4,274
  • 1
    You can first subtract the first equation with the second equation times $\frac{x_1}{x_3}$, and you will get an expression of $a_n$ in $b_n$ and $ b_{n-1}$, which you can plug back into the second equation to get a clean expression of $b_n$ in $b_{n-1}$ and $b_{n-2}$. – Lazy Lee Aug 01 '17 at 03:19
  • Ok, if you write up that in the answer I can accept, thank you. – mtheorylord Aug 01 '17 at 03:22
  • Also known as Cayley-Hamilton – Will Jagy Aug 01 '17 at 03:26

1 Answers1

2

If $$A = \begin{bmatrix}x_1&x_2\\x_3&x_4 \end{bmatrix}$$

Then

$$ A\begin{bmatrix}a_{n-1}\\b_{n-1} \end{bmatrix} = \begin{bmatrix}a_n\\b_n \end{bmatrix}$$

$$ A^2\begin{bmatrix}a_{n-1}\\b_{n-1} \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix},$$

$$ (\tau A - d I)\begin{bmatrix}a_{n-1}\\b_{n-1} \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix},$$ where $\tau = x_1 + x_4$ and $d = x_1 x_4 - x_2 x_3$ and so

$$ a_{n+1} = \tau a_n - d a_{n-1}, $$ $$ b_{n+1} = \tau b_n - d b_{n-1}. $$

$$ A^n\begin{bmatrix}a_{0}\\b_{0} \end{bmatrix} = \begin{bmatrix}a_n\\b_n \end{bmatrix}$$

$A^n$ can be computed (to give a closed form formula) via diagonalization if that exists.

In other cases, repeated squaring will give fast algorithms. Not sure about a closed form formula.

Will Jagy
  • 139,541
Aryabhata
  • 82,206
  • I put in the $ a_{n+1} = \tau a_n - d a_{n-1}, $ I hope I got the signs correct. Anyway, you get two relations, one for a, one for b. Compare with the comment at the question by Lazy Lee – Will Jagy Aug 01 '17 at 03:41
  • 1
    @WillJagy: Now I understand. Seems like by general formula OP meant $b_n$ independent of $a_n$ etc. Then your edits make perfect sense. Thanks! – Aryabhata Aug 01 '17 at 03:50