Ouvrir le menu principal

Suite de Fibonacci

Suite d'entiers naturels définie par la relation de récurrence : u_n = u_(n-1) + u_(n-2)

En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Elle commence par les termes 0 et 1 (on trouve des définitions[réf. nécessaire] qui la commencent avec 1 et 1). Les termes de cette suite sont appelés nombres de Fibonacci (suite A000045 de l'OEIS) :

...
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 ...

La suite est définie par et pour n > 1.

Cette suite est liée au nombre d'or, φ (phi) : ce nombre 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.

HistoireModifier

En IndeModifier

Population de lapinsModifier

 
Une page de Liber Abaci de Fibonacci à la bibliothèque nationale de Florence. Dans la partie droite, on voit la suite de Fibonacci en chiffres latins, romains, et leurs valeurs dans le système hindo-arabe.

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 :

 
Croissance d'une population de lapins selon la suite de Fibonacci jusqu'au 6e mois.

« Quelqu’un a déposé un couple de lapins dans un certain lieu, clos de toutes parts, pour savoir combien de couples seraient issus de cette paire en une année, car il est dans leur nature de générer un autre couple en un seul mois, et qu’ils enfantent dans le second mois après leur naissance. »[1]

Le problème de Fibonacci est à l'origine de la suite dont le n-ième terme correspond au nombre de paires de lapins au n-ième mois. Dans cette population idéale, on suppose que :

  • au début du premier mois, il y a juste une paire de lapereaux ;
  • les lapins ne peuvent procréer qu'après deux mois d'existence ;
  • chaque début de mois, toute paire susceptible de procréer engendre exactement une nouvelle paire de lapereaux ;
  • les lapins ne meurent jamais (donc la suite de Fibonacci est croissante).

Notons   le nombre de couples de lapins au début du mois n. Jusqu’à la fin du deuxième mois, la population se limite à un couple (ce qu'on note :  ).

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  .

Plaçons-nous maintenant au mois n et cherchons à exprimer ce qu'il en sera deux mois plus tard, soit au mois n + 2 :   désigne la somme des couples de lapins au mois n + 1 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, pour tout entier n strictement positif :

 

On choisit alors de poser  , de manière que cette équation soit encore vérifiée pour n = 0.

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.

Expression fonctionnelleModifier

Le calcul du n-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 n-ième terme ne présuppose pas la connaissance des termes précédents. Binet a redécouvert une formule en 1843[réf. nécessaire], qui avait déjà été obtenue par de Moivre[réf. nécessaire] en 1718 et par Euler en 1765[2]. Cette expression fonctionnelle s'appelle la formule de Binet :

 

(Ces calculs restent valables pour n entier négatif quand la suite est prolongée comme ci-dessous.)

Quand n tend vers +∞,   est équivalent à  . Plus précisément, φn tend vers l'infini et φ' n tend vers zéro car  .

En fait, dès le rang n = 1, le deuxième terme   est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir du premier terme :

  est l'entier le plus proche de   (et il lui est supérieur ou inférieur, selon la parité de n).

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 n entier négatif).

Extension aux indices négatifsModifier

La suite est étendue aux indices négatifs et Knuth parle de nombres de negafibonacci[3]. La formule de récurrence les définisse aussi de proche en proche : Ainsi, autour de 0, la suite est :

                         
−8 5 −3 2 −1 1 0 1 1 2 3 5 8

On remarque, sur ces premières valeurs, que

  • si n est pair alors  
  • si n est impair alors  

ou plus synthétiquement :

 

On peut le démontrer pour tout entier n, par la formule de Binet ci-dessus, ou directement par récurrence.

Limite des quotientsModifier

Comme l'avait déjà remarqué Johannes Kepler[4], 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 fonctionnelle), 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 a et aφ'.

Série des inverses de nombres liés à la suite de FibonacciModifier

  • La série des inverses des nombres de Fibonacci est convergente ; André-Jeannin a démontré en 1989[5] que sa somme[6] est irrationnelle.
  • On a également l'égalité   [7]
  • La série   converge vers une somme irrationnelle[7].

Bases et espaces vectorielsModifier

  • La dénomination de « suite de Fibonacci généralisée » est attribuée plus généralement à toute fonction   définie sur ℕ vérifiant pour tout entier naturel n,  . Ces fonctions sont précisément celles pour lesquelles il existe des nombres a et b tels que pour tout entier naturel n,  . Ainsi, l'ensemble des suites de Fibonacci est un espace vectoriel, et les suites   et   en forment une base.
  • Le nombre d'or est la racine positive du polynôme x2x – 1, ainsi φ2 = φ + 1. Si l'on multiplie les deux côtés par φn, on obtient φn + 2 = φn + 1 + φn, donc la fonction   est une suite de Fibonacci. La racine négative du polynôme, φ' = 1 – φ, possède les mêmes propriétés, et les deux fonctions linéairement indépendantes   et  , forment une autre base de l'espace vectoriel.

Algorithmes de calcul des nombres de FibonacciModifier

Le calcul des nombres de Fibonacci est souvent donné en exemple pour introduire des notions d'algorithmique, comme par exemple dans le Chapitre 0 du livre Algorithms de Dasgupta et al[8] ou alors dans le problème 31.3 laissé en exercice dans Introduction à l'algorithmique de Cormen et al.[9].

Avec la formule de BinetModifier

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 [8]). En général, on obtient les bonnes valeurs jusqu’à   = 308 061 521 170 129, sur ordinateur ou sur calculatrice.

