## Friday, March 13, 2009

### Fibonacci, a mathematician from Pisa

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?

#### 1 comment:

1. We can write the Fibonacci formula in matrix form

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