Suite de Fibonacci

Infos
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
Suite de Fibonacci

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

Notons \mathcal_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 : \mathcal_1=\mathcal_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 \mathcal_3=2. Plaçons-nous maintenant au mois n\, et cherchons à exprimer ce qu'il en sera deux mois plus tard (n + 2)\, : \mathcal_ 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 deux mois auparavant. On a donc : :\mathcal_=\mathcal_+\mathcal_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, \mathcal_1 et \mathcal_2, qui sont connus. Les premières valeurs des nombres de Fibonacci, dans l'ordre croissant en commençant avec n=0, sont donc donnés 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 : :x_1 = \varphi = \frac1+\sqrt\, et x_2 = \varphi' = \frac1-\sqrt\, . (\varphi\, est le nombre d'or, et \varphi'\, l'opposé de la section dorée). Les suites (\varphi^n) et (\varphi'^n) engendrent alors l'espace vectoriel des suites vérifiant u_=u_+u_n. Il en résulte que : :\mathcal_n = \alpha\varphi^n+\beta\varphi'^n (\alpha\, et \beta\, sont des constantes à déterminer à partir de \mathcal_1 et \mathcal_2.) Les conditions initiales \mathcal_1=\mathcal_2=1 conduisent au système suivant : :\left\\begin \alpha + \beta = 0 \\ \alpha - \beta = \frac\sqrt\end\right. Ce qui donne le résultat suivant : :\alpha = \frac\sqrt et \beta = -\frac\sqrt. Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de formule de Binet : :\mathcal_n = \frac\sqrt(\varphi^n-\varphi'^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. 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, :\mathcal_2\cdotn = \mathcal_ : \mathcal_2\cdotn = \mathcal_\mathcal_n + \mathcal_n\mathcal_ (Propriété 1) : \mathcal_2\cdotn = \mathcal_n(\mathcal_ + \mathcal_) (Factorisation) : \mathcal_2\cdotn = \mathcal_n\mathcal_n (Propriété 5) Propriété 8 : \forall n\in\mathbb^
-, \mathcal_2\cdotn-1 = \mathcal_^2+\mathcal_^2 :par application directe de la propriété 1 pour p = n et q = n -1 Propriété 9 : \forall n\in\mathbb^
-, \mathcal_\mathcal_ -\mathcal_n^2= (-1)^n boîte déroulante|align=left|titre=Démonstration|contenu= En remplaçant k par n - 1 dans la propriété 3 : \mathcal_\mathcal_ - \mathcal_\mathcal_ = (-1)^\mathcal_ En multipliant par (-1) et en remplaçant \mathcal_ par 1 : \mathcal_\mathcal_ - \mathcal_^2 = (-1)^ Propriété 10 : \forall n\in\mathbb, 1+\sum_^n \mathcal_i=\mathcal_ boîte déroulante|align=left|titre=Démonstration|contenu= Par récurrence sur n.
-Initialisation (
n = 0) : 1+\sum_^0 \mathcal_i=1 et \mathcal_2=1
-Hypothèse de récurrence : au rang n, 1+\sum_^n \mathcal_i=\mathcal_
-Hérédité (rang n + 1) : :1+\sum_^ \mathcal_i=1+\sum_^n \mathcal_i+\mathcal_ (Calcul sur les sommes) :1+\sum_^ \mathcal_i=\mathcal_+\mathcal_ (Hypothèse de récurrence) :1+\sum_^ \mathcal_i=\mathcal_ (Définition de la suite de Fibonacci) Propriété 11 : \forall n\in\mathbb, 1+\sum_^n \mathcal_2\cdoti=\mathcal_2\cdotn+1 boîte déroulante|align=left|titre=Démonstration|contenu= Par récurrence sur n
-Initialisation (
n = 0) : 1+\sum_^0 \mathcal_2\cdoti=1 et \mathcal_1=1
-Hypothèse de récurrence : au rang n, 1+\sum_^n \mathcal_2\cdoti=\mathcal_2\cdotn+1
-Hérédité (rang n + 1) : :1+\sum_^ \mathcal_2\cdoti=1+\sum_^n \mathcal_2\cdoti+\mathcal_2\cdotn+2 (Calcul sur les sommes) :1+\sum_^ \mathcal_2\cdoti=\mathcal_2\cdotn+1+\mathcal_2\cdotn+2 (Hypothèse de récurrence) :1+\sum_^ \mathcal_2\cdoti=\mathcal_2\cdot(n+1)+1 (Définition de la suite de Fibonacci) Propriété 12 : \forall n\in\mathbb, \mathcal_ = \sum_^\infty n-k \choose k où les n-k \choose k sont des coefficients binomiaux. boîte déroulante|align=left|titre=Démonstration|contenu= En réalité, la somme n'est pas infinie car tous les n-k \choose k sont nuls pour k > n - k mais on sommera sur \infty pour faciliter les démonstrations. Par récurrence d'ordre 2 sur n.
-Initialisation :(
n = 0) : \sum_^\infty 0-k\choose k = 1 et \mathcal_1 = 1 :(n = 1) : \sum_^\infty 1-k\choose k = 1 et \mathcal_2 = 1
-Hypothèses de récurrence : : au rang n, \mathcal_ = \sum_^\infty n - k \choose k : au rang n + 1, \mathcal_ = \sum_^\infty n +1 - k \choose k
-Hérédité (rang n + 2) : :\sum_^\infty (n+2)-k \choose k = \sum_^\infty (n+1) - k \choose k + (n+1) - k \choose k-1 :::(Formule du triangle de Pascal) :\sum_^\infty (n+2)-k \choose k = \sum_^\infty (n+1) - k \choose k + \sum_^\inftyn - (k - 1) \choose k-1 :::Car n+1 \choose -1 = 0) :\sum_^\infty (n+2)-k \choose k = \mathcal_+\sum_^\inftyn - m \choose m :::(Hypothèse de récurrence, changement de variable m = k - 1\, ) :\sum_^\infty (n+2)-k \choose k = \mathcal_+ \mathcal_ (Hypothèse de récurrence) :\sum_^\infty (n+2)-k \choose k = \mathcal_ (Définition de la suite de Fibonacci) :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) Propriété 13 : \forall n\in\mathbb^
-, \varphi^n = \mathcal_n\cdot\varphi + \mathcal_ boîte déroulante|align=left|titre=Démonstration|contenu= Par récurrence sur n\,
- Initialisation (n = 1\, ) : \varphi^1 = \mathcal_1\cdot\varphi + \mathcal_0
- Hypothèse de récurrence : au rang n\, , \varphi^n = \mathcal_n\cdot\varphi + \mathcal_
- Hérédité (rang n + 1\, ) : :\varphi^= \varphi\cdot\varphi^n (Calculs sur les puissances) :\varphi^ =\varphi\cdot(\mathcal_n\cdot\varphi + \mathcal_) :\varphi^=\varphi^2\mathcal_n+\varphi\mathcal_ (Distributivité) :\varphi^=(1+\varphi)\mathcal_n+\varphi\mathcal_ (Hypothèse de récurrence appliquée au cas n = 2\, ) :\varphi^=\varphi(\mathcal_+\mathcal_n)+\mathcal_n (Factorisation) :\varphi^=\mathcal_\cdot\varphi+\mathcal_n (Définition de la suite de Fibonacci) Propriété 14 : \forall n > 2, \mathcal_\mathcal_\mathcal_\mathcal_ - \mathcal_^4 + 1 = 0 boîte déroulante|align=left|titre=Démonstration|contenu= Il suffit de remplacer \mathcal_n par son expression en fonction de \varphi et \varphi', et de simplifier l'expression.

