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 :
Fn+1=Fn+Fn-1, with F0=1 and F1=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 Ln:
2,1,3,4,7,11,18,...

A few properties

F0+F1+F2+...+Fn = Fn+2 - 1
Fn+1 = C0n + C1n-1 + C2n-2 +... (The Fibonnaci numbers are sums of diagonals in the Pascal triangle)
Ln = Fn+1 + Fn-1
F2n = Fn(Fn+1 + Fn-1) = FnLn = Fn² + 2FnFn-1 = Fn+1² + Fn-1²
F2n+1 = Fn² + Fn+1²
2Fm+n = FmLn + FnLm
Fm+n = Fm-1Fn + FmFn-1
lim Fn+1/Fn = (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 :

Fn = (φn - φ'n)/√5

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)
  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)²);

n     details

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Franšaise Previous topic Next topic