Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$

And it comes out to be that the following that

$$\begin{bmatrix}1&1\\1&0\end{bmatrix}^n = \begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}$$

Can please anyone tell me how do we derive such a base matrix for recursive equations? How can we determine the order of the matrix for the recursive equation, as well as the elements of the matrix?

Solution 1:

If $F_n$ is a linear function of $F_{n-1},F_{n-2},\dots,F_{n-k}$ with constant coefficients, then you'll need a $k \times k$ matrix to represent the recurrence. Intuitively this is because the "state" of the recurrence is the previous $k$ values: you need exactly those values to compute the next one.

As for actually finding the matrix, you need to find $A$ such that (in the case of a second order recurrence):

$$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = A \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}.$$

The second row of $A$ is clear: $F_{n-1} = F_{n-1}$, so the second row should be $\begin{bmatrix} 1 & 0 \end{bmatrix}$. The recurrence itself lives in the first row; in the Fibonacci case we have $F_n = F_{n-1} + F_{n-2}$ so the first row is $\begin{bmatrix} 1 & 1 \end{bmatrix}.$

Solution 2:

Imagine you have recursive relation, for example $a_n=\alpha a_{n-1}+ \beta a_{n-2}$. You try to find such a matrix $A$, that:

$$A \begin{bmatrix}a_{n} \\ a_{n-1}\end{bmatrix}=\begin{bmatrix}a_{n+1} \\ a_{n}\end{bmatrix}$$

It will be $2 \times 2$ matrix. Let $A=\begin{bmatrix}a && b \\ c && d\end{bmatrix}$, so:

$$A\begin{bmatrix}a_{n} \\ a_{n-1}\end{bmatrix}=\begin{bmatrix}a \cdot a_{n}+b \cdot a_{n-1} \\ c \cdot a_{n}+d \cdot a_{n-1}\end{bmatrix}$$

You want have:

$$a \cdot a_{n}+b \cdot a_{n-1}=a_{n+1}=\alpha a_{n}+ \beta a_{n-1}$$

$$c \cdot a_{n}+d \cdot a_{n-1}=a_{n}$$

If you solve this system of equation you get:

$$A=\begin{bmatrix}\alpha && \beta \\ 1 && 0\end{bmatrix}$$

You can you this method for other recursive relation, for example $a_n=\alpha a_{n-1}+ \beta a_{n-2}+\gamma a_{n-3}$ or any numbers of components.