vignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21.
En mathématiques, la suite de Fibonacci, tirant son nom du mathématicien italien Fibonacci, est une suite de nombres entiers dans laquelle chaque nombre est la somme des deux nombres qui le précèdent. Elle commence par les nombres 0 et 1. puis se poursuit avec : 1 (comme somme de 0 et 1), 2 (comme somme de 1 et 1), 3 (comme somme de 1 et 2), 5 (comme somme de 2 et 3), 8 (comme somme de 3 et 5), etc.
Les termes de cette suite, c'est-à-dire les nombres apparaissant dans cette suite, sont appelés nombres de Fibonacci.
La suite de Fibonacci est répertoriée comme .
Elle est liée au nombre d'or, noté (phi), qui intervient dans l'expression du terme général de la suite. Inversement, la suite de Fibonacci intervient dans l'écriture des réduites de l'expression de en fraction continue : les quotients de deux termes consécutifs de la suite de Fibonacci sont les meilleures approximations du nombre d'or.
Définition formelle La suite de Fibonacci est définie par , et la relation de récurrence pour . Le tableau suivant donne les 15 premiers termes de la suite de Fibonacci : ... 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610... Dans cet article, nous avons fait commencer la suite à avec , comme le fait Édouard Lucas. D'autres auteurs font débuter la suite à 1. : , etc. Le nombre s'appelle parfois le n-ième nombre de Fibonacci (bien qu'il soit techniquement le n+1-ième si on commence à 0).vignette|Représentation géométrique de la fraction continue de faisant apparaître les nombres de la suite de Fibonacci.|239x239px
Histoire En Inde vignette|Treize () façons d'alterner courtes et longues syllabes dans un vers de six mātrās. Huit () finissent par une courte syllabe et cinq () par une longue syllabe. Dans la branche des mathématiques concernant la combinatoire, les mathématiciens indiens s'intéressent à des problèmes de lexicographie et de métrique. Le est composé de syllabes pouvant être brèves (de longueur un mātrā) ou longues (de longueur deux mātrās).
La question est de savoir comment peuvent s'alterner les brèves et les longues dans un vers de n mātrās. Ce problème apparaît très tôt en Inde, sous le nom maatraameru (montagne de cadence), dans le travail du grammairien du sanskrit, Pingala, auteur du Chhandah-shastra (l'art de la Prosodie), vers 450 ou 200 av. J.-C. Le mathématicien indien en a donné des règles explicites au . Le philosophe indien Acharya Hemachandra (c. 1150) ainsi que Gopala (c. 1135) ont revisité le problème de manière assez détaillée Susantha Goonatilake, Toward a Global Science: Mining Civilizational Knowledge, Indiana University Press, 1998, p. 126..
Si la syllabe longue L est deux fois plus longue que la syllabe courte C, les solutions sont, en fonction de la longueur totale de la cadence : 1 C → 1 2 CC,L → 2 3 CCC, CL, LC → 3 4 CCCC, CCL, CLC, LCC, LL → 5 5 CCCCC, CCCL, CCLC, CLCC, LCCC, CLL, LCL, LLC → 8 Le nombre de cadences fait apparaître les termes de la suite de Fibonacci. En effet, une cadence de longueur n peut être constituée en ajoutant C à une cadence de longueur n – 1, ou L à une cadence de longueur n – 2. Ainsi, le nombre de cadences de longueur n est la somme des deux nombres précédents de la suite.
Si on note , le nombre de manière d'alterner les brèves et les longues dans un vers de n mātrās, cette remarque conduit naturellement à la relation de récurrence suivante :
formule explicitement donnée dans l’œuvre de Virahanka Jayant Shah, A history of Pingala's combinatorics, Northeastern University, Boston, p. 38..
Population de lapins
La suite doit son nom à Leonardo Fibonacci qui, dans un problème récréatif posé dans l'ouvrage Liber abaci publié en 1202, décrit la croissance d'une population de lapins : Pour la version latine, voir ce document p. 283-284 et pour la traduction, ce recueil d'extraits par Jérôme Gavin et Alain Schärlig, p. 11.
Le problème de Fibonacci est à l'origine de la suite dont le -ième terme correspond au nombre de paires de lapins au -ième mois. Dans cette population idéale, on suppose que : au début du premier mois, il n'y a qu'une paire de lapereaux ; les lapins ne peuvent procréer qu'à partir de l'âge de deux mois ; chaque début de mois, toute paire susceptible de procréer engendre exactement une nouvelle paire de lapereaux ; les lapins ne meurent jamais (la suite de Fibonacci est donc croissante).
Notons le nombre de couples de lapins au début du mois . Jusqu’à la fin du deuxième mois, la population se limite à un couple ; on note .
Dès le début du troisième mois, le premier couple de lapins atteint l'âge de deux mois et engendre un second couple de lapins ; on note alors .
Plaçons-nous maintenant au mois et cherchons à exprimer ce qu'il en sera deux mois plus tard, soit au mois : les couples de lapins sont formés des couples du mois précédent et des couples nouvellement engendrés.
Or, n'engendrent au mois que les couples pubères, c'est-à-dire ceux qui existaient déjà deux mois auparavant, qui sont en nombre . On a donc, pour tout entier strictement positif :
On choisit alors de poser , de manière que cette relation soit encore vérifiée pour .
On obtient 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, et , qui sont connus. centré|cadre|Chez une population à la croissance idéale, les nombres de couples de lapins forment la suite de Fibonacci. À la fin du n-ième mois, le nombre de couples est égal à .
Expressions Il existe plusieurs façons d'obtenir une expression mathématique du -ième terme de la suite de Fibonacci.
Expression explicite Le calcul du -ième terme de la suite de Fibonacci via la formule de récurrence requiert le calcul des termes précédents. Au contraire, une expression explicite de la suite de Fibonacci est une expression où le calcul du -ième terme ne présuppose pas la connaissance des termes précédents. Binet a redécouvert une formule en 1843., qui avait déjà été obtenue par de Moivre en 1718 et par Euler en 1765E326, Opera Omnia, série 1, vol. 15, .. Cette expression explicite s'appelle la formule de Binet :
(Ces calculs restent valables pour entier négatif quand la suite est prolongée comme ci-dessous.)
Quand tend vers , est équivalent à . Plus précisément, tend vers l'infini et tend vers zéro car .
En fait, dès le rang , est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir de : est l'entier le plus proche de (et il lui est supérieur ou inférieur, selon la parité de ).
Il existe d'autres démonstrations de la formule de Binet, telles que la transformation en Z et la technique des fonctions génératrices. Remarquons qu'une fois découverte, cette formule se démontre aussi par récurrence (y compris pour entier négatif).
Expression matricielle De la relation , on déduit et ; ceci permet d'écrire la forme matricielle :En appliquant le déterminant, on obtient simplement l'identité de Cassini (propriété 5 ci-dessous) : .
Et en calculant de deux façons , on obtient (propriété 2 ci-dessous) : .
Expression par déterminant d'ordre n – 1 En développant par rapport à la première colonne le déterminant d'ordre n : ,
on obtient .
Comme , si , on obtient : d'où, pour :
Limite des quotients
Comme l'avait déjà remarqué Johannes Kepler., le taux de croissance des nombres de Fibonacci, c'est-à-dire , converge vers le nombre d'or .
En effet, puisque la suite est équivalente à (cf. supra, section Expression explicite), la suite est équivalente à , qui est donc sa limite.
En fait plus généralement, toutes les suites vérifiant la même relation de récurrence que la suite de Fibonacci (cf. infra, section Suites de Fibonacci généralisées) satisfont cette propriété, sauf celles commençant par et .
Séries associées aux nombres de Fibonacci
Série des inverses La série des inverses des nombres de Fibonacci non nuls est convergente, et sa somme est parfois appelée constante de Fibonacci inverse ; Richard André-Jeannin en a démontré l'irrationalité. en 1989Voir , ainsi que la (développement décimal) et (fraction continue).. La somme d'une de ses sous-séries et .. est, elle, un nombre algébrique, voir la . Le nombre est lui aussi irrationnel, voir la suite .
Série des carrés des inverses Il a été démontré que la somme est un nombre transcendant, voir la .
Bases et espaces vectoriels
La dénomination de « suite de Fibonacci généralisée » est attribuée plus généralement à toute suite définie sur ℕ vérifiant pour tout entier naturel , . Ces suites sont précisément celles pour lesquelles il existe des nombres et tels que pour tout entier naturel , . Ainsi, l'ensemble des suites de Fibonacci est un sous-espace vectoriel de et les suites et en forment une base. Le nombre d'or est la racine positive du polynôme , ainsi . Si l'on multiplie les deux côtés par , on obtient , donc la suite est une suite de Fibonacci. La racine négative du polynôme, , possède les mêmes propriétés, et les deux suites linéairement indépendantes et , forment une autre base de l'espace vectoriel.
Interprétations combinatoires
Dénombrements de compositions est égal au nombre de suites finies d'entiers égaux à 1 ou 2 dont la somme est égale à (ou compositions de formées des entiers 1 ou 2).. Par exemple car . On peut donc interpréter comme : le nombre de façons différentes de paver un rectangle 2× au moyen de dominos 2×1, le nombre de façons de vider un tonneau de litres à l'aide de bouteilles de un ou deux litres. Démonstration : les compositions de se terminant par 1 sont obtenues en ajoutant 1 à la fin d'une composition de , celles se terminant par 2 sont obtenues en ajoutant 2 à la fin d'une composition de , donc le nombre de compositions de vérifie . De plus, (la composition vide), (la composition (1)), ce qui montre la relation.
Dénombrements de suites de pile ou face est égal au nombre de jeux de pile ou face de longueur qui ne contiennent pas 2 "pile" consécutifs.
Démonstration : pour former un jeu de longueur qui ne contient pas 2 "pile" consécutifs on peut commencer par 0, et continuer avec un jeu de longueur du même type, soit commencer par 1, 0 et continuer avec un jeu de longueur du même type, donc le nombre de tels jeux vérifie ; De plus, ( jeu de longueur nulle), ((1) et (0)), ce qui montre la relation.
On en déduit que est aussi le nombre de parties de ne contenant pas 2 entiers consécutifs.
Algorithmes de calcul des nombres de Fibonacci Le calcul des nombres de Fibonacci est souvent donné en exemple pour introduire des notions d'algorithmique, comme dans le chapitre 0 du livre Algorithms de Dasgupta . ou alors dans le problème 31.3 laissé en exercice dans Introduction à l'algorithmique de Cormen ou l'exercice 2 de la section 1.2.8 de TAOCP, qui est précisément consacrée aux nombres de Fibonacci.
Avec la formule de Binet
Calculer les nombres de Fibonacci à partir du nombre d'or est une possibilité très pratique. Néanmoins, la précision de calcul de la racine carrée génère des erreurs d'arrondis pour des valeurs assez grandes dépendant du système utiliséCf. discussion à la fin de l'exercice 0.4 de .. En général, on obtient les bonnes valeurs jusqu’à , sur ordinateur ou sur calculatrice.
Notons qu’au-delà de , les calculs dépassent les possibilités de calcul en notation entière, et sont alors représentés en notation scientifique. Les premiers chiffres significatifs sont alors de nouveau bien représentés par cette formule.
Voici le détail d’un exemple d'application faisable à partir d'une calculatrice : le calcul de .