Notons[réf. nécessaire] 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.

Détail d’un exemple d'application faisable à partir d'une calculatrice : calcul de  .

Le nombre d’or vaut  , et d'après la formule de Binet,   est l'entier le plus proche du réel  , 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, 1,61803398874989 est une approximation suffisante de φ.

On trouve que le réel (1,61803398874989)50/5 est à peine inférieur à l'entier 12 586 269 025, d'où

 ,

si bien que

 .

Algorithme récursif naïfModifier

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 fibo(n)
     si n = 0 alors renvoyer 0
     sinon si n = 1 alors renvoyer 1
     sinon renvoyer fibo(n - 1) + fibo(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 n, à moins d'employer une technique de mémoïsation.

Algorithme polynomialModifier

On calcule le n-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 i = 0 et j = 1, puis on remplace répétitivement le premier nombre par le second, et le second nombre par la somme des deux.

fonction fibo(n)
     (i, j) := (0, 1)
     pour k = 1 à n
           (i, j) = (j, i+j)
     retourner i 

L'algorithme réalise n additions. On peut montrer que le n-ième terme de la suite de Fibonacci s'écrit avec O(n) bits. Comme l'addition de deux nombres sur n bits est linéaire en n, l'algorithme est en O(n2)[8]. 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[10] pour calculer la suite de Fibonacci.

fonction fibonacci(n, a, b)
      si n = 0 alors retourner a
      sinon si n = 1 alors retourner b
      sinon retourner fibonacci(n-1, b, a+b)

L'appel à fibonacci(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 Fn et celle de b est Fn+1. Le temps de calcul est à chaque fois proportionnel à n. 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.

Algorithme corécursifModifier

En Haskell, on peut définir la suite de Fibonacci comme un stream (une liste infinie qui est évaluée de façon paresseuse[11]) [12]

fibs = 0:1:zipWith (+) fibs (tail fibs) 

Le calcul du n-ème terme s'effectue avec :

fibs !! n

Algorithme avec relation matricielleModifier

On a la relation de récurrence suivante (voir exercice 0.4 dans [8]) :   et donc  

On écrit alors un algorithme qui utilise l'exponentiation rapide pour calculer  , afin d'en déduire le n-è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 [8]).

Curiosité algorithmiqueModifier

