Fibonnaci numbers
The Fibonnaci numbers come from a problem by Leonard de Pise alias Fibonnaci (about in 1200) about the growth of
rabbit poulation.
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 :
F
_{n+1}=F
_{n}+F
_{n1}, with F
_{0}=1 and F
_{1}=2
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 L_{n}:
2,1,3,4,7,11,18,...
A few properties
F
_{0}+F
_{1}+F
_{2}+...+F
_{n} = F
_{n+2}  1
F
_{n+1} = C
_{0}^{n} + C
_{1}^{n1} + C
_{2}^{n2} +...
(The Fibonnaci numbers are sums of diagonals in the Pascal triangle)
L
_{n} = F
_{n+1} + F
_{n1}
F
_{2n} = F
_{n}(F
_{n+1} + F
_{n1}) = F
_{n}L
_{n} =
F
_{n}² + 2F
_{n}F
_{n1} = F
_{n+1}² + F
_{n1}²
F
_{2n+1} = F
_{n}² + F
_{n+1}²
2F
_{m+n} = F
_{m}L
_{n} + F
_{n}L
_{m}
F
_{m+n} = F
_{m1}F
_{n} + F
_{m}F
_{n1}
lim F
_{n+1}/F
_{n} = (1+√5)/2 = φ
Calculation
The recurrence formula gives the Fibonacci sequence, sure...
But to calculate the millionth Fibonacci number ?
Solving the linear recurrence gives the Binet formula :
Naming π =
_{ } (1+√
5)/2 the golden ration and φ' = 1/φ = (1√
5)/2 the conjugate :
F_{n} = (φ^{n}  φ'^{n})/√5

as φ' < 0.5, F_{n} is the nearest integer to _{ }φ^{n}/√5
A recursive method to calculate F_{n} in O(log(n)),
from the F_{2n1} and F_{2n} out the F_{n} and F_{n1} :
This recursive subroutine returns (F_{n1}, F_{n})
fibo (n) :
if n = 0 : return (1, 0)
else :
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)²);