The Fibonnaci numbers come from a problem by Leonard de Pise alias Fibonnaci (about in 1200) about the growth of
Starting from a couple of rabbits, and supposing that each couple in a given generation
gives a couple for next generation, then a couple for the second next generation, then dies.
The number of rabbit couples is then :
1,2,3,5,8,13, .... given by the recurrence relation :
, with F0
=1 and F1
Starting from 1,1, comes the same sequence, just shifted by one : 1,1,2,3,...
or from 0,1, giving 0,1,1,2,3,... (the initial rabbit statement)
But starting from 2,1 we get similar, but different numbers, named Lucas numbers Ln:
A few properties
(The Fibonnaci numbers are sums of diagonals in the Pascal triangle)
) = Fn
² + 2Fn
² + Fn-1
² + Fn+1
= (1+√5)/2 = φ
The recurrence formula gives the Fibonacci sequence, sure...
But to calculate the millionth Fibonacci number ?
Solving the linear recurrence gives the Binet formula :
Naming π =
)/2 the golden ration and φ' = -1/φ = (1-√5
)/2 the conjugate :
as |φ'| < 0.5, Fn is the nearest integer to φn/√5
A recursive method to calculate Fn in O(log(n)),
from the F2n-1 and F2n out the Fn and Fn-1 :
This recursive subroutine returns (Fn-1, Fn)
fibo (n) :
if n = 0 : return (1, 0)
k = integer part of n/2
(fk1, fk) = fibo(k)
if n even : return (fk² + fk1², fk² + 2*fk*fk1)
else : return (fk² + 2*fk*fk1, fk² + (fk + fk1)²);