Converting recursive equations into matrices

Question

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?

Answer 1

One way to prove this is a mathematical induction.

I assume you are using the convention that $F_0=0$, $F_1=1$ and $F_2=1$.

Then, $\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_2&F_1\\F_1&F_0\end{bmatrix}$.

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

Then, using $F_{n+2}=F_{n+1}+F_n$, you can see that

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

and this completes the proof.

Answer 2

Just evaluated the matrix product and you'll see that $$ \begin{align} \begin{pmatrix} F_{k+2}& F_{k+1}\\F_{k+1}& F_{k} \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{k+1}& F_{k} \\ F_{k} &F_{k-1} \end{pmatrix} \end{align} . $$ from Fibonacci Number/Matrix Form...

A similar approach works for Chebychev polynomials $T_{n+1}(t) = 2xT_n(t) - T_{n-1}(t)$:

$$ \pmatrix{T_{n+1}(t)\cr T_n(t)} = \pmatrix{2t & -1\cr 1 & 0\cr}^n \pmatrix{t\cr 1\cr} $$

Answer 3

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

Answer 4

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.