Nombres de Fibonacci
Les nombres de Fibonacci sont issus d'un problème posé par Leonard de Pise dit Fibonacci (vers 1200)
sur la croissance d'une population de lapins.
En partant d'un couple de lapin, et en supposant que chaque couple d'une génération produise un couple pour la génération suivante, et un couple pour la génération qui suit, puis meurt. Le nombre de couples de lapin est alors :
1,2,3,5,8,13, .... donné par la relation de récurence :
Fn+1=Fn+Fn-1, avec F0=1 et F1=2
En partant de 1,1, il vient d'ailleurs la même suite : 1,1,2,3,... ou de 0,1, qui donne 0,1,1,2,3,...
Par contre en partant de 2,1 on obtient des nombres du même genre, mais différents, appelés nombres de Lucas Ln:
2,1,3,4,7,11,18,...
Quelques propriétés
F0+F1+F2+...+Fn = Fn+2 - 1Fn+1 = C0n + C1n-1 + C2n-2 +... (Les nombres de Fibonnaci sont la somme des diagonales du triangle de Pascal)
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 = φ
Calcul
La formule de récurrence donne la suite des nombres de Fibonacci, certes... Mais pour calculer le millionième nombre de Fibonacci ?La résolution de la récurence linéaire donne la formule de Binet :
En appelant π = (1+√5)/2 le nombre d'or et φ' = -1/φ = (1-√5)/2 son conjugué :
| Fn = (φn - φ'n)/√5 |
et comme |φ'| < 0.5, Fn est l'entier le plus proche de φn/√5
Une méthode récursive pour calculer Fn en O(log(n)),
à partir des F2n-1 et F2n en fonction des Fn et Fn-1 :
Ce sous programme récursif retournant (Fn-1, Fn)
fibo (n) :
si n = 0 : retour (1, 0)
sinon :
k = partie entière de n/2
(fk1, fk) = fibo(k)
si n pair : retour (fk² + fk1², fk² + 2*fk*fk1)
sinon : retour (fk² + 2*fk*fk1, fk² + (fk + fk1)²);
