La
suite de Fibonacci est l'une des suites
Mathématiques les plus connues. Elle doit son nom au mathématicien
italien Leonardo Pisano, plus connu sous le pseudonyme de
Fibonacci (
1175 -
1250). Dans un problème récréatif posé dans un de ses ouvrages, le
Liber Abaci, Fibonacci décrit la croissance d'une population de lapins :
- « Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? »
Ce problème est à l'origine de la suite dont le n -ème terme correspond au nombre de paires de lapins au n -ème mois. Dans cette population (idéale), on suppose que :
- le premier mois, il y a juste une paire de lapereaux ;
- les lapereaux ne sont pubères qu'à partir du deuxième mois ;
- chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapereaux ;
- les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante).
Présentation mathématique
Formule de réccurence
Notons
F n le nombre de couples de lapins au mois
n . Jusqu’à la fin du deuxième mois, la population se limite à un couple (ce qu'on note :
F 1 = F 2 = 1). Dès le début du troisième mois, le couple de lapins a deux mois et il engendre un autre couple de lapins. On note alors
F 3 = 2. Plaçons-nous maintenant au mois
n et cherchons à exprimer ce qu'il en sera deux mois plus tard
(n + 2) :
F n + 2 désigne la somme des couples de lapins au mois
n + 2 et des couples nouvellement engendrés. Or, n'engendrent au mois
(n + 2) que les couples pubères, c'est à dire ceux qui existent deux mois auparavant. On a donc :
F n + 2 = F n + 1 +F n .
Nous obtenons ainsi la forme récurrente de la suite de Fibonacci : chaque terme de cette suite est la somme des deux termes précédents ; pour obtenir chacun de ces deux termes, il faut faire la somme de leurs termes précédents... et ainsi de suite, jusqu'à ce que ces deux termes soient les deux termes initiaux, F 1 et F 2 , qui sont connus.
Nombres de Fibonacci
Les premières valeurs des nombres de Fibonacci, dans l'ordre croissant en commençant avec
n = 0, sont donc données par :
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...
Les termes de cette suite sont appelés
nombres de Fibonacci.
Expression fonctionnelle
On souhaite établir une expression
fonctionnelle de la suite de Fibonacci, c'est-à-dire une expression telle que le calcul du nombre de couples pour une valeur de
n donnée ne présuppose la connaissance d’aucun nombre de couples pour une quelconque autre valeur de
n , ce que ne permet pas la formule de récurrence. Comme la suite de Fibonacci est récurrente d’ordre deux, on peut écrire son équation caractéristique. On obtient une équation du second degré :
x 2 -x-1 = 0 .
Le calcul du Discriminant de cette équation donne les deux solutions du Polynôme :
et . ( ϕ est le Nombre d'or, et ϕ ' l'opposé de la section dorée).
Les suites ( ϕ n ) et ( ϕ ' n ) engendrent alors l'Espace vectoriel des suites vérifiant u n + 2 = u n + 1 +u n . Il en résulte que :
F n = α ϕ n + β ϕ ' n ( α et β sont des constantes à déterminer à partir de F 1 et F 2 .)
Les conditions initiales F 1 = F 2 = 1 conduisent au système suivant :
Ce qui donne le résultat suivant :
et .
Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de formule de Binet :
F n = | 1 ––– √5 | ( ϕ n - ϕ ' n ) |
.
Il existe d'autres démonstrations. Une démonstration utilisant la Transformée en Z est donnée dans l'article du même nom(éponyme). Le résultat s'obtient également en utilisant la technique des fonctions génératrices.
La suite pour les nombres négatifs
En général, on n'étudie pas les nombres de Fibonacci pour des valeurs négatives de n, bien qu'ils existent et soient facilement déterminables avec la formule récurrente. Il existe ainsi une règle très simple pour générer ces nombres quand
n<0 :
- si n est pair alors F(-n) = -F(n)
- si n est impair alors F(-n) = F(n)
Limite des quotients
Comme l'a remarqué
Johannes Kepler, le taux de croissance des nombres de Fibonacci, c'est-à-dire
, converge vers le
Nombre d'or, noté
ϕ . Mathématiquement, le résultat s'obtient ainsi :
- {| border=0
|
|
= | lim n → ∞ | ϕ n + 1 - ϕ ' n + 1 –––––––––––––––––– ϕ n - ϕ ' n |
|- | |
= | lim n → ∞ | ϕ | 1-( ϕ '/ ϕ) n + 1 ––––––––––––––––––– 1-( ϕ '/ ϕ) n |
|(en simplifiant par
ϕ n ) |- | |
= ϕ |(comme
ϕ '/ ϕ ∈ ]-1;1-1 ; 1