En mathématiques, la suite de Fibonacci est définie par récurrence par :
, pour tout entier .
Autrement dit, les deux valeurs de départ 0 et 1 étant données, chaque nombre est la somme des deux précédents.
La suite de Fibonacci peut être généralisée de nombreuses façons ; par exemple, en partant d'autres nombres que 0 et 1, en ajoutant plus de deux termes pour engendrer le suivant, ou en ajoutant des objets autres que des nombres.
Extension aux entiers négatifs À l'aide de la relation , on peut étendre la suite de Fibonacci à des indices entiers négatifs. On obtient la suite : qui vérifie : .
Extension aux nombres réels ou complexes vignette|Tracé de la courbe de la fonction Fib entre -5 et 5.
De manière similaire à la généralisation de la suite des factorielles par la fonction Gamma d'Euler, on peut construire une généralisation de la suite de Fibonacci à des valeurs de départ réelles (et même complexes).
Elle est basée sur la formule de Binet faisant intervenir le nombre d'or φ : .
En posant :
on obtient une fonction holomorphe sur le plan complexe qui satisfait pour tout entier nPravin Chandra et Eric W. Weisstein. "Fibonacci Number". MathWorld..
Elle vérifie aussi pour tout complexe z.
Modification des termes initiaux On peut désigner par suite de type Fibonacci toute suite à valeurs dans un espace vectoriel, vérifiant pour tout naturel n. Ces suites peuvent aussi être définies par , de sorte qu'elles forment un plan vectoriel de base . D'après la formule de Binet ci-dessus, une autre base de ce plan est .
Plus généralement, peut prendre ses valeurs dans un groupe abélien (considéré comme un -module). Dans ce cas, les suites de type Fibonacci forment un -module de dimension 2.
La suite de type Fibonacci la plus connue après la suite est la suite des nombres de Lucas définie par , et donc ; prolongée aux entiers négatifs, elle vérifie aussi .
Les suites d'entiers de type Fibonacci non triviales se trouvent toutes (éventuellement avec un décalage) sur une des lignes du tableau de Wythoff. La suite de Fibonacci en est la première ligne, et un décalage de celle de Lucas la deuxième..
Modification des coefficients de la récurrence En reprenant les notations des suites de Lucas, on peut considérer les suites vérifiant où p et q sont des entiers fixés. Elles sont toutes combinaisons linéaires des deux suites de base définies par :
(pour , et ).
Lorsque , la suite est appelée p-suite de Fibonacci et c'est aussi la valeur en p du polynôme de Fibonacci d'indice n. Exemples : La 2-suite de Fibonacci est la suite de Pell. La 3-suite de Fibonacci est la : 0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, ... La 4-suite de Fibonacci est la : 0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, ... La 5-suite de Fibonacci est, avec un décalage d'une unité, la : 0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, ... La 6-suite de Fibonacci est la : 0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, ...
La p-constante de Fibonacci, appelée aussi p-ième nombre métallique, est la limite du rapport de deux nombres consécutifs de la p-suite de Fibonacci ; c'est l'unique solution positive de , égale à .
En particulier, pour on obtient le nombre d'or , pour , le nombre d'argent 1 + , et sa valeur pour p = 3 , , est parfois appelée nombre de bronze.
Pour cette raison, ces suites ont été baptisées suites de p - métallonaci (p - metallonacci sequences en anglais), ce qui permet de les différencier des suites de p - bonacci suivantes. Elles sont regroupées dans le tableau .
Plus généralement, est appelée la -suite de Fibonacci ; exemples : La (1,2)-suite de Fibonacci est la suite de Jacobsthal, : 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, ... La (1,3)-suite de Fibonacci est la : 0,1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, ... La (2,2)-suite de Fibonacci est la : 0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, ... La (3,3)-suite de Fibonacci est la : 0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, 507627, 1924560, 7296561, 27663363, 104879772, 397629405, 1507527531, 5715470808, ...
Augmentation de l'ordre de la récurrence
Suites de p-bonacci Une suite de type Fibonacci d'ordre p , ou suite de -bonacci, est une suite d'entiers dans laquelle chaque terme à partir du + 1-ième est la somme des précédents (le cas classique est = 2). Commençant à l'indice 0 et avec les premiers termes 0, 1, 1, 2, 4, ..., , on la note .
Interprétations combinatoires :
Le nombre de listes d'entiers compris entre 1 et inclus dont la somme vaut (des compositions de ) est égal à ; Le nombre de jeux de pile ou face de longueur qui ne contiennent pas "pile" consécutifs (ou le nombre de parties de ne contenant pas entiers consécutifs) est égal à et .
Ces suites ont été étudiées par Marc Barr en 1913.
Suites de Tribonacci
Ce sont les suites de type Fibonacci d'ordre 3 ; avec pour premiers termes 0,0,1, on obtient la :
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, , , , , , , …
La constante de Tribonacci : , limite du quotient (suivant sur précédent) de deux termes consécutifs est étudiée dans l'article détaillé ci-dessus.
Suites de Tétranacci Ce sont les suites de type Fibonacci d'ordre 4 ; avec pour premiers termes 0, 0, 0, 1, on obtient la :
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, ...
La constante de Tétranacci, rapport limite de deux termes consécutifs, racine positive de l'équation , ou , vaut environ 1,927561975482925 (lien=On-Line Encyclopedia of Integer Sequences|15x15px A086088) ; sa valeur exacte est :
où .
Suites d'ordres supérieurs Une suite où chaque terme est la somme des précédents est désignée par suite de -bonacci, ou -nacci, avec des suffixes grecs pour les premières valeurs de :
Pentanacci : 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, ... Hexanacci : 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, ... Heptanacci : 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, ... Octanacci : 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ... Enneanacci : 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, ...
La limite du quotient de deux termes consécutifs de la suite de -nacci est appelée constante de -nacci ; c'est la solution positive de l'équation caractéristique : ou celle de autre que 1
Elle permet d'obtenir une formule directe du terme d'indice de la suite de -nacci définie ci-dessus : où et désigne la fonction "entier le plus proche".
Autres généralisations On peut mettre des coefficients dans la relation de récurrence ; la suite de Padovan, et la suite de Perrin, vérifiant , entrent dans cette catégorie, et, plus généralement, les suites suivantes.
Suite engendrée par un rationnel Pour obtenir toutes les suites où chaque terme est une combinaison linéaire à coefficients entiers fixée des termes précédents, on définit la suite de Fibonacci engendrée par N (où N est un nombre rationnel positif) comme suit : si où est le r-ième nombre premier, on pose :
avec les initialisations : pour , .
On obtient ainsi les cas précédents comme : Nom de la suiteNRéférence dans l'OEISsuite de Fibonacci6suite de Pell12suite de Jacobsthal18suite de Tribonacci30suite de Tetranacci210suite de Padovan15
Suites modélisant l'accroissement d'une population de lapins
Partons du problème initial posé par Fibonacci : sachant qu'un couple de lapins donne naissance à un nouveau couple chaque mois et que chaque couple commence à engendrer à partir du deuxième mois suivant sa naissance, on demande le nombre total de couples au -ième mois.
Changement du délai de gestation On peut supposer que chaque couple commence à engendrer à partir du p-ième mois suivant sa naissance (biologiquement ce serait ou 5).
Posant , le nombre de couples de lapins nés durant le mois , et partant d'un couple au mois 1, le nombre demandé est ; comme , la suite est définie par :
.
Pour (la lapine met bas dès le mois suivant son mois de naissance), on trouve .
Pour , on obtient la suite de Fibonacci classique
Pour , on obtient : 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277,... : suite de Naranaya, . Pour , on obtient : 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131,... :
Changement du nombre de couples dans la portée Ici, un couple de lapins donne naissance à nouveaux couples chaque mois et chaque couple commence à engendrer à partir du -ième mois suivant sa naissance.
La suite donnant le nombre de lapins au mois est alors définie par .
Pour , on dispose de la formule exacte : , et la limite de est . Exemples :
pour , on obtient la suite de Jacobsthal : 1, 1, 3, 5, 11, 21, 43, 85, 171, 341,..., , aussi dénommée suite de Bêta-nacci par Shari Lynn Levine. On a dans ce cas tout simplement et tend vers 2. pour , on obtient la suite de Gamma-nacci : 1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, ..., décalée d'un cran. pour r = 4, 5, 6, Levine a donné les noms de delta, êta , zêta - nacci.
Pour , on obtient : 1, 1, 1, 3, 5, 7, 13, 23, 37, 63, 109,..., décalée d'un cran. Pour , on obtient : 1, 1, 1, 4, 7, 10, 22, 43, 73, 139, 268,..., décalée d'un cran.
Cas d'une durée de vie finie pour les lapins On pose maintenant la condition que chaque lapin vit exactement mois (i.e. meurt durant le -ième mois suivant son mois de naissance), avec , les portées étant toujours de r couples.
Plus précisément, une lapine qui naît le mois , commence à procréer le mois , continue de procréer jusqu'au mois , et meurt à la fin de ce mois ; chaque couple donne donc naissance à couples.
Si l'on pose :
, le nombre de couples de lapins nés durant le mois , le nombre de couples de lapins vivants à la fin du mois .
La suite peut être définie sur les entiers relatifs par :
pour
pour .
et on obtient par la formule .
La suite peut être définie directement par récurrence d'ordre :
pour
les premiers termes étant définis par :
pour pour
Elle vérifie aussi la relation de récurrence plus simple, mais d'ordre : pour .
Exemples pour r = 1 (1 couple par portée)
1) Pour et (le couple met bas au bout de 2 mois, met bas puis meurt le mois suivant), on obtient la suite définie par :
Soit 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151,...
vérifiant aussi la récurrence d'ordre 4 :
.
C'est la suite de Padovan décalée, .
2) Pour et , on obtient la suite définie par :
Soit : 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277,...
Elle est aussi définie par récurrence d'ordre 3 :
Et on a la récurrence d'ordre 5 :
C'est la suite de Naranaya, .
Exemples avec r supérieur ou égal à 2
Cas le plus simple
Pour , , , on obtient la suite définie par :
: 1, 3, 8, 22, 60, 164, 448, 1224, 3344, 9136, 24960, 68192, ...., décalée d'un cran.
Suite de Vauban