Le programme FRACTRAN défini par la liste de fractions [23/95, 57/23, 17/39, 130/17, 11/14, 35/11, 19/13, 1/19, 35/2, 13/7, 7][réf. nécessaire] et appliqué à l'entier 3 génère une suite qui contient tous les termes de la forme 2a 3b, où a et b sont deux termes consécutifs de la suite de Fibonacci.

Série génératriceModifier

La série génératrice de la suite de Fibonacci[13] donne une série entière dont le rayon de convergence vaut 1/φ (d'après le théorème de Cauchy-Hadamard ou plus simplement, la règle de d'Alembert). Pour tout complexe z de module strictement inférieur à 1/φ, la série correspondante (absolument convergente) est égale à   (donc à  , où les coefficients binomiaux   sont nuls pour k > m).

En particulier, pour tout réel k > φ,  

Propriétés de la suite de FibonacciModifier

La suite de Fibonacci présente de remarquables propriétés. En voici quelques-unes, démontrées le plus souvent à partir de la formule de Binet ou par récurrence (pour certaines, on peut aussi utiliser le calcul matriciel et les identités données au paragraphe « algorithme logarithmique »). Nous donnons également quelques propriétés liant la suite de Fibonacci et la suite des nombres de Lucas   définie par la même relation de récurrence mais avec pour initialisation   et  , et pour laquelle l'analogue de la formule de Binet est :  .

Par une récurrence immédiate[14] sur  ,   est égal au nombre de suites finies d'entiers égaux à 1 ou 2 dont la somme est égale à n. (On peut donc l'interpréter comme le nombre de façons différentes de paver un rectangleN au moyen de dominos 2×1.)

Propriété 1 :   ou encore :  

C'est un cas particulier des identités remarquables vérifiées par les suites récurrentes linéaires d'ordre 2.

Propriété 2 :  

C'est le cas r = 1 de la propriété 1[15].

Propriété 3 :  

C'est le cas q = p –1 de la propriété 2.

Propriété 4 :  

C'est le cas q = 1 de la propriété 1.

Propriété 5 :   (identité de Catalan) et   (identité de Cassini[14],[16]).