Formules

- La formule suivante permet de retrouver tous les nombres de Fibonacci (formule de Binet): :\mathcal_ = \frac\sqrt \left
- La formule suivante permet de retrouver tous les nombres de Lucas (formule de Maillet): :\mathcal_ = \left

Primalité des nombres de Fibonacci

On ignore s'il existe une infinité de nombres de Fibonacci premiers. On sait que \mathcal_n divise \mathcal_k\cdotn (voir Propriétés, Propriété 2), et donc que, pour tout n >4\, , si \mathcal_n est premier, alors n\, est premier, mais la réciproque est fausse. Le plus grand nombre de Fibonacci premier connu est \mathcal_ qui possède 126377 chiffres. Il existe des suites (\mathcal_n) vérifiant en même temps les trois conditions suivantes :
- \mathcal_=\mathcal_+\mathcal_n
- \mathcal_n et \mathcal_ sont premiers entre eux (ils n'ont aucun diviseur commun).
- \forall n\in\mathbb, \; \mathcal_n n'est pas premier. Les plus petits exemples connus sont déterminés par :
- \mathcal_0 = 3794765361567513 = 3\cdot 1264921787189171
- \mathcal_1 = 20615674205555510 = 2\cdot 5\cdot 5623\cdot 366631232537
- \mathcal_0 = 1786772701928802632268715130455793 = 2521\cdot 49993\cdot 14177095479037851751198481
- \mathcal_1 = 1059683225053915111058165141686995 = 3\cdot 5\cdot 84089\cdot 73919059\cdot 150031897\cdot 75754002239

Applications

- 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 apparaît d'aillleurs très tôt en Inde, sous le nom maatraameru (montagne de cadence), dans le travail du grammairien de Sanskrit Pingala, le Chhandah-shastra, (l'art de la Prosodie), 450 ou 200 av. JC). Le mathématicien Indien Virahanka en a donné des règles explicites au VIII siècle. Le philosophe Indien Hemachandra (c.1150) (et aussi Gopala) ont revisité le problème de manière assez détaillée. En Sanskrit en effet, les voyelles peuvent être longues (L) ou courtes (C), et Hemachandra a souhaité calculer combien on peut former de cadences différentes d'une longueur donnée, chaque cadence étant définie par les longueurs des voyelles qui la constituent. Si la voyelle longue est deux fois plus longue que la courte, 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 série. Ce problème est également équivalent au dénombrement des emballages de longueur n donnée, constitué d'articles de longueur 1 ou 2, tel qu'on le trouve par exemple dans The Art of Computer Programming de Donald Knuth.
- Les nombres de Fibonacci interviennent dans l'étude de l'exécution de l'algorithme d'Euclide qui détermine le plus grand commun diviseur de deux entiers.
- Matiyasevich a montré que les nombres de Fibonacci pouvaient être définis par une équation diophantienne, ce qui a conduit à la résolution du dixième problème d'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 2xy^4 + x^2y^3 - 2x^3y^2 - y^5 - x^4y + 2y étaient exactement les nombres de Fibonacci. 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é 11).
- Une utilisation intéressante des suites de Fibonacci est la conversion des miles en kilomètres. Par exemple, pour savoir combien de kilomètres font 5 miles, il suffit de considérer le \mathcal_5 = 5 et le suivant \mathcal_6 = 8. 5 miles font environ 8 kilomètres. Cela fonctionne parce que le facteur de conversion entre les miles et les kilomètres est grossièrement égal à \varphi\, . Carrés de Fibonacci en spirale.
- 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.
- 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 \mathcal_1 unités vers la droite, puis de \mathcal_2 unités vers le haut, on se déplace de \mathcal_3 unités vers la gauche, ensuite de \mathcal_4 unités vers le bas, puis de \mathcal_5 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.
- La plupart des êtres vivants sexués sont issus de deux parents, de sorte que leurs ancêtres à la n génération, supposés distincts, sont au nombre de 2
n''. 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 génération sont constitués : ::pour les femelles, de \mathcal F_n mâles et \mathcal F_ femelles, ::pour les mâles, de \mathcal F_ mâles et \mathcal F_n femelles.
- Le nombre de façons différentes de paver un rectangle 2×N au moyen de dominos 2×1 est \mathcal F_. boîte déroulante|align=left|titre=Démonstration|contenu= Par récurrence sur N que l'on considéra comme la longueur horizontale du rectangle 2×N :
- Initialisation :
-: Le rectange 2×1 est un domino 2×1 ; il y a 1 seule façon de paver ce rectangle \left( 1=\mathcal F_2 \right).
- Supposons qu'il y ait \mathcal F_ façons de paver le rectangle 2×N.
- Considérons le rectangle 2×\mathcal F_ :
- Ce rectangle 2×(N+1) peut être construit comme la juxtaposition d'un rectangle 2×(N-1) et de 2 dominos placés horizontalement (la longueur du rectangle d'origine est toujours N+1) ; il y a par hypothèse \mathcal F_N façons de paver le rectangle auquel on a retiré les 2 dominos.
- Ce rectangle 2×(N+1) peut aussi être construit comme la juxtaposition d'un rectangle 2×N et d'un domino placé verticalement (la longueur du rectangle d'origine est toujours N+1) ; il y a par hypothèse \mathcal F_ façons de paver le rectangle auquel on a retiré le domino.
- Le nombre de façons de paver le rectangle 2×(N+1) est donc la somme \mathcal F_ + \mathcal F_ = \mathcal F_, ce qui termine le raisonnement par récurrence.

Généralisations

Il existe plusieurs voies pour généraliser la suite de Fibonacci : on peut 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.

Suites de Fibonacci généralisées

Ce sont des suites qui conservent la même relation de récurrence mais dont les termes initiaux ont changé. Comme l'a démontré la première partie, ces suites sont des combinaisons linéaires des deux suites géométriques (\varphi)^n et (1-\varphi )^n où φ est le nombre d'or. Le quotient de deux termes consécutifs tend toujours vers φ. Parmi ces suites de nombres, il faut signaler les nombres de Lucas obtenus en choisissant comme initialisation : L_0 =2 et L_1=1. Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29, ... On trouve parfois une initialisation L_0 =1 et L_1=3 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, en particulier par la relation suivante : \mathcal_n = \mathcal_ + \mathcal_\, pour tout entier n strictement positif (voir Propriétés, Propriété 5).

Suites de Lucas

Ce sont les suites où la relation de récurrence a changé : elle est devenue : U_ = P \cdot U_n + Q \cdot U_ Elles sont de deux types selon que l'initialisation est de u_0 =0 et u_1=1 ou qu'elle est v_0 =2 et v_1=P. La suite de Fibonacci est alors une suite u de Lucas de paramètres P = 1 et Q = 1. La suite des nombres de Lucas est alors une suite v de Lucas de paramètres P = 1 et Q = 1.

Suites de k-bonacci

Ce sont des suites dont la relation de récurrence est d'ordre k. Un terme est la somme des k termes qui le précèdent : u_ \, = \, u_n + u_ + u_ + ... +u_ 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. Si on modifie tout à la fois (initialisation, récurrence, ordre) on arrive à l'ensemble très général des suites à récurrence linéaire.

Voir aussi

===
Sujets connexes
Algorithme d'Euclide   Base   C (langage)   Calculatrice   Coefficient binomial   Diophantien   Discriminant   Diviseur   Domino (jeu)   Donald Knuth   Espace vectoriel   Exponentiation rapide   Fonction génératrice   Groupe de Fibonacci   Hymenoptera   Italie   Jacques Philippe Marie Binet   Java (langage)   Johannes Kepler   Leonardo Pisano   Maple   Mathématiques   Nombre d'or   Nombre premier   Pavage   Plus grand commun diviseur   Polynôme   Poésie   Python (langage)   Raisonnement par récurrence   Rectangle   Relation de récurrence   Récursion terminale   Récursivité   Sanskrit   Scheme   Spirale logarithmique   Suite (mathématiques)   Suite de Tribonacci   Suite récurrente linéaire   The Art of Computer Programming   Transformée en Z   Triangle de Pascal   Yuri Matiyasevich  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^