Suite de Fibonacci (encyclopédie mathématiques)

La suite de Fibonacci est une suite d'entiers très connue. Elle doit son nom à Leonardo Fibonacci, dit Leonardo Pisano, un mathématicien italien du XIII^e siècle qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, décrit la croissance d'une population de lapins :

« Un homme met un couple de lapins dans un lieu isolé de tous les côtés par un mur. Combien de couples obtient-on en un an si chaque couple engendre tous les mois un nouveau couple à compter du troisième mois de son existence ? »

Ce problème est à l'origine de la suite dont le $n$ -ième terme correspond au nombre de paires de lapins au $n$ -è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 lapereaux ne procréent qu'à partir du (début du) troisième mois ;
chaque (début de) 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).

Croissance de population des lapins selon une suite de Fibonacci

Sommaire

[modifier] Présentation mathématique

[modifier] Formule de récurrence

Notons $\mathcal F_n$ 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 : $\mathcal F_1=\mathcal F_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 F_3=2$ . Plaçons-nous maintenant au mois $n\,$ et cherchons à exprimer ce qu'il en sera deux mois plus tard $(n + 2)$ : $\mathcal F_{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 :

$\mathcal F_{n+2}=\mathcal F_{n+1}+\mathcal F_n,$

pour tout entier $n$ strictement positif. On choisit alors de poser $\mathcal F_0=0$ , 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, $\mathcal F_1$ et $\mathcal F_0$ , qui sont connus.

[modifier] Nombres de Fibonacci

Les termes de cette suite sont appelés nombres de Fibonacci (suite A000045 de l’OEIS) :

$\mathcal F_0$	$\mathcal F_1$	$\mathcal F_2$	$\mathcal F_3$	$\mathcal F_4$	$\mathcal F_5$	$\mathcal F_6$	$\mathcal F_7$	$\mathcal F_8$	$\mathcal F_9$	$\mathcal F_{10}$	$\mathcal F_{11}$	$\mathcal F_{12}$	$\mathcal F_{13}$	$\mathcal F_{14}$	$\mathcal F_{15}$	$\mathcal F_{16}$	$\mathcal F_{17}$	$\mathcal F_{18}$	$\mathcal F_{19}$	$\mathcal F_{20}$	$\mathcal F_{21}$	$\mathcal F_{22}$	$\mathcal F_{23}$	$\mathcal F_{24}$	$\mathcal F_{25}$	…	$\mathcal F_n$
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765	10946	17711	28657	46368	75025	...	$\mathcal F_{n-1}+\mathcal F_{n-2}$

[modifier] 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 linéairement 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=\frac{1+\sqrt5}2\qquad\text{et}\qquad x_2=\varphi'=\frac{1-\sqrt5}2=-\frac1\varphi,$

où $φ$ est le nombre d'or.

Les suites $(φ n)$ et $(φ' n)$ engendrent alors l'espace vectoriel des suites vérifiant $u n + 2 = u n + 1 + u n$ . Il en résulte que :

$\mathcal F_n = \alpha{}\varphi^n+\beta\varphi'^n$ (

α

β

sont des constantes à déterminer à partir de $\mathcal F_0$ et $\mathcal F_1$ .)

Les conditions initiales $\mathcal F_0=0$ et $\mathcal F_1=1$ conduisent au système suivant :

