Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers 4

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
But this is not what the posters asks... –  VividD Jul 20 at 5:38
add comment

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:

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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