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?
 A: 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.
A: 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} $$
A: 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}.$
A: 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.