$\left\{\begin{matrix}\alpha+\beta=0\\ \alpha-\beta=\frac2{\sqrt5}\end{matrix}\right.$

ce qui donne :

$\alpha=\frac1{\sqrt5}\qquad\text{et}\qquad\beta=-\frac1{\sqrt5}.$

Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de formule de Binet :

$\mathcal F_n=\frac1{\sqrt5}(\varphi^n-\varphi'^n),\qquad\text{avec}\qquad\varphi=\frac{1+\sqrt5}2\qquad\text{et}\qquad \varphi'=-\frac1\varphi.$

Quand $n$ tend vers l'infini, $\mathcal F_n$ est équivalent à $\frac{\varphi^n}{\sqrt5}$ . Plus précisément, $φ n$ tend vers l'infini et $φ' n$ tend vers zéro car $| φ' | < 1 < φ$ .

En fait, dès le rang $n = 1$ , le deuxième terme ${\varphi'^n \over\sqrt5}$ est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir du premier terme :

$\mathcal F_n$ est l'entier le plus proche de $\frac{\varphi^n}{\sqrt5}$ (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 quand la suite est prolongée comme ci-dessous.

[modifier] 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 calculer ces nombres quand $n < 0$ :

si n est pair alors $\mathcal F_{-n} = -\mathcal F_n$
si n est impair alors $\mathcal F_{-n} = \mathcal F_n$

ou plus généralement : $\forall n\in\N,\ \mathcal F_{-n}=(-1)^{n+1}\mathcal F_n.$

Ainsi, autour de 0, la séquence est :

$\ldots,\;-8,\;5,\;-3,\;2,\;-1,\;1,\;0,\;1,\;1,\;2,\;3,\;5,\;8,\;\ldots$

[modifier] Limite des quotients

Comme l'avait déjà remarqué Johannes Kepler^[1], le taux de croissance des nombres de Fibonacci, c'est-à-dire $\frac{\mathcal F_{n+1}}{\mathcal F_n}$ , converge vers le nombre d'or, noté $φ$ .

En effet, puisque la suite $\mathcal F_n$ est équivalente à $\frac{\varphi^n}{\sqrt5}$ (cf supra, section Expression fonctionnelle), la suite $\frac{\mathcal F_{n+1}}{\mathcal F_n}$ est équivalente à $\frac{\frac{\varphi^{n+1}}{\sqrt5}}{\frac{\varphi^n}{\sqrt5}}=\varphi,$ 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é.

[modifier] Bases et espaces vectoriels

La dénomination de « suite de Fibonacci généralisée » est attribuée plus généralement à toute fonction $\mathcal G$ définie sur ${}^\N$ vérifiant pour tout entier naturel $n$ , $\mathcal G_{n+2}=\mathcal G_{n+1}+\mathcal G_n$ . Ces fonctions sont précisément celles pour lesquelles il existe des nombres a et b, tels que pour tout entier naturel n, $\mathcal G_n = a{}\cdot{}\mathcal F_n+b{}\cdot{}\mathcal F_{n+1}$ . Ainsi, l'ensemble des suites de Fibonacci est un espace vectoriel, et les suites $(\mathcal F_n)$ et $(\mathcal F_{n+1})$ en forment une base.

Le nombre d'or est la racine positive de l'équation du second degré $x^2 - x - 1 = 0\,$ , ainsi $\varphi^2 = \varphi + 1\,$ . Si on multiplie les deux côtés par $\varphi^n\,$ , on obtient $\varphi^{n+2} = \varphi^{n+1} + \varphi^n\,$ , donc la fonction $n\mapsto \varphi^n$ est une suite de Fibonacci. La racine négative de l'équation du second degré, $\varphi'=1-\varphi\,$ , 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.

[modifier] Algorithmes de calcul des nombres de Fibonacci

[modifier] 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é. En général, on obtient les bonnes valeurs jusqu’à $\mathcal F_{71}$ = 308 061 521 170 130, sur ordinateur ou sur calculatrice.

Notons qu’au-delà de $\mathcal F_{79}$ , 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 $\mathcal F_{50}$ .

Le nombre d’or vaut $\varphi=\frac{1+\sqrt5}2\ \approx$ 1,618 033 988 749 89…, et d'après la formule de Binet, $\mathcal F_{50}$ est l'entier le plus proche du réel $\frac{\varphi^{50}}{\sqrt 5}$ , 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,618 033 988 749 89 est une approximation suffisante de $φ$ .

On trouve que le réel (1,618 033 988 749 89)⁵⁰/ $\sqrt 5$ est à peine inférieur à l'entier 12 586 269 025, d'où

$\mathcal F_{50}\approx\frac{\varphi^n}{\sqrt5}\approx 12586269025~,$

si bien que

$\mathcal F_{50} = 12586269025~.$

[modifier] Algorithme récursif naïf

La mise en œuvre récursive naïve qui suit la définition de la suite de Fibonacci est immédiate en appliquant la fonction donnée par l'algorithme suivant :

fonction fibo(n): 
// entrée : un nombre entier n
// sortie : le terme de rang n de la suite de Fibonacci
//
// deux premiers cas : fibo(0) est égal à 0 et fibo(1) est égal à 1
si (n <= 1)
  retourner n 
// récurrence à partir du terme de rang 2  
sinon 
  retourner fibo(n - 1) + fibo(n - 2)
fin de la fonction

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 (à moins d'employer une technique de mémoization). Le temps de calcul s'avère exponentiel.

[modifier] Algorithme linéaire

Un moyen bien plus efficace de calculer la suite de Fibonacci consiste à calculer simultanément deux valeurs consécutives de la suite, c'est-à-dire 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.

En Python, un tel algorithme itératif donne :

def fibo(n):
    f_n_1 = 1  # F_{-1} = 1
    f_n = 0    # F_0 = 0
    for i in range(n):  # n fois
        (f_n_1, f_n) = (f_n, f_n + f_n_1)
    return f_n

De manière équivalente, on peut écrire une fonction récursive terminale :

def fibo(n, f_n_1 = 1, f_n = 0):  # (n, F_{n-1}, F_n)
    if (n == 0):  # cas de base
        return f_n
    else:         # récurrence
        return fibo(n - 1, f_n, f_n + f_n_1)

Le temps de calcul est à chaque fois proportionnel à n mais l'espace mémoire occupé n'est pas constant dans le second cas car Python n'optimise pas la récursivité terminale (au contraire du langage Scheme par exemple). La récursivité terminale n'est pas encouragée en Python, qui lui préfère un véritable itérateur !

[modifier] Algorithme logarithmique

En utilisant la relation matricielle suivante, que l'on montre par récurrence :

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} \mathcal F_{n+1} & \mathcal F_n \\ \mathcal F_n & \mathcal F_{n-1} \end{pmatrix}$

ou avec les propriétés de la suite de Fibonacci, on obtient :

$\mathcal F_{2k} = 2\mathcal F_{k-1} \mathcal F_k + \mathcal F_k^2 = (2 \mathcal F_{k-1} + \mathcal F_k) \mathcal F_k$

$\mathcal F_{2k+1} = \mathcal F_{k+1}^2 + \mathcal F_k^2$

En prenant bien soin de ne pas calculer deux fois les mêmes éléments, on obtient alors un algorithme dont le temps de calcul est proportionnel au logarithme de n. Voici un exemple de programme en Python :

def fibo2(n):
    """Renvoie F_{n-1}, F_n"""
    if (n == 0):  # cas de base
        return 1, 0  # F_{-1}, F_0
    else:         # récurrence
        f_k_1, f_k = fibo2(n//2)        # F_{k-1}, F_k   avec k = n/2
        f2_k = f_k**2                   # F_k^2
        if n%2 == 0:  # n pair
            return f2_k + f_k_1**2,    f_k*f_k_1*2 + f2_k       # F_{2k-1}, F_{2k}
        else:         # n impair
            return f_k*f_k_1*2 + f2_k, (f_k + f_k_1)**2 + f2_k  # F_{2k},   F_{2k+1}
 
def fibo(n):
    """Renvoie F_n"""
    return fibo2(n)[1]

En retravaillant les relations de récurrence pour le cas pair on obtient :

$\mathcal F_{2k} = \mathcal F_{2k+1} - \mathcal F_{2k-1} = (\mathcal F_{k+1}^2 + \mathcal F_k^2) - (\mathcal F_k^2 + \mathcal F_{k-1}^2) = \mathcal F_{k+1}^2 - \mathcal F_{k-1}^2$

Et donc :

$\forall n\in\Z,~\mathcal F_n=\mathcal F_{\lfloor\frac{n}{2}\rfloor+1}^2-(-1)^n\mathcal F_{\lfloor\frac{n-1}2\rfloor}^2.$

[modifier] Curiosité algorithmique

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] et appliqué à l'entier 3 génère une suite qui contient tous les termes de la forme $2 a 3 b$ , où $a$ et $b$ sont deux termes consécutifs de la suite de Fibonacci.

[modifier] Propriétés de la suite de Fibonacci

La suite de Fibonacci présente de remarquables propriétés. En voici quelques-unes, démontrées à 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 précédent). Nous donnons également quelques propriétés liant la suite de Fibonacci et la suite des nombres de Lucas $\mathcal L_n$ définie par la même relation de récurrence mais avec pour initialisation $\mathcal L_0=2$ et $\mathcal L_1=1$ , et pour laquelle l'analogue de la formule de Binet est : $\mathcal L_n=\varphi^n+\varphi'^n$ .

Propriété 1 : $\forall(p,q,r)\in\Z^3,\mathcal F_p\mathcal F_{q+r}-(-1)^r\mathcal F_{p-r}\mathcal F_q=\mathcal F_{p+q}\mathcal F_r,$ ou encore : $\mathcal F_p\mathcal F_{r+q}-\mathcal F_r\mathcal F_{p+q}=(-1)^r\mathcal F_{p-r}\mathcal F_q.$

Démonstration

$\begin{align}\mathcal F_p\mathcal F_{q+r}-(-1)^r\mathcal F_{p-r}\mathcal F_q&=\frac15\left((\varphi^p+(-1)^{p+1}\varphi^{-p})(\varphi^{q+r}+(-1)^{q+r+1}\varphi^{-q-r})+(-1)^{r+1}(\varphi^{p-r}+(-1)^{p-r+1}\varphi^{r-p})(\varphi^q+(-1)^{q+1}\varphi^{-q})\right)\\&=\frac15\left(\varphi^{p+q+r}+(-1)^{p+q+r}\varphi^{-p-q-r}+(-1)^{r+1}\varphi^{p+q-r}+(-1)^{p+q+1}\varphi^{r-p-q}\right)\\&=\frac{\varphi^{p+q}-(-1)^{p+q}\varphi^{-p-q}}{\sqrt5}\times\frac{\varphi^r-(-1)^r\varphi^{-r}}{\sqrt5}\\&=\mathcal F_{p+q}\times\mathcal F_r.\end{align}$

Propriété 2 : $\forall(p,q)\in\Z^2,\mathcal F_p\mathcal F_{q+1}+\mathcal F_{p-1}\mathcal F_q=\mathcal F_{p+q}.$

C'est le cas

r = 1

de la propriété 1.

Propriété 3 : $\forall p\in\Z,\mathcal F_{2p-1}=\mathcal F_{p-1}^2+\mathcal F_p^2.$

C'est le cas

q = p - 1

de la propriété 2.

Propriété 4 : $\forall(p,r)\in\Z^2,\mathcal F_p\mathcal F_{r+1}-\mathcal F_r\mathcal F_{p+1}=(-1)^r\mathcal F_{p-r}.$

C'est le cas

q = 1

de la propriété 1.

Propriété 5 : $\forall(p,q)\in\Z^2,\mathcal F_p^2-\mathcal F_{p-q}\mathcal F_{p+q}=(-1)^{p-q}\mathcal F_q^2$ (identité de Catalan) et $\mathcal F_{p+1}\mathcal F_{p-1}-\mathcal F_p^2=(-1)^p$ (identité de Cassini).

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 : $\forall p\in\Z, \mathcal F_p=\frac{\mathcal F_{p-1}+\sqrt{5\mathcal F_{p-1}^2-4(-1)^p}}2~\text{et}~\sqrt{5\mathcal F_p^2+4(-1)^p}\in\N.$

Démonstration

Pour prouver la première propriété, il suffit de considérer l'identité de Cassini $(\mathcal F_p+\mathcal F_{p-1})\mathcal F_{p-1}-\mathcal F_p^2=(-1)^p$ et de résoudre l'équation du second degré obtenue d'inconnue $\mathcal F_p$ , à savoir $\mathcal F_p^2-\mathcal F_{p-1}\mathcal F_p-\mathcal F_{p-1}^2+(-1)^p=0.$

La suite de Fibonnacci apparaît également comme une suite récurrente du premier ordre, mais non linéaire.

Pour en déduire la fin du corollaire, on fait un petit décalage d'indice dans la formule précédente, en remarquant que les termes de la suite de Fibonacci sont entiers.

Corollaire 2 : $\forall p\in\Z,\mathcal F_{p+2}\mathcal F_{p+1}\mathcal F_{p-1}\mathcal F_{p-2}-\mathcal F_p^4+1=0.$

Démonstration

$\begin{align}\mathcal F_{p+1}\mathcal F_{p-1}\mathcal F_{p+2}\mathcal F_{p-2}&=(\mathcal F_p^2-(-1)^{p-1}\mathcal F_1^2)(\mathcal F_p^2-(-1)^{p-2}\mathcal F_2^2)\\&=(\mathcal F_p^2\pm1)(\mathcal F_p^2\mp1)\\&=\mathcal F_p^4-1.\end{align}$

Propriété 6 : $\forall (k,n)\in\Z^2,\mathcal F_n{}|{}\mathcal F_{nk},$ en particulier $\mathcal F_{2n}=\mathcal F_n\mathcal L_n.$

Démonstration

Le cas $n k = 0$ est immédiat et le cas $k < 0$ se déduit du cas $k > 0$ . On peut donc supposer $k > 0$ et ${}^{n\ne0}$ .

$\begin{align}\frac{\mathcal F_{nk}}{\mathcal F_n}&=\frac{\varphi^{nk}-\varphi'^{nk}}{\varphi^n-\varphi'^n}=\sum_{j=0}^{k-1}\varphi^{n(k-1-j)}\varphi'^{nj}\\&=(\varphi^{n(k-1)}+\varphi'^{n(k-1)})+(\varphi^{n(k-2)}\varphi'^n+\varphi'^{n(k-2)}\varphi^n)+(\varphi^{n(k-3)}\varphi'^{2n}+\varphi'^{n(k-3)}\varphi^{2n})+\ldots\\&=(\varphi^{n(k-1)}+\varphi'^{n(k-1)})+(-1)^n(\varphi^{n(k-3)}+\varphi'^{n(k-3)})+(\varphi^{n(k-5)}+\varphi'^{n(k-5)})+\ldots\\&=\mathcal L_{n(k-1)}+(-1)^n\mathcal L_{n(k-3)}+\mathcal L_{n(k-5)}+\ldots\in\Z. \end{align}$

En particulier,

$\frac{\mathcal F_{2n}}{\mathcal F_n}=\frac{\varphi^{2n}-\varphi'^{2n}}{\varphi^n-\varphi'^n}=\varphi^n+\varphi'^n=\mathcal L_n.$

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

Ou par contraposée : si

n

est composé alors $\mathcal F_n$ aussi. En effet, supposons

n = m k

avec

m

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, $\mathcal F_m$ est alors un diviseur propre de $\mathcal F_n$ , qui n'est donc pas premier.

La réciproque est fausse, car 2 est premier alors que $\mathcal F_2$ ne l'est pas ; de façon moins triviale, $\mathcal F_{19}=4181=37\times 113$ .

Propriété 8 : $\forall(a,b)\in\Z\times\Z^*,~\mathcal F_a\land\mathcal F_b=\mathcal F_{a\land b},$ où $\land$ désigne le PGCD de nombres entiers.

Démonstration

Soient $d=a\land b$ et $D=\mathcal F_a\land\mathcal F_b$ (qui sont tous deux positifs ou nuls).

D'après la propriété 6, $\mathcal F_d~|~\mathcal F_a$ et $\mathcal F_d~|~\mathcal F_b$ et donc $\mathcal F_d{}|{}D$ .
D'après le théorème de Bézout, il existe deux entiers $x$ et $y$ tels que $d = a x + b y$ . Posons alors $p = a x$ et $q = b y$ . Comme $D~$ divise $\mathcal F_a$ et $\mathcal F_b$ , il divise aussi $\mathcal F_p$ et $\mathcal F_q$ d'après la propriété 6, donc également $\mathcal F_{p+q}$ d'après la propriété 2, autrement dit $D~|~\mathcal F_d$ .
Ainsi, $\mathcal F_d$ est égal ou opposé à $D$ . Comme il est positif ou nul (car $d$ l'est), nous en concluons que $\mathcal F_d=D$ .

En particulier, $\forall n\in\Z,\mathcal F_n\land\mathcal F_{n+1}=1$ c.-à-d. que $\mathcal F_n$ et $\mathcal F_{n+1}$ sont premiers entre eux.

Propriété 9 : $\forall(n,k)\in\Z^2,\mathcal F_{n+k}-(-1)^k\mathcal F_{n-k}=\mathcal F_k\mathcal L_n.$ En particulier :

$\mathcal F_{n+1}+\mathcal F_{n-1}=\mathcal L_n,\quad\mathcal F_{n+2}-\mathcal F_{n-2}=\mathcal L_n,\quad\mathcal F_{n+3}+\mathcal F_{n-3}=2\mathcal L_n.$

Démonstration

$\begin{align}\mathcal F_{n+k}-(-1)^k\mathcal F_{n-k}&=\frac1{\sqrt5}(\varphi^{n+k}+(-1)^{n+k+1}\varphi^{-n-k}+(-1)^{k+1}\varphi^{n-k}+(-1)^n\varphi^{k-n})\\&=(\varphi^n+(-1)^n\varphi^{-n})\frac{\varphi^k+(-1)^{k+1}\varphi^{-k}}{\sqrt5}\\&=\mathcal L_n\mathcal F_k. \end{align}$

Propriété 10 : $\forall n\in\Z,\varphi^n=\mathcal F_n\varphi+\mathcal F_{n-1}~\text{et}~\varphi'^n=\mathcal F_n\varphi'+\mathcal F_{n-1}.$

Démonstration

Par somme et différence, il revient au même de démontrer que

$\mathcal L_n=\mathcal F_n\mathcal L_1+2\mathcal F_{n-1}~\text{et}~\mathcal F_n=\mathcal F_n\mathcal F_1.$

La seconde égalité est immédiate et la première résulte de la propriété 9 :

$\mathcal L_n=\mathcal F_{n+1}+\mathcal F_{n-1}=(\mathcal F_n+\mathcal F_{n-1})+\mathcal F_{n-1}.$

Propriété 11 : $\forall n\in\N,\quad\sum_{0\le i<n}\mathcal F_{2i+1}=\mathcal F_{2n},\quad1+\sum_{0\le i<n}\mathcal F_{2i}=\mathcal F_{2n-1}\quad\text{et}\quad1+\sum_{0\le i<n}\mathcal F_i=\mathcal F_{n+1}.$

Démonstration

Les deux premières égalités s'obtiennent par somme télescopique :

$\sum_{0\le i<n}\mathcal F_{2i+1}=\sum_{0\le i<n}(\mathcal F_{2i+2}-\mathcal F_{2i})=\mathcal F_{2n}-\mathcal F_0=\mathcal F_{2n}\quad\text{et}$

$\sum_{0\le i<n}\mathcal F_{2i}=\sum_{0\le i<n}(\mathcal F_{2i+1}-\mathcal F_{2i-1})=\mathcal F_{2n-1}-\mathcal F_{-1}=\mathcal F_{2n-1}-1.$

La troisième s'en déduit en les additionnant, de façon différente suivant la parité de $n$ :

$\text{si}\quad n=2m,\quad\sum_{0\le i<n}\mathcal F_i=\sum_{0\le k<m}\mathcal F_{2k}+\sum_{0\le k<m}\mathcal F_{2k+1}=(\mathcal F_{2m-1}-1)+\mathcal F_{2m}=\mathcal F_{2m+1}-1=\mathcal F_{n+1}-1,$

$\text{si}\quad n=2m+1,\quad\sum_{0\le i<n}\mathcal F_i=\sum_{0\le k\le m}\mathcal F_{2k}+\sum_{0\le k<m}\mathcal F_{2k+1}=(\mathcal F_{2m+1}-1)+\mathcal F_{2m}=\mathcal F_{2m+2}-1=\mathcal F_{n+1}-1.$

Propriété 12 : $\forall n\in\N,~\mathcal F_{n+1}=\sum_{k=0}^\infty{n-k\choose k}$ où les $n-k\choose k$ sont des coefficients binomiaux.

Démonstration

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_{k=0}^{\infty} {0-k\choose k} = 1$ et $\mathcal{F}_1 = 1$

(n = 1) : $\sum_{k=0}^{\infty} {1-k\choose k} = 1$ et $\mathcal{F}_2 = 1$

Hypothèses de récurrence :

au rang n, $\mathcal{F}_{n+1} = \sum_{k=0}^{\infty} {n - k \choose k}$

au rang n + 1, $\mathcal{F}_{n+2} = \sum_{k=0}^{\infty} {n +1 - k \choose k}$

Hérédité (rang n + 2) :

$\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \sum_{k=0}^{\infty} {(n+1) - k \choose k} + {(n+1) - k \choose k-1}$

(Formule du triangle de Pascal)

$\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \sum_{k=0}^{\infty} {(n+1) - k \choose k} + \sum_{k=1}^{\infty}{n - (k - 1) \choose k-1}$

Car ${n+1 \choose -1} = 0$ )

$\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+2}+\sum_{m=0}^{\infty}{n - m \choose m}$

(Hypothèse de récurrence, changement de variable $m = k - 1\,$ )

$\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+2}+ \mathcal{F}_{n+1}$ (Hypothèse de récurrence)

