Fibonacci Matrix

Question

I'm looking for a good way to find the matrix form of fibonacci equation, and also a more general implementation.

I've looked all other the web and haven't found it. I'll be really thankfull to any one that can point me in the right direction.

Answer 1

The Fibonacci's sequence satisfies $F_{n+2} = F_{n+1} + F_n$. Write this as $$ \begin{array}{cc} F_{n+2} &=& F_{n+1} + F_{n} \cr F_{n+1} &=& F_{n+1} \phantom{+F_n} \end{array} \implies \begin{pmatrix} F_{n+2} \cr F_{n+1} \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}}_M \cdot \begin{pmatrix} F_{n+1} \cr F_{n} \end{pmatrix} $$ Denoting vector $v_{n} = (F_{n+1}, F_n)$ the above recurrence equation reads $v_{n+1} = M v_n$, having a general solution $v_n = M^n v_0$.

Answer 2

You know that

$$f_{n+1}=f_n+f_{n-1} \,,$$ to discover the matrix, all you need is to figure that $f_n=f_n$.

Thus

$$f_{n+1}=f_n+f_{n-1} \,,$$ $$f_n=f_n$$

This means that $(f_{n+1}, f_n)^T=F (f_{n}, f_{n-1})^T$, where $F$ is the coefficient matrix...