Suite de Fibonacci

En mathématiques, les nombres de Fibonacci forment une suite définie par la relation de récurrence suivante :

pour tout n ≥ 0, F(n + 2) = F(n) + F(n + 1),

et les conditions initiales :

F(0) = 0

F(1) = 1

En d'autres termes, vous commencez avec un 0 et puis un 1, et vous calculez chaque nombre de Fibonacci comme la somme des deux précédents. Les premiers nombres de Fibonacci sont :

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

Cette suite reçu le nom de suite de Fibonacci du nom du mathématicien italien Leonardo Pisano connu sous le pseudonyme de Fibonacci (1170-1250). Dans un problème récréatif posé dans un de ses ouvrages Liber Abaci il décrit la croissance d'une population de lapins, la solution est donnée par la suite de Fibonacci, le terme numéro n de la suite correspond au nombre de paires de lapins au bout de n-ième mois, dans cette population (idéale) de lapins on suppose que :

le premier mois, il y juste une paire de lapereaux,
des lapereaux qui ne peuvent être productifs qu'à partir du deuxième mois,
chaque mois, chaque paire de lapin engendre une nouvelle paire de lapereaux,
et les lapins ne meurent jamais.

Table of contents

1 Formule explicite
2 Calcul des nombres de Fibonacci
3 Applications
4 Généralisations
5 Programme

Formule explicite

La dénomination de «suite de Fibonacci» est aussi attribuée plus généralement à toute fonction g définie sur vérifiant pour tout entier naturel n, g(n + 2) = g(n) + g(n + 1). Ces fonctions sont précisément celles pour lesquelles il existe des nombres a et b, tels que pour tout entier naturel n, g(n) = aF(n) + bF(n + 1). Ainsi l'ensemble des suites de Fibonacci est un espace vectoriel, et les suites (F(n)) et (F(n + 1)) en forment une base.

Comme l'a remarqué Johannes Kepler, le taux de croissance des nombres de Fibonacci, c'est-à-dire F(n + 1) /F(n), converge vers le nombre d'or, noté φ. Le nombre d'or est la racine positive de l'équation du second degré x² - x - 1 = 0, ainsi φ² = φ + 1. Si nous multiplions les deux côtés par φⁿ, nous obtenons : φⁿ⁺² = φⁿ⁺¹ + φⁿ, donc la fonction est une suite de Fibonacci. La racine négative de l'équation du second degré, 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.

En ajustant le coefficients pour obtenir les valeurs initiales F(0) = 0 et F(1) = 1, nous obtenons pour tout entier naturel n,

Le résultat peut aussi être obtenu en utilisant la technique des fonctions génératrices.

Quand n tend vers l'infini, le second terme tend vers zéro, ainsi les nombres de Fibonacci se comportent comme une exponentielle d'un entier multiplié par le facteur 1 / √5 soit φⁿ / √5.

En fait, à partir du rang n=2, le deuxième terme est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir du premier terme φⁿ/ √5, et en arrondissant à l'entier le plus proche.

Calcul des nombres de Fibonacci

Calculer exactement les nombres de Fibonacci à partir des puissances du nombre d'or n'est pas pratique du tout, sauf pour les petites valeurs de n, puisque les erreurs d'arrondis s'accroissent et les nombres réels flottants n'ont habituellement pas assez de précision.

L'implémentation récursive naïve de la relation de définition de la suite de Fibonacci n'est pas non plus judicieuse, puisque l'on calculerait de nombreuses fois les mêmes valeurs (à moins que le langage de programmation ait la particularité d'emmagasiner les valeurs d'une fonction précédemment calculées). On calcule donc habituellement les nombres de Fibonacci «de bas en haut», en commençant avec les deux premières valeurs 0 et 1, et en remplaçant répétitivement le premier nombre par le second, et le second nombre par la somme des deux.

Avec un système permettant les calculs arithmétiques en multi-précision , on calcule plus rapidement les nombres de Fibonacci pour de grandes valeurs de l'entier n, en utilisant la relation matricielle suivante :

et l'algorithme d'exponentiation rapide.

Cette relation s'obtient par récurrence, à partir de :

et des conditions F(0)=0, F(1)=F(2)=1.

Applications

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, qui conduit à la résolution du dixième problème d'Hilbert.

Les nombres de Fibonacci apparaissent dans la formule des diagonales du triangle de Pascal (voir coefficients binomiaux).

Une utilisation intéressante des suites de Fibonacci est la conversion des miles en kilomètres. Par exemple, si vous voulez savoir combien de kilomètres font 5 miles, vous considérez le nombre de Fibonacci (5) et vous regardez le suivant qui est (8). 5 miles font environ 8 kilomètres. Cela fonctionne parce qu'il se trouve que le facteur de conversion entre les miles et les kilomètres est grossièrement égal à φ.

Une spirale logarithmique peut être approximée de la manière suivante : on commence à l'origine d'un repère cartésien, on se déplace de F(1) unités vers la droite, puis de F(2) unités vers le haut, on se déplace de F(3) unités vers la gauche, ensuite de F(4) unités vers le bas, puis de F(5) unité 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.

Généralisations

Une généralisation des suites de Fibonacci sont les suites de Lucas. Celles-ci peuvent être définies de la manière suivante :

F(0) = 0

F(1) = 1

F(n+2) = PF(n+1) + QF(n)

où les suites de Fibonacci apparaissent comme cas particulier où P = Q = 1.

D'autres types de suites de Lucas sont les suites définies de la même façon avec d'autres conditions initiales:

L(0) = 2

L(1) = 0

L(n+2) = PL(n+1) + QL(n)

De telles suites ont des applications en théorie des nombres.

Lorsque le polynome a deux racines distinctes et (réelles ou imaginaires), on a:

Les suites de Lucas, à leur tour, ne sont qu'un cas particulier des suites à relation de récurrence linéaire. Une suite S de nombres réels ou complexes, indexée par les naturels, est dite obéir à une relation de récurrence linéaire lorsqu'il existe un entier naturel k et des coefficients , , ... tels que pour tout ,

Lorsque le polynome se décompose en où les racines sont toutes distinctes (et les m_i > 0), les séquences qui obéissent à la relation ci-dessus s'obtiennent par combinaison linéaire des séquences linéairement indépendantes suivantes:

la suite des puissances de pour toute racine ,
plus la suite pour toute racine au moins double,
et ainsi de suite...

c'est-à-dire qu'on considère la suite b_i,k, définie par pour toute racine p_i et tout exposant non-négatif k strictement inférieur à la multiplicité m_i de la racine. (Si k = 0, b_i,k est simplement la suite des puissances de p_i; ici, par convention, 0⁰ est considéré égal à 1.)

Cette base de séquences est fortement semblable à la base des solutions de l'équation différentielle linéaire générale.

Programme

Les nombres de Fibonacci peuvent être calculés par le programme en langage Scheme suivant :


(define fib
 (lambda (x)

   (if (< x 2)

     x

     (+ (fib (- x 1)) (fib (- x 2))))))

Un programme OCaml est un peu plus lisible :

let rec fib = function
 0 -> 0

| 1 -> 1
| n -> fib (n-1) + fib (n-2)