$\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+3}$ (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).

[modifier] Bestiaire de formules

$\forall N\ge1,~\mathcal F_{2N+1}=4^N\cdot\prod_{n=1}^N\left(\cos^2\left(\frac{n\pi}{2N+1}\right)+\frac14\right).$

[modifier] Divisibilité des nombres de Fibonacci

Une première approche de la question de la divisibilité de $\mathcal F_n$ par un entier $a$ consiste à étudier la suite des restes de $\mathcal F_n$ modulo $a$ : cette suite ( $r n$ ) vérifie (dans Z/aZ) la même récurrence ( $r n + 2 = r n + 1 + r n$ ) et est donc périodique de période au plus $a 2$ (les longueurs des périodes en fonction de $n$ forment la suite des périodes de Pisano (en) suite A001175 de l’OEIS) ; on en déduit que pour tout $a$ , il existe $n$ inférieur ou égal à $a 2$ tel que $\mathcal F_n$ (et donc $\mathcal F_{kn}$ ) 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 $\mathcal F_{5n}$ est divisible par 5, et que si p est premier autre que 5, $\mathcal F_{(p-1)n}$ est divisible par p si p est de la forme 5m+1 ou 5m+4, et $\mathcal F_{(p+1)n}$ est divisible par p sinon (des résultats un peu plus précis peuvent être obtenus ; ainsi, dans le premier cas, $\mathcal F_{(p-1)/2}$ est divisible par p si (p-1)/2 est pair). Enfin, si p>2 est premier et divise $\mathcal F_n$ , p^k divise $\mathcal F_{p^{k-1}n}$ , et 2^k+1 divise $\mathcal F_{3.2^{k-1}}$ ; ces derniers résultats sont des conséquences du lemme de Hensel^[2]^,^[3].

