27
$\begingroup$

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?

$\endgroup$
20
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ But this is not what the posters asks... $\endgroup$ – VividD Jul 20 '14 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.