L'identité de Catalan est le cas r = p – q de la propriété 1. L'identité de Cassini est le cas q = 1 de celle de Catalan (c'est donc aussi le cas r = p – 1 de la propriété 4).
Corollaire 1 :  
Corollaire 2 :  

Propriété 6 : La suite de Fibonacci est à divisibilité (en) faible :  [17].

Cela résulte immédiatement de la propriété 2 ou 4 (par récurrence sur |k|), ou d'un calcul explicite du quotient (en particulier,  ). Plus généralement (par l'une ou l'autre méthode) toute suite de Lucas U(P, Q) est à divisibilité faible. La propriété 6 est aussi — lorsqu'on ne l'y utilise pas comme lemme — un corollaire de la propriété 8 ci-dessous.

Propriété 7 : Pour tout entier naturel n différent de 4, si   est premier, alors n est premier.

Ou par contraposée : si n est composé alors   aussi. En effet, supposons n = mk avec m et k entiers strictement supérieurs à 1. Comme n est supposé différent de 4, l'un au moins des deux facteurs est strictement supérieur à 2 : par exemple m > 2. D'après la propriété 6,   est alors un diviseur propre de  , qui n'est donc pas premier.
La réciproque est fausse, car 2 est premier alors que   ne l'est pas ; de façon moins triviale,  .

Propriété 8 : La suite de Fibonacci est à divisibilité forte :   où ∧ désigne le PGCD de nombres entiers.

En particulier,   c.-à-d. que   et   sont premiers entre eux.
Sans utiliser que l'anneau est de Bézout (ni la propriété 6), on démontre plus généralement que dans tout anneau intègre à PGCD, une suite de Lucas U(P, Q) est à divisibilité forte si (et seulement si) ses paramètres P et Q sont premiers entre eux.

Propriété 9 :   En particulier :

 
L'égalité est immédiate si p = 0. Pour p ≠ 0, c'est le cas particulier q = p de la propriété 1.

Propriété 10 :  

Propriété 11 :  [18].

 
La somme des diagonales ascendantes du triangle de Pascal forme la suite de Fibonacci.

Propriété 12 :   (somme finie car les coefficients binomiaux   sont nuls si k < 0 ou si k > n – 1 – k).

Cette propriété se déduit immédiatement de l'expression de la série génératrice (voir supra). On peut aussi la démontrer par une récurrence d'ordre 2 sur n :

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,   et  .

Propriété 13 :  .

Cette propriété découle du développement binomial de la formule de Binet[19] ; on a d'ailleurs une formule analogue pour les nombres de Lucas :  .

Propriété 14 : La suite   définie par   vérifie [réf. souhaitée](d'après la relation de récurrence sur les   et l'identité de Cassini vue en propriété 5).

Propriété 15 : La factorisation des polynômes de Fibonacci permet d'exprimer les   (pour n ≥ 1) sous forme de produits trigonométriques[20] : .

Divisibilité des nombres de FibonacciModifier

Une première approche de la question de la divisibilité de   par un entier a consiste à étudier la suite des restes de   modulo a : cette suite (rn) vérifie (dans Z/aZ) la même récurrence (rn+2 = rn+1 + rn) 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, suite A001175 de l'OEIS) ; on en déduit que pour tout a, il existe n inférieur ou égal à a2 tel que   (et donc  ) 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   est divisible par 5, et que si p est premier autre que 5,   est divisible par p si p est de la forme 5m + 1 ou 5m + 4, et   est divisible par p sinon. Des résultats plus précis peuvent d'ailleurs être obtenus ; ainsi, dans le premier cas,   est divisible par p si (p – 1)/2 est pair[21]. Enfin, si p > 2 est premier et divise  , pk divise  , et 2k+1 divise   ; ces derniers résultats sont des conséquences du lemme de Hensel[22],[23] ; les mêmes méthodes permettent d'obtenir des résultats analogues pour les nombres de Lucas[21],[24].

Primalité des nombres de FibonacciModifier

Article détaillé : Nombre premier de Fibonacci.

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 FibonacciModifier

Article détaillé : Théorème de Zeckendorf.

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
 .

ApplicationsModifier

  • 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).
  • 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'ailleurs 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. J.-C.). Le mathématicien indien Virahanka (en) en a donné des règles explicites au VIIIe 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. 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 suite. 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.
 
Les carrés de Fibonacci en spirale s'ajustent ensemble pour former une spirale d'or.
  • 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.
 
Approximation d'une spirale d'or créée en dessinant des arcs de cercle reliant les coins opposés de carrés dans un pavage Fibonacci. Celui-ci utilise des carrés de tailles 1, 1, 2, 3, 5, 8, 13, 21, et 34.
  • 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   unités vers la droite, puis de   unités vers le haut, on se déplace de   unités vers la gauche, ensuite de   unités vers le bas, puis de   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).
  •  
    Animation GIF représentant Fibonacci
    La 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 :pour les femelles, de   mâles et   femelles,pour les mâles, de   mâles et   femelles. 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 c'était en fait les apiculteurs de Béjaïa et la connaissance de la reproduction des abeilles qui ont vraiment inspiré les nombres de Fibonacci plutôt que la reproduction des lapins[26].

GénéralisationsModifier

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éesModifier

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 1. Sur le modèle de la démonstration donnée plus haut (voir section Expression fonctionnelle), une telle suite un) est encore de la forme αφn + βφ'nφ est le nombre d'or et   Elle est donc équivalente à αφn, sauf si α = 0 (ce qui ne se produit que si  ), si bien que (comme la suite des quotients de la suite de Fibonacci) la suite   converge vers φ.

Parmi ces suites de nombres, il faut signaler les nombres de Lucas obtenus en choisissant comme initialisation :   et  . Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29,… On trouve parfois une initialisation   et   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 :   pour tout entier n > 0 (voir Propriétés, Propriété 9).