[modifier] Primalité des nombres de Fibonacci

On ignore s'il existe une infinité de nombres de Fibonacci premiers. On sait que $\mathcal F_n$ divise $\mathcal F_{kn}$ (voir Propriétés, Propriété 6), et donc que, pour tout $n >4\,$ , si $\mathcal F_n$ est premier, alors $n\,$ est premier, mais la réciproque est fausse ( $\mathcal F_{19}=4181=37\times 113$ est le premier contre-exemple non trivial). À ce jour (août 2011), le plus grand nombre premier de Fibonacci connu est $\mathcal F_{81~839}$ ^[4] et le plus grand nombre de Fibonacci probablement premier connu est $\mathcal F_{1~636~007}$ ^[5], qui possède 341 905 chiffres.

Depuis 1964, on connait des suites $(\mathcal T_n)$ vérifiant en même temps les trois conditions suivantes :

$\mathcal T_{n+2}=\mathcal T_{n+1}+\mathcal T_n$
$\mathcal T_n{}$ et $\mathcal T_{n+1}$ sont premiers entre eux (ils n'ont aucun diviseur commun).
$\forall n\in\N,\; \mathcal T_n$ n'est pas premier.

Par exemple:

suite A082411 de l’OEIS (John Nicol, 1999) déterminée par :
- $\mathcal T_0=407~389~224~418$
- $\mathcal T_1=76~343~678~551$
suite A083216 de l’OEIS (Herbert Wilf (en), 1990) déterminée par :
- $\mathcal T_0=20~615~674~205~555~510=2\cdot 5\cdot 5623\cdot 366~631~232~537$
- $\mathcal T_1=3~794~765~361~567~513=3\cdot 1~264~921~787~189~171$
et suite A083103 de l’OEIS (Robert Graham, 1964 ; non vérifiée, selon l'OEIS) déterminée par:
- $\mathcal T_0=1786772701928802632268715130455793 = 2521\cdot 49993\cdot 14177095479037851751198481$
- $\mathcal T_1 = 1059683225053915111058165141686995 = 3\cdot 5\cdot 84089\cdot 73919059\cdot 150031897\cdot 75754002239$

[modifier] Applications

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'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. J.-C.). Le mathématicien indien Virahanka (en) en a donné des règles explicites au VIII^e siècle. Le philosophe indien Acharya Hemachandra (en) (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 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 $2 x y 4 + x 2 y 3 - 2 x 3 y 2 - y 5 - x 4 y + 2 y$ é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é 12).

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 F_1$ unités vers la droite, puis de $\mathcal F_2$ unités vers le haut, on se déplace de $\mathcal F_3$ unités vers la gauche, ensuite de $\mathcal F_4$ unités vers le bas, puis de $\mathcal F_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. Depuis l'antiquité grecque, la suite est également utilisée par les architectes afin de définir l'agencement et les proportions des différentes pièces d'un logement.

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 ici une explication et le lien avec le nombre d'or dans la nature.

La plupart des êtres vivants sexués sont issus de deux parents, de sorte que leurs ancêtres à la n^e génération, supposés distincts, sont au nombre de 2ⁿ. 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^e génération sont constitués :

pour les femelles, de $\mathcal F_n$ mâles et $\mathcal F_{n+1}$ femelles,

pour les mâles, de $\mathcal F_{n-1}$ 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_{N+1}$ .

Démonstration

Par récurrence sur N que l'on considéra comme la longueur horizontale du rectangle 2×N :

Initialisation :

Le rectangle 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_{N+1}$ façons de paver le rectangle 2×N.
Considérons le rectangle 2×(N+1) :
- 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_{N+1}$ 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_{N} + \mathcal F_{N+1} = \mathcal F_{N+2}$ , ce qui termine le raisonnement par récurrence.

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

[modifier] 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 1. Sur le modèle de la démonstration donnée plus haut (voir section Expression fonctionnelle), une telle suite $u n$ est encore de la forme $αφ n + βφ' n$ où $φ$ est le nombre d'or et $φ' = - 1 / φ.$ Elle est donc équivalente à $αφ n$ , si bien que (comme la suite des quotients de la suite de Fibonacci) la suite $\frac{u_{n+1}}{u_n}$ converge vers $φ$ .

Parmi ces suites de nombres, il faut signaler les nombres de Lucas obtenus en choisissant comme initialisation : $\mathcal L_0=2$ et $\mathcal L_1=1$ . Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29, … On trouve parfois une initialisation $\mathcal L_0 =1$ et $\mathcal 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 L_n=\mathcal F_{n+1}+\mathcal F_{n-1}\,$ pour tout entier n strictement positif (voir Propriétés, Propriété 9).

[modifier] Suites de Lucas

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

$U_{n+2} = P \cdot U_n + Q \cdot U_{n+1}$

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$ .

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

[modifier] 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_{n+k} \, = \, u_n + u_{n+1} + u_{n+2} + \dots +u_{n+k - 1}$

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.

[modifier] La suite de Fibonacci dans la culture populaire

[modifier] Littérature

Da Vinci Code, de Dan Brown
Maya Fox 2012, tome 1 : La prédestinée, de Silvia Brena et Iginio Straffi
La Confrérie des Invisibles, de Kurt Aust (en)
Le problème avec les lapins, d'Emily Gravett
Les Pyramides de Napoléon, de William Dietrich

[modifier] Cinéma

Π (film)
Le nombre 23
Crimes à Oxford
Las Vegas 21
Jean de Florette
Da Vinci Code
L : Change the WorLd

[modifier] Télévision

Numb3rs (épisodes 6, 21 des saison 1, 5)
Fringe (épisode 10 de la saison 1)
Chuck (épisode 7 de la saison 2)
Alias
Lost
Esprits Criminels (épisode 8 de la saison 4)
Disparition
Touch (série télévisée)

[modifier] Musique

Le groupe de metal progressif Tool structure le rythme de certaines parties du morceau Lateralus selon une suite de Fibonacci^[6].

[modifier] Architecture

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

[modifier] Notes et références

↑ (la) J. Kepler, Strena seu de nive sexangula, 1611
↑ (en) Paulo Ribenboim, The New Book of Prime Number Records, New York, Springer, 1996 (ISBN 0-387-94457-5), p. 64
↑ (en) Franz Lemmermeyer (de), Reciprocity Laws, New York, Springer, 2000 (ISBN 3-540-66957-4), ex. 2.25–2.28, p. 73–74
↑ (en) Fibonacci Number, sur le site Prime Pages
↑ suite A001605 de l’OEIS
↑ (en) Christopher diCarlo, Interview with Maynard James Keenan [lire en ligne]

[modifier] Voir aussi

[modifier] Bibliographie

N. Vorobiev, Caractères de Divisibilité, Suite de Fibonacci, coll. Initiation aux Mathématiques, Editions Mir, Moscou, 1973

[modifier] Articles connexes

Groupe de Fibonacci
Suite de Padovan
Nombre d'or
Mot de Fibonacci
Polynôme de Fibonacci (en)
Codage de Fibonacci
The Fibonacci Association (en) et sa revue, Fibonacci Quarterly

[modifier] Liens externes

Divisibilité des nombres de Fibonacci
Suite de Fibonacci et nombre d'or dans l'ensemble de Mandelbrot
Suite de Fibonacci dans le dictionnaire des nombres
Les suites de Fibonacci aléatoires, conférence de Benoît Rittaud à la Cité des sciences et de l'industrie

Suite de Fibonacci

Sommaire

[modifier] Présentation mathématique

[modifier] Formule de récurrence

[modifier] Nombres de Fibonacci

[modifier] Expression fonctionnelle

[modifier] La suite pour les nombres négatifs

[modifier] Limite des quotients

[modifier] Bases et espaces vectoriels

[modifier] Algorithmes de calcul des nombres de Fibonacci

[modifier] Avec la formule de Binet

[modifier] Algorithme récursif naïf

[modifier] Algorithme linéaire

[modifier] Algorithme logarithmique

[modifier] Curiosité algorithmique

[modifier] Propriétés de la suite de Fibonacci

[modifier] Bestiaire de formules

[modifier] Divisibilité des nombres de Fibonacci

[modifier] Primalité des nombres de Fibonacci

[modifier] Applications

[modifier] Généralisations

[modifier] Suites de Fibonacci généralisées

[modifier] Suites de Lucas

[modifier] Suites de k-bonacci

[modifier] La suite de Fibonacci dans la culture populaire

[modifier] Littérature

[modifier] Cinéma

[modifier] Télévision

[modifier] Musique

[modifier] Architecture

[modifier] Notes et références

[modifier] Voir aussi

[modifier] Bibliographie

[modifier] Articles connexes

[modifier] Liens externes

Rechercher

Menu

Espace membre

Changer d'île