Suite de Fibonacci

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

et les conditions initiales :

F(0) = 0

F(1) = 1

Autrement dit, pour calculer un terme, il faut faire la somme des deux termes précédents, en considérant les deux termes initiaux 0 et 1.

Les termes de cette suite sont appelés nombres de Fibonacci.

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çut 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.

Sommaire

1 Formule explicite

2 Calcul des nombres de Fibonacci

3 Primalité des nombres de Fibonacci

4 Applications

5 Généralisations

6 Programme

Formule explicite

La dénomination de « suite de Fibonacci » est aussi attribuée plus généralement à toute fonction g définie sur $\mathbb N$ 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 $n\mapsto \varphi^n$ 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 $n\mapsto \varphi^n$ et $n\mapsto \left(1-\varphi\right)^n$ , 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,

$F\left(n\right) = {\varphi^n \over \sqrt{5}} - {(1-\varphi)^n \over \sqrt{5}}$

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 ${(1-\varphi)^n \over \sqrt{5}}$ 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 :

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\ F\left(n\right) & F \left(n-1\right) \end{bmatrix}$

et l'algorithme d'exponentiation rapide.

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

$\begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\ F\left(n\right) & F \left(n-1\right) \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F\left(n\right) & F \left(n-1\right) \\ F\left(n-1\right) & F \left(n-2\right) \end{bmatrix}$

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

Primalité des nombres de Fibonacci

On ignore s'il existe une infinité de nombres de Fibonacci premiers. On sait que F_n divise F_kn, et donc que, si F_n est premier, alors n est premier, mais la réciproque est fausse. Le plus grand nombre de Fibonacci premier connu est F₂₉₇₁ qui possède 621 chiffres.

Il existe des suites (T_n) vérifiant en même temps les trois conditions suivantes :

T_n+2 = T_n+1 + T_n
PGCD(T₀, T₁) = 1
pour tout n, T_n est non premier.

Le plus petit exemple connu est déterminé par :

T₀ = 1786772701928802632268715130455793
T₁ = 1059683225053915111058165141686995

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 polynôme $X 2 - P X - Q$ a deux racines distinctes $\varphi$ et $ψ$ (réelles ou imaginaires), on a:

$F(n) = \frac{\varphi^n - \psi ^n}{\varphi - \psi}$

$L(n) = {\varphi^n + \psi^n}$ .

Les suites de Lucas, à leur tour, ne sont qu'un cas particulier des suites à relation de récurrence linéaire. On dit qu'une suite S de nombres réels ou complexes, indexée par les naturels, obéit à une relation de récurrence linéaire lorsqu'il existe un entier naturel k et des coefficients $a 1$ , $a 2$ , ... $a k$ tels que pour tout $n \leq k$ ,

$S(n) = a_1 S(n-1) + a_2 S(n-2) + \dots + a_k S(n-k)$

Lorsque le polynôme $P(X) = X^n - a_1 X^{n-1} - \dots - a_k$ se décompose en $(X - p_0)^{m_0} \cdot (X - p_j)^{m_j} \cdot \dots \cdot (X - p_0)^{m_0}$ où les racines $p i$ 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 $p i$ pour toute racine $p i$ ,
plus la suite $s(n) = n p_i^n$ pour toute racine $p i$ au moins double,
et ainsi de suite...

c'est-à-dire qu'on considère la suite b_i,k, définie par $b_{i,k}(n) = n^k p_i^n$ 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 en théorie ê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 plus proche de la notation mathématique :

let rec fib = function
   0 -> 0
 | 1 -> 1
 | n -> fib (n-1) + fib (n-2)

Ces deux programmes sont cependant extrêmement lents, puisque leur temps de calcul de F(n) est proportionnel à F(n). Pour des algorithmes plus performants, voir la section « Calcul ».