Suites de LucasModifier

Ce sont les suites où la relation de récurrence a changé : elle est devenue

 

Elles sont de deux types, notés X = U et X = V, selon que l'initialisation est U0 = 0 et U1 = 1 ou qu'elle est V0 = 2 et V1 = P.

La suite de Fibonacci et la suite des nombres de Lucas sont les suites U et V de Lucas de paramètres P = 1 et Q = –1.

Articles détaillés : Suite de Lucas et Nombre de Lucas.

Suites de k-bonacciModifier

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

 

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.

Dans la cultureModifier

PeintureModifier

 
Georges Seurat, Parade de cirque, 1887-1888

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[27].

LittératureModifier

CinémaModifier

Cette section ne cite pas suffisamment ses sources (avril 2013)
Pour l'améliorer, ajoutez des références vérifiables [comment faire ?] ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

TélévisionModifier

MusiqueModifier

  • Le groupe de metal progressif Tool structure le rythme de certaines parties du morceau Lateralus selon une suite de Fibonacci[31].
  • 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[32].
  • Selon Ernő Lendvaï[33], le compositeur Béla Bartók s'est régulièrement servi du nombre d'or et de la suite de Fibonacci dans ses œuvres. L'exemple le plus emblématique serait sa Musique pour cordes, percussion et célesta. Cependant, d'autres spécialistes de Bartók ont critiqué cette interprétation[34].
  • 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[35].
  • Sur la guitare de Robert Smith, chanteur de The Cure, pour la tournée 2016 du groupe, figure le début de la suite de Fibonacci[36].

ArchitectureModifier

Le Corbusier et son Modulor, une mesure harmonique à l'échelle humaine applicable universellement à l'Architecture et à la mécanique.


Mario Merz, Suite de Fibonacci, commande publique artistique, 1994, Strasbourg.

Jeux vidéoModifier

Dans le jeu Metal Gear Solid 4: Guns of the Patriots, 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.

CuriositéModifier

La suite de Fibonacci peut servir à mémoriser des conversions de milles américains en kilomètres. En effet,  , or le nombre d'or   et  donc on peut utiliser la formule approchée :  , éventuellement multipliée par une constante.

Par exemple,   (en fait 4,8 km), donc  ,   donc   et  ,   etc.

