0
$\begingroup$

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.

  • 2
    http://en.wikipedia.org/wiki/Companion_matrix2012-10-02

2 Answers 2

2

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

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