Leonardo Pisano (Leonardo Fibonacci, or simply Fibonacci meaning "filius nacci", the son of Nacci) was born in Pisa, Italy in about 1170 (the place where I live). He is well known for his Fibonacci Numbers.

Can you compute the Fibonacci numbers in optimal time?

We can write the Fibonacci formula in matrix form

ReplyDeletex(i+1) | 1 1 | x(i)

= | |

x(i) | 1 0 | x(i-1)

or y(i) = F y(i-1) and y(0) = [0 1], or simply

y(i) = F^n y(0). We must efficently calculate F^n.

This can be calculated using the Caley-Hamilton Theorem (A matrix is root of its characteristic polynomial). We obtain p(a) = -a(1-a) -1 and then F^2-F-I = 0 ==> F^2 = F+I. The divide et impera.