Notes et référencesModifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fibonacci number » (voir la liste des auteurs).
  1. Pour la version latine, voir ce document p. 283-284 et pour la traduction, ce recueil d'extraits par Jérôme Gavin, p. 8
  2. E326, Opera Omnia, série 1, vol. 15, p.  50-69.
  3. Knuth, Donald (2008-12-11), "Negafibonacci Numbers and the Hyperbolic Plane", Annual meeting, The Fairmont Hotel, San Jose, CA: The Mathematical Association of America
  4. (la) J. Kepler, Strena seu de nive sexangula, 1611
  5. Richard André-Jeannin, « Irrationalité de la somme des inverses de certaines suites récurrentes », C. R. Acad. Sci. Paris, série I Math., vol. 308,‎ , p. 539-541 (lire en ligne).
  6. Voir (en) Eric W. Weisstein, « Reciprocal Fibonacci Constant », sur MathWorld, ainsi que  A079586 (développement décimal) et  A079587 (fraction continue).
  7. a et b (en) Catalin Badea, « A theorem on irrationality of infinite series and applications », Acta Arithmetica, vol. 63,‎ , p. 313-323
  8. a b c d et e (en) Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms, McGraw-Hill,
  9. a et b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein, Introduction à l'algorithmique, 1176 p., Section 31.2
  10. « https://www.geeksforgeeks.org/tail-recursion-fibonacci/ » (consulté le 15 octobre 2019)
  11. Voir par exemple l’évaluation similaire de la factorielle.
  12. Antony J. T. Davie, Introduction to Functional Programming Systems Using Haskell, Cambridge University, coll. « Cambridge computer sciince texts », , « chapitre 7 Lazy evaluation »
  13. Cet exemple de la théorie développée dans (la) Abraham de Moivre, Miscellanea analytica de seriebus et quadraturis, (lire en ligne), p. 26-42, est détaillé par (en) John Stillwell, Mathematics and Its History [détail des éditions] (p. 192-194 sur Google Livres) comme outil de la seconde preuve de la formule « de Binet », indépendante de la première, publiée par Daniel Bernoulli deux ans auparavant.
  14. a et b (en) M. Werman et D. Zeilberger, « A bijective proof of Cassini's Fibonacci identity », Discrete Math., vol. 58, no 1,‎ , p. 109 (DOI 10.1016/0012-365X(86)90194-9, Math Reviews 0820846).
  15. a et b Pour une preuve combinatoire, voir (en) Arthur T. Benjamin et Jennifer J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, MAA, (lire en ligne), p. 4.
  16. Pour une preuve combinatoire, voir Benjamin et Quinn 2003, p. 8.
  17. Pour une preuve combinatoire, voir Benjamin et Quinn 2003, p. 11.
  18. Pour une preuve combinatoire, voir Benjamin et Quinn 2003, p. 2-3. 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 n : voir par exemple cet exercice corrigé sur Wikiversité.
  19. Voir (en) Steven Vajda (en), Fibonacci and Lucas Numbers, and the Golden Section, Dover, (1re éd. 1989) (lire en ligne), p. 68-69.
  20. (en) Bala Sury, « Trigonometric expressions for Fibonacci and Lucas Numbers », Acta Math. Univ. Comenianae, vol. 79, no 2,‎ , p. 199-208 (lire en ligne).
  21. a et b (en) T. Lengyel, The order of the Fibonacci and the Lucas numbers, Fibonacci Quarterly, 1995.
  22. (en) Paulo Ribenboim, The New Book of Prime Number Records, New York, Springer, 1996 (ISBN 0-387-94457-5), p. 64.
  23. (en) Franz Lemmermeyer (de), Reciprocity Laws, New York, Springer, 2000 (ISBN 3-540-66957-4), ex. 2.25-2.28, p. 73-74.
  24. (en) Thomas Jeffery et Rajesh Pereira, Divisibility Properties of the Fibonacci, Lucas, and Related Sequences, 2013.
  25. (en) Victor H. Moll, Numbers and Functions: From a Classical-experimental Mathematician's Point of View, AMS, (lire en ligne), p. 113, reproduit dans « Infinitude of Primes - via Fibonacci Numbers », sur Cut The Knot.
  26. (en) T.C. Scott et P. Marketos, « On the Origin of the Fibonacci Sequence », MacTutor History of Mathematics archive, University of St Andrews,‎ (lire en ligne)
  27. C. Pasquet, « Du nombre d'or à la Section d'or », Dossier de l'Art, no 257,‎ , p. 70-71.
  28. Seligman, qui recueille l’héroïne, est adepte de pêche à la ligne, de Bach et de la suite de Fibonacci selon Libération
  29. Détails et explications dans l'article «Nymphomaniac», un film fourré aux mathématiques de Thomas Messias sur Slate
  30. « X + Y Review [TIFF 2014] » (consulté le 13 juin 2015)
  31. (en) Christopher diCarlo, Interview with Maynard James Keenan [lire en ligne].
  32. Voir la liste des chansons de l'album sur la boutique en ligne de l'artiste.
  33. (en) Ernő Lendvai, Béla Bartók: An Analysis of His Music — With an Introduction by Alan Bush, Kahn & Averill, (ISBN 978-0-90070781-0).
  34. Voir par exemple (en) Gareth E. Roberts, « The Bartók Controversy », .
  35. Sven Sterken, « Iannis Xenakis, Ingénieur et Architecte. p122 » [PDF],
  36. http://s1.lprs1.fr/images/2016/11/15/6332622_the-cure007.jpg

Voir aussiModifier

BibliographieModifier

Articles connexesModifier

Liens externesModifier