Fichier:Fibonacci Squares.svgUne 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 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<ref name=":1">Modèle:Ouvrage</ref> 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, i.e. les nombres apparaissant dans cette suite, sont appelés nombres de Fibonacci.
La suite de Fibonacci est répertoriée comme Modèle:OEIS.
Elle est liée au nombre d'or, noté Modèle:Mvar (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 Modèle:Mvar en fraction continue : les quotients de deux termes consécutifs de la suite de Fibonacci sont les meilleures approximations du nombre d'or.
La suite de Fibonacci <math>(F_n)_{n \in \mathbb N}</math> est définie par <math>F_0=0,\quad F_1= 1</math>, et la relation de récurrence <math>F_n=F_{n-1} + F_{n-2}</math> pour <math>n\geqslant2</math>. Le tableau suivant donne les 15 premiers termes de la suite de Fibonacci :
Dans cet article, nous avons fait commencer la suite à <math>n=0</math> avec <math>F_0=0</math>, comme le fait Edouard Lucas<ref name=":1" />. D'autres auteurs font débuter la suite à 1<ref name=":3">Modèle:Ouvrage</ref> : <math>f_0 = f_1 = 1, f_2 = 2, f_3 = 3, f_4 = 5</math>, etc. Le nombre Modèle:Mvar s'appelle parfois le n-ième nombre de Fibonacci<ref name=":3" /> (bien qu'il soit techniquement le n+1-ième si on commence à 0).
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 Modèle:Lien est composé de syllabes pouvant être brèves (de longueur un mātrā, Modèle:Cf. alphasyllabaire) 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 Modèle:Lien en a donné des règles explicites au Modèle:Lien siècleModèle:Vérification siècle. Le philosophe indien Acharya Hemachandra (c. 1150) (et aussi Gopala, c. 1135) ont revisité le problème de manière assez détaillée<ref>{{#invoke:Langue|indicationDeLangue}} Susantha Goonatilake, Toward a Global Science: Mining Civilizational Knowledge, Indiana University Press, 1998, p. 126.</ref>.
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 :
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 Modèle:Mvar, 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 :
Modèle:Retrait
formule explicitement donnée dans l’œuvre de Virahanka<ref>{{#invoke:Langue|indicationDeLangue}} Jayant Shah, A history of Pingala's combinatorics, Northeastern University, Boston, p. 38.</ref>.
Le problème de Fibonacci est à l'origine de la suite dont le Modèle:Mvar-ième terme correspond au nombre de paires de lapins au Modèle:Mvar-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 Modèle:Mvar le nombre de couples de lapins au début du mois Modèle:Mvar. Jusqu’à la fin du deuxième mois, la population se limite à un couple ; on note Modèle:Math.
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 Modèle:Math.
Plaçons-nous maintenant au mois Modèle:Mvar et cherchons à exprimer ce qu'il en sera deux mois plus tard, soit au mois Modèle:Math : les Modèle:Math couples de lapins sont formés des Modèle:Math couples du mois précédent et des couples nouvellement engendrés.
Or, n'engendrent au mois Modèle:Math que les couples pubères, c'est-à-dire ceux qui existaient déjà deux mois auparavant, qui sont en nombre Modèle:Mvar. On a donc, pour tout entier Modèle:Mvar strictement positif :
<math>F_{n+2}=F_{n+1}+F_n</math>.
On choisit alors de poser Modèle:Math, de manière que cette relation soit encore vérifiée pour Modèle:Math.
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, Modèle:Math et Modèle:Math, qui sont connus.
Fichier:Fibonacci Rabbits.svgChez 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 à Modèle:Math.
Expressions
Il existe plusieurs façons d'obtenir une expression mathématique du Modèle:Mvar-ième terme de la suite de Fibonacci.
Expression fonctionnelle
Le calcul du Modèle:Mvar-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 fonctionnelle de la suite de Fibonacci est une expression où le calcul du Modèle:Mvar-ième terme ne présuppose pas la connaissance des termes précédents. Binet a redécouvert une formule en 1843<ref>Modèle:Article.</ref>, qui avait déjà été obtenue par de MoivreModèle:Référence nécessaire en 1718 et par Euler en 1765<ref>E326, Opera Omnia, série 1, vol. 15, Modèle:P..</ref>. Cette expression fonctionnelle s'appelle la Modèle:Ancreformule de Binet :Modèle:Bloc emphase
En fait, dès le rang Modèle:Math, le deuxième terme <math>{\varphi'^n \over\sqrt5}</math> est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir du premier terme :
Comme l'avait déjà remarqué Johannes Kepler<ref>Modèle:Lien web.</ref>, le taux de croissance des nombres de Fibonacci, c'est-à-dire <math>\frac{F_{n+1}}{F_n}</math>, converge vers le nombre d'or Modèle:Mvar.
En effet, puisque la suite Modèle:Mvar est équivalente à <math>\frac{\varphi^n}{\sqrt5}</math> (cf. supra, section Expression fonctionnelle), la suite
<math>\frac{F_{n+1}}{F_n}</math> est équivalente à <math>\frac{\frac{\varphi^{n+1}}{\sqrt5}}{\frac{\varphi^n}{\sqrt5}}=\varphi</math>, 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 Modèle:Mvar et Modèle:Mvar.
Série des inverses de termes de la suite de Fibonacci
On a également l'égalité <math>\sum^{\infty}_{k=0} \frac1{F_{2^k}} = \frac{7 - \sqrt 5}2</math><ref name="cucu">Modèle:Article et Modèle:Article.</ref>,<ref name="badea">Modèle:Article.</ref>, voir la Modèle:OEIS.
Le nombre <math>\sum^{\infty}_{k=0} \frac1{F_{2^k + 1}}</math> est lui aussi irrationnel<ref name="badea" />, voir la suite Modèle:OEIS2C.
Bases et espaces vectoriels
La dénomination de « suite de Fibonacci généralisée » est attribuée plus généralement à toute suite Modèle:Math définie sur ℕ vérifiant pour tout entier naturel Modèle:Mvar, Modèle:Math. Ces suites sont précisément celles pour lesquelles il existe des nombres Modèle:Mvar et Modèle:Mvar tels que pour tout entier naturel Modèle:Mvar, Modèle:Math. Ainsi, l'ensemble des suites de Fibonacci est un sous-espace vectoriel de <math>\mathbb R ^ \mathbb N</math>et les suites Modèle:Math et Modèle:Math en forment une base.
le nombre de façons de vider un tonneau de Modèle:Mvar litres à l'aide de bouteilles de un ou deux litres.
Démonstration : les compositions de Modèle:Mvar se terminant par 1 sont obtenues en ajoutant 1 à la fin d'une composition de <math>n-1</math>, celles se terminant par 2 sont obtenues en ajoutant 2 à la fin d'une composition de <math>n-2</math>, donc le nombre <math>C_n</math> de compositions de Modèle:Mvar vérifie <math>C_n=C_{n-1}+C_{n-2}</math>. De plus, <math>C_0=F_1=1</math> (la composition vide), <math>C_1=F_2=1 </math> (la composition (1)), ce qui montre la relation.
Dénombrements de suites de pile ou face
Modèle:Math est égal au nombre de jeux de pile ou face de longueur Modèle:Mvar qui ne contiennent pas 2 "pile" consécutifs.
Démonstration : pour former un jeu de longueur Modèle:Mvar qui ne contient pas 2 "pile" consécutifs on peut commencer par 0, et continuer avec un jeu de longueur Modèle:Math du même type, soit commencer par 1, 0 et continuer avec un jeu de longueur Modèle:Math du même type, donc le nombre <math>P_n</math> de tels jeux vérifie <math>P_n=P_{n-1}+P_{n-2}</math> ; De plus, <math>P_0=F_2=1</math> ( jeu de longueur nulle), <math>P_1=F_3=2 </math> ((1) et (0)), ce qui montre la relation.
On en déduit que Modèle:Math est aussi le nombre de parties de <math>[ \! [ 1,n ] \! ]</math> 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 Modèle:Et al.<ref name=":2">Modèle:Ouvrage.</ref> ou alors dans le problème 31.3 laissé en exercice dans Introduction à l'algorithmique de Cormen Modèle:Et al.<ref name=":0" /> 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é<ref>Cf. discussion à la fin de l'exercice 0.4 de Modèle:Harvsp.</ref>. En général, on obtient les bonnes valeurs jusqu’à Modèle:Math, sur ordinateur ou sur calculatrice.
NotonsModèle:Référence nécessaire qu’au-delà de Modèle:Math, 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.
Détail d’un exemple d'application faisable à partir d'une calculatrice : calcul de Modèle:Math.
Le nombre d’or vaut <math>\varphi=\frac{1+\sqrt5}2\approx 1{,}618</math> et d'après la formule de Binet, <math>F_{50}</math> est l'entier le plus proche du réel <math>\frac{\varphi^{50}}{\sqrt 5}</math>, qui le dépasse à peine. Compte tenu de l'ordre de grandeur de ce réel, le théorème des accroissements finis permet de s'assurer que pour le calculer à 0,5 près par défaut, Modèle:Unité est une approximation suffisante de Modèle:Mvar.
Voici la mise en œuvre récursive naïve qui suit la définition de la suite de Fibonacci.
// entrée : un nombre entier n
// sortie : le terme de rang n de la suite de Fibonacci
fonction fib(n)
si n = 0
renvoyer 0
sinonsi n = 1
renvoyer 1
sinonrenvoyer fib(n - 1) + fib(n - 2)
Ce n'est cependant pas une façon judicieuse de calculer la suite de Fibonacci, car on calcule de nombreuses fois les mêmes valeurs. Le temps de calcul est exponentiel en Modèle:Mvar, à moins d'employer une technique de mémoïsation.
Algorithme polynomial
On calcule le Modèle:Mvar-ième terme de la suite de Fibonacci en mémorisant deux termes consécutifs de la suite. On commence avec les deux premières valeurs Modèle:Math et Modèle:Math, puis on remplace répétitivement le premier nombre par le second, et le second nombre par la somme des deux.
fonction fib(n)
(a, b) ← (0, 1)
pour i de 1 à n
(a, b) ← (b, a + b)
renvoyer a
L'algorithme réalise Modèle:Mvar additions. On peut montrer que le Modèle:Mvar-ième terme de la suite de Fibonacci s'écrit avec Modèle:Math bits. Comme l'addition de deux nombres sur Modèle:Mvar bits est linéaire en Modèle:Mvar, l'algorithme est en Modèle:Math<ref name=":2" />. De manière équivalente à l'algorithme ci-dessus, on peut écrire une fonction récursive terminale, c'est-à-dire où la dernière opération effectuée par la fonction est un appel récursif. Voici un algorithme récursif terminal<ref>Modèle:Lien web.</ref> pour calculer la suite de Fibonacci.
fonction fib(n, a, b)
si n = 0
renvoyer a
sinonsi n = 1
renvoyer b
sinonrenvoyer fib(n - 1, b, a + b)
L'appel à fib(n, 0, 1) lance le calcul pour la valeur de n donnée. Les paramètres a et b sont des accumulateurs : la valeur de a est Modèle:Mvar et celle de b est Modèle:Math. Le temps de calcul est à chaque fois proportionnel à Modèle:Mvar. Par contre, l'espace mémoire occupé n'est a priori plus constant. Pour les langages qui réalisent l'optimisation d'élimination de la récursivité terminale, la mémoire occupée est constante.
Comme vu ci-dessus,<math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^n=\begin{bmatrix} F_{n+1}&F_n \\ F_{n}&F_{n-1} \end{bmatrix}</math>, on écrit un algorithme qui utilise l'exponentiation rapide pour calculer <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^n</math>, afin d'en déduire le n-ième terme. Si on considère les additions et multiplications de nombres comme des opérations élémentaires, en coût constant, l'algorithme est logarithmique en n. En comptabilisant la complexité des additions et multiplications, on peut montrer que la complexité de cet algorithme est en O(M(n) log n), et même O(M(n)), où M(n) est la complexité de l'algorithme utilisée pour réaliser une multiplication de deux nombres sur n bits (voir exercice 0.4 dans <ref name=":2" />).
La suite de Fibonacci présente de remarquables propriétés. Leur recherche et leur étude font l'objet de publications régulières, notamment par l'association d'universitaires « The Fibonacci Association » dans sa revue « The Fibonacci Quarterly », consultable en ligne<ref>Modèle:Lien web</ref>. Certaines de ces propriétés, que l'on peut démontrer à partir de la formule de Binet, ou par récurrence ou encore à l'aide de l'expression matricielle de la suite, sont indiquées dans cette section. Nous donnons également quelques propriétés liant la suite de Fibonacci et la suite de Lucas (Modèle:Mvar ) définie par la même relation de récurrence mais avec pour initialisation Modèle:Math et Modèle:Math, et pour laquelle l'analogue de la formule de Binet est : <math>L_n=\varphi^n+\varphi'^n</math>.
Propriété 1 : <math>\forall(p,q,r)\in\Z^3,F_pF_{q+r}-(-1)^rF_{p-r}F_q=F_{p+q}F_r</math>, ou encore : <math>F_pF_{q+r}-F_rF_{p+q}=(-1)^rF_{p-r}F_q</math>.
Propriété 5 : <math>\forall(p,q)\in\Z^2,F_p^2-F_{p-q}F_{p+q}=(-1)^{p-q}F_q^2</math> (identité de Catalan) et <math>F_{p+1}F_{p-1}-F_p^2=(-1)^p</math> (identité de Cassini<ref name="Cassini" />,<ref>Pour une preuve combinatoire, voir Modèle:Harvsp.</ref>).
L'identité de Catalan est le cas Modèle:Mvar de la propriété 1. L'identité de Cassini est le cas Modèle:Math de celle de Catalan (c'est donc aussi le cas Modèle:Math de la propriété 4). L'identité de Cassini peut aussi se démontrer à l'aide de l'expression matricielle :
On peut aussi démontrer cette propriété par la proposition 4 (par récurrence sur Modèle:Math), ou par un calcul explicite du quotient (en particulier, Modèle:Nobr
Propriété 11 : La suite de Fibonacci possède plusieurs propriétés de récurrence additive forte, notamment : <math>\forall n\in\N^*\quad\sum_{i=1}^{n}F_{2i-1}=F_{2n},\quad1+\sum_{i=0}^{n-1}F_{2i}=F_{2n-1}\quad\text{et}\quad1+\sum_{i=0}^{n-1}F_i=F_{n+1}</math><ref>Pour une preuve combinatoire, voir Modèle:Harvsp. On peut aussi obtenir les deux premières égalités par somme télescopique, et en déduire la troisième en les additionnant, de façon différente suivant la parité de Modèle:Mvar : voir par exemple Modèle:Note autre projet</ref>.
La suite <math>(F_{2n})</math> vérifie en outre : <math>F_{2n}=n+\sum_{k=1}^{n-1}(n-k)F_{2k}</math> pour <math>n\geqslant2</math> ; voir la Modèle:OEIS.
Modèle:Démonstration
Propriété 12 : <math>\forall n\in\N,~F_n=\sum_{k\in\Z}{n-1-k\choose k}</math> (somme finie car les coefficients binomiaux <math>{n-1-k\choose k}</math> sont nuls si Modèle:Math ou si Modèle:Math).
Cette propriété se déduit immédiatement de l'expression de la série génératrice Modèle:Supra. On peut aussi la démontrer par une récurrence d'ordre 2 sur Modèle:Mvar<ref name="Benjamin4" /> :
au rang n, <math>\mathcal{F}_n= \sum_k{n-1- k \choose k}</math>
au rang n + 1, <math>\mathcal{F}_{n+1}= \sum_k{n- k \choose k}</math>
Hérédité (rang n + 2) :
<math>\sum_k{n+1-k \choose k} = \sum_k\left({n- k \choose k} + {n- k \choose k-1}\right)</math> (formule du triangle de Pascal)
<math>= \mathcal{F}_{n+1}+\sum_m{n-1- m\choose m}</math> (hypothèse de récurrence, changement de variable Modèle:Math)
<math>= \mathcal{F}_{n+1}+ \mathcal{F}_n</math> (hypothèse de récurrence)
<math>= \mathcal{F}_{n+2} </math> (définition de la suite de Fibonacci).
Modèle:Démonstration/fin
Cela signifie que, dans un triangle de Pascal, les nombres de Fibonacci s'obtiennent en sommant les termes situés sur une diagonale (du bas vers la droite). Les termes de ces diagonales sont d'ailleurs les coefficients des polynômes de Fibonacci ; ainsi, <math>F_6(x)=x^5+4x^3+3x</math> et <math>F_9(x)=x^8+7x^6+15x^4+10x^2+1</math>.
Cette propriété découle du développement binomial de la formule de Binet<ref>Voir Modèle:Ouvrage.</ref> ; on a d'ailleurs une formule analogue pour les nombres de Lucas : <math>\forall n\in\N,~2^{n-1}L_n=\sum_{0\le k\le n/2}{n\choose 2k}5^k</math>.
Une première approche de la question de la divisibilité de Modèle:Mvar par un entier a consiste à étudier la suite des restes de Modèle:Mvarmodulo a : cette suite (rn) vérifie (dans Z/aZ) la même récurrence Modèle:Nobr et est donc périodique de période au plus a2 (les longueurs des périodes en fonction de a forment la suite des périodes de Pisano, Modèle:OEIS) ; on en déduit que pour tout a, il existe Modèle:Math inférieur ou égal à a2 tel que Modèle:Mvar (et donc Modèle:Mvar) soit divisible par a. Plus précisément, l'étude de cette récurrence dans le corps Z/pZ (où p est un nombre premier) amène à des formules analogues à la formule de Binet, d'où l'on déduit finalement (selon que 5 est ou n'est pas un carré modulo p ; voir la loi de réciprocité quadratique) que <math>F_{5n}</math> est divisible par 5, et que si p est premier autre que 5, <math>F_{(p-1)n}</math> est divisible par p si p est de la forme 5m + 1 ou 5m + 4, et <math>F_{(p+1)n}</math> est divisible par p sinon. Des résultats plus précis peuvent d'ailleurs être obtenus ; ainsi, dans le premier cas, <math>F_{(p-1)/2}</math> est divisible par p si (p – 1)/2 est pair<ref name="order">{{#invoke:Langue|indicationDeLangue}} T. Lengyel, The order of the Fibonacci and the Lucas numbers, Fibonacci Quarterly, 1995.</ref>. Enfin, si p > 2 est premier et divise Modèle:Mvar, pk divise <math>F_{p^{k-1}n}</math>, et 2k+1 divise <math>F_{3\times 2^{k-1}}</math> (si k>1) ; ces derniers résultats sont des conséquences du lemme de Hensel<ref>{{#invoke:Langue|indicationDeLangue}} Paulo Ribenboim, The New Book of Prime Number Records, New York, Springer, 1996 Modèle:ISBN, Modèle:P..</ref>,<ref>{{#invoke:Langue|indicationDeLangue}} Franz Lemmermeyer, Reciprocity Laws, New York, Springer, 2000 Modèle:ISBN, ex. 2.25-2.28, Modèle:P..</ref> ; les mêmes méthodes permettent d'obtenir des résultats analogues pour les nombres de Lucas<ref name="order" />,<ref>{{#invoke:Langue|indicationDeLangue}} Thomas Jeffery et Rajesh Pereira, Divisibility Properties of the Fibonacci, Lucas, and Related Sequences, 2013.</ref>.
Primalité des nombres de Fibonacci
Modèle:Voir
Un nombre premier de Fibonacci est un nombre de Fibonacci qui est également premier.
Les sept plus petits nombres premiers de Fibonacci <math> F_n</math> sont<ref>Voir les suites Modèle:OEIS2C et Modèle:OEIS2C de l'OEIS pour plus de termes de cette sous-suite et de ses indices.</ref> 2, 3, 5, 13, 89, 233 et Modèle:Nombre, et les indices Modèle:Math correspondants sont 3, 4, 5, 7, 11, 13 et 17 (sauf pour <math>F_4</math>, ces indices sont nécessairement premiers<ref>Voir propriété 7.</ref>) .
On découvre au fil des ans des nombres de Fibonacci premiers de plus en plus grands, mais on ignore toujours s'il en existe une infinité.
Décomposition d'un entier en somme de nombres de Fibonacci
Modèle:Voir
Tout entier positif se décompose de manière unique en la somme de nombres de Fibonacci d'indice supérieur ou égal à 2, les indices successifs de ces nombres ayant une différence supérieure ou égale à 2 lorsqu'ils sont rangés dans l'ordre.
Exemple
<math>25 = 21 + 3 + 1 = F_8 + F_4 + F_2</math>.
Applications
En mathématiques
La suite de Fibonacci apparaît dans de nombreux problèmes de dénombrement. Par exemple, le terme d'indice n (pour n supérieur ou égal à 2) de la suite de Fibonacci permet de dénombrer le nombre de façons de parcourir un chemin de longueur n-1 en faisant des pas de 1 ou 2. Ce problème est également équivalent au problème de bin packing pour n articles de longueur 1 ou 2, tel qu'on le trouve par exemple dans The Art of Computer Programming de Donald Knuth.Modèle:Référence nécessaire
Youri Matiiassevitch a montré que les nombres de Fibonacci pouvaient être définis par une [[équation diophantienne|équation diophantienneModèle:Référence nécessaire]], ce qui a conduit à la résolution du dixième problème de Hilbert. En 1975, Jones en a déduit que, pour des valeurs de x et y entières positives ou nulles, les valeurs positives du polynôme <math>2xy^4 + x^2y^3 - 2x^3y^2 - y^5 - x^4y + 2y</math> étaient exactement les nombres de FibonacciModèle:Référence nécessaire. Ces valeurs positives s'obtiennent d'ailleurs en attribuant pour valeurs à x et y deux nombres de Fibonacci successifs.
Les nombres de Fibonacci apparaissent dans la formule des diagonales du triangle de Pascal (voir Propriétés, Propriété 12).
Une bonne approximation d'un rectangle d'or peut être construite à l'aide de carrés dont les côtés sont égaux aux nombres de Fibonacci.Fichier:Fibonacci Spiral.svgLa spirale de Fibonacci : une approximation de la spirale d'or formée en traçant des arcs de cercle reliant les sommets opposés des carrés de Fibonacci (voir image en haut de cette page).
Une spirale logarithmique peut être approchée de la manière suivante : on commence à l'origine d'un repère cartésien, on se déplace de Modèle:Math unités vers la droite, puis de Modèle:Math unités vers le haut, on se déplace de Modèle:Math unités vers la gauche, ensuite de Modèle:Math unités vers le bas, puis de Modèle:Math unités vers la droite, etc. Cela ressemble à la construction mentionnée dans l'article sur le nombre d'or.
Les nombres de Fibonacci apparaissent souvent dans la nature lorsque des spirales logarithmiques sont construites à partir d'une unité discrète, telles que dans les tournesols ou dans les pommes de pin. Le nombre de pétales de la marguerite (et d'autres fleurs composées comme le tournesol) appartient à la suite de Fibonacci : souvent 34, 55 ou 89. Cela s'explique par le mécanisme de développement de la plante (voir le paragraphe « Phyllotaxie » de l'article sur le nombre d'or).
Fichier:Animation Fibonacci.gifAnimation GIF représentant FibonacciLa plupart des êtres vivants sexués sont issus de deux parents, de sorte que leurs ancêtres à la ne génération, supposés distincts, sont au nombre de 2n. Mais les hyménoptères sont tels que les femelles sont issues de deux parents, et les mâles sont issus d'une mère seulement. Il en résulte que leurs ancêtres à la n-ième génération sont constitués :Modèle:RetraitModèle:Retrait Cette forme de reproduction asexuée décrit exactement la reproduction des abeilles. Récemment, une analyse mathématique et historique du contexte de Fibonacci et sa proximité de la ville de Béjaïa, une grande source de cire à l'époque (la version française du nom de cette ville est Bougie), a suggéré que ce seraient en fait les apiculteurs de Béjaïa et la connaissance de la reproduction des abeilles qui, plutôt que la reproduction des lapins, auraient inspiré la découverte de Fibonacci <ref>Modèle:Article.</ref>.
Art
En poésie, un fib est un petit poème, sorte de haïku, dont le nombre de pieds des premiers vers correspond aux premiers nombres de la suite (1, 1, 2, 3, 5, 8).
Il existe plusieurs façons de généraliser la suite de Fibonacci : étendre aux indices négatifs, modifier les valeurs initiales, modifier les coefficients de la relation de récurrence ou modifier le nombre de termes (ou ordre) de la relation de récurrence. Si on modifie tout à la fois (initialisation, récurrence, ordre) on arrive à l'ensemble général des suites à récurrence linéaire. Un bon nombre de propriétés se généralisent au cas où le polynôme minimal de la suite récurrente linéaire définit un nombre de Pisot. Ces propriétés ont été étudiées en lien avec la théorie des automates finis (sur les mots finis et les mots infinis) dans la thèse d'État de Christiane Frougny sur la représentation des entiers et des réels en base Pisot, sur une suggestion de Marcel-Paul Schützenberger.
Extension aux indices négatifs
La suite est étendue aux indices négatifs et Knuth parle de nombres de negafibonacci<ref>{{#invoke:Langue|indicationDeLangue}} Donald Knuth (2008-12-11), « Negafibonacci Numbers and the Hyperbolic Plane », Annual meeting, The Fairmont Hotel, San Jose, CA: The Mathematical Association of America.</ref>. La formule de récurrence les définit aussi de proche en proche :Modèle:Retrait
On peut le démontrer pour tout entier Modèle:Math, par la formule de Binet ci-dessus, ou directement par récurrence.
Suites de Fibonacci généralisées
On appelle suite de Fibonacci généralisée toute suite définie par la même relation de récurrence que la suite de Fibonacci, mais dont les termes initiaux sont différents de 0 et 1Modèle:Référence nécessaire. Sur le modèle de la démonstration donnée plus haut (voir section Expression fonctionnelle), une telle suite Modèle:Math est encore de la forme Modèle:Mvar où Modèle:Mvar est le nombre d'or et <math>\varphi'=-1/\varphi</math>. Elle est donc équivalente à Modèle:Mvar, sauf si Modèle:Math (ce qui ne se produit que si <math>u_1=\varphi'u_0</math>), si bien que (comme la suite des quotients de la suite de Fibonacci) la suite <math>\frac{u_{n+1}}{u_n}</math> converge vers Modèle:Mvar.
Parmi ces suites de nombres, il faut signaler les nombres de Lucas obtenus en choisissant comme initialisation : <math>L_0=2</math> et <math>L_1=1</math>. Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29,… On trouve parfois une initialisation <math>L_0 =1</math> et <math>L_1=3</math> qui ne consiste qu'à décaler la suite d'un rang. Ces nombres interviennent dans la résolution d'équations diophantiennes. Ils sont très liés à la suite de Fibonacci par la relation suivante : <math>L_n=F_{n+1}+F_{n-1}</math> pour tout entier Modèle:Math (voir Propriétés, Propriété 9).
Parmi ces suites, on distingue la suite de Tribonacci (récurrence d'ordre 3) et la suite de Tetranacci (récurrence d'ordre 4). Selon ce nouveau classement de suites, la suite de Fibonacci est une suite de 2-bonacci.
La suite de Fibonacci apparaît sous de nombreuses formes biologiques<ref>Modèle:Ouvrage.</ref>, comme la ramification des arbres, la disposition des feuilles sur une tige, les fruits de l'ananas<ref name=Zhao2016/>, la floraison de l'artichaut, le déroulement des feuilles de fougères, la disposition d'une pomme de pin<ref>Modèle:Article.</ref>, la coquille de l’escargot et la disposition des nuages lors des ouragans. Quant aux marguerites, elles ont le plus souvent un nombre de pétales issu de la suite de Fibonacci.
Chez les Astéracées, dans les inflorescences en capitule, la disposition des fleurons sur le réceptacle forme des spirales régulières, dextres et sénestres, qui suivent les règles de la phyllotaxie dans lesquelles on peut retrouver la suite de Fibonacci<ref name=Zhao2016>Modèle:Article.</ref>.
Les abeilles domestiques ont une reproduction haplodiploïde : un œuf non fécondé donnera un mâle et un œuf fécondé donnera une ouvrière ou une reine. Ainsi, un mâle aura une mère, quand les ouvrières et reine auront une mère et un père. Par conséquent, le pedigree d'un mâle est constitué d'un parent, de deux grands-parents, de trois arrière-grands-parents, de cinq arrière-arrière-grands-parents, etc. ; il s'agit d'une suite de Fibonacci<ref>Modèle:Article.</ref>.
Dans son tableau Parade de cirque, peint en 1887-1888, Georges Seurat emploie les premiers termes de la suite : un personnage central, deux personnages à droite, trois musiciens, cinq banderoles ou cinq spectateurs en bas à gauche, huit à droite, treize en tout<ref>Modèle:Article.</ref>.
La chanteuse suisse pour enfants Sonia Grimm a publié sur son album Un petit lapin une chanson intitulée Le lapin de Fibonacci. Cette chanson présente aux enfants le nombre d'or et la suite de Fibonacci à travers l'exemple de la croissance d'une population de lapins<ref>Voir la liste des chansons de l'album sur la boutique en ligne de l'artiste.</ref>.
Le compositeur Iannis Xenakis a plusieurs fois utilisé la suite de Fibonacci : dès 1952 en tentant de créer une "image auditive" de cette série, puis dans quelques compositions : Zygia en 1952 et Le Sacrifice en 1953<ref>Modèle:Lien web</ref>.
Mario Merz, Suite de Fibonacci, commande publique artistique, 1994, Strasbourg.
Jeux et jeux vidéo
Dans le jeu Modèle:Langue, la suite de Fibonacci apparaît en tant que petite comptine chantée par la petite Sunny.
Dans le jeu Watch Dogs, la suite de Fibonacci est introduite dans l'algorithme de Bellwether, capable de transmettre un message subliminal à travers le système ctOS.
Dans le jeu Elite sur BBC Micro, les développeurs ont utilisé la suite de Fibonacci pour permettre au jeu de tenir dans 22 ko. Le jeu génère donc aléatoirement la galaxie, mais il peut ensuite la générer exactement de la même façon lorsqu'une partie est sauvegardée puis rechargée.
Le jeu de société « 4.6.Suite » (jeu de cartes) est basé sur les suites numériques et notamment sur les suites de Fibonacci.
