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.

I have been told a couple of times it possible to calculate the fibonacci sequence much quicker using matrices but I never understood/they never elaborated. Would somebody be able to show how this technique works?

share|improve this question
2  
Or just use $F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ where $\phi = \frac{1+\sqrt{5}}{2}$. –  Gamma Function May 10 at 2:08
    

1 Answer 1

Using the recursion $F_{n+2}=F_{n+1}+F_n$ and the initial $F_0=0$ and $F_1=1$, we get $$ \begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{\large n} \begin{bmatrix} 1\\0 \end{bmatrix} =\begin{bmatrix} F_{n+1}\\F_n \end{bmatrix} $$ or $$ F_n= \begin{bmatrix} 0&1 \end{bmatrix} \begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{\large n} \begin{bmatrix} 1\\0 \end{bmatrix} $$


We can use the Jordan decomposition $$ \begin{bmatrix} 1&1\\1&0 \end{bmatrix} =\frac1{\sqrt5}\begin{bmatrix} -1/\phi&\phi\\1&1 \end{bmatrix} \begin{bmatrix} -1/\phi&0\\0&\phi \end{bmatrix} \begin{bmatrix} -1&\phi\\1&1/\phi \end{bmatrix} $$ to get that $$ \begin{align} F_n &=\frac1{\sqrt5} \begin{bmatrix} 1&1 \end{bmatrix} \begin{bmatrix} -1/\phi&0\\0&\phi \end{bmatrix}^{\large n} \begin{bmatrix} -1\\1 \end{bmatrix}\\[6pt] &=\frac{\phi^n-(-1/\phi)^n}{\sqrt5} \end{align} $$

share|improve this answer
2  
To turn this into a «quicker way» one needs to be smart about computing the matrix powers, though. –  Mariano Suárez-Alvarez May 10 at 2:06
    
So you are saying to calculate f(7) I need to multiply the {(1,1),(1,0)} matrice by itself 7 times and then multiply the result with (1,0)? Sorry its been a while since I used matrices. –  user997112 May 10 at 2:09
1  
You diagonalize the matrix so then, computing the $n$-th power is easy and you get it back in the right basis with two matrix multiplications. –  xavierm02 May 10 at 2:15
2  
You can also compute it using the binary algorithm for (matrix) powers: to find $M^7$, first find $M^2$, then $M^4=(M^2)^2$, and finally $M^7=M\cdot M^2\cdot M^4$, with a total of four (matrix) multiplications. (This can be translated directly into a recurrence for $F_{2n}$ and $F_{2n+1}$ in terms of $F_n$ and $F_{n+1}$.) This approach (which clearly should be better-known!) takes $O(\log n)$ multiplications to find $F_n$, similarly to the explicit formula, but has the strong advantage of using only integer operations rather than needing $\phi$ to high precision. –  Steven Stadnicki May 10 at 3:10
1  
Doesn’t diagonalizing the matrix and calculating the $n$-th powers of the eigenvalues amount to the same thing as using the (?) well-known closed formula for the Fibs? –  Lubin May 10 at 3:32

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.