Suite de Fibonacci (original) (raw)

Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci :
1, 1, 2, 3, 5, 8, 13 et 21.

En mathématiques, la suite de Fibonacci, tirant son nom du mathématicien italien Fibonacci, est une suite de nombres entiers dans laquelle chaque nombre est la somme des deux nombres qui le précèdent. Elle commence par les nombres 0 et 1[1] puis se poursuit avec :

Les termes de cette suite, c'est-à-dire les nombres apparaissant dans cette suite, sont appelés nombres de Fibonacci.

La suite de Fibonacci est répertoriée comme suite A000045 de l'OEIS.

Elle est liée au nombre d'or, noté φ (phi), qui 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.

La suite de Fibonacci ( F n ) n ∈ N {\displaystyle (F_{n})_{n\in \mathbb {N} }} {\displaystyle (F_{n})_{n\in \mathbb {N} }} est définie par F 0 = 0 , F 1 = 1 {\displaystyle F_{0}=0,\quad F_{1}=1} {\displaystyle F_{0}=0,\quad F_{1}=1}, et la relation de récurrence F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} {\displaystyle F_{n}=F_{n-1}+F_{n-2}} pour n ⩾ 2 {\displaystyle n\geqslant 2} {\displaystyle n\geqslant 2}. Le tableau suivant donne les 15 premiers termes de la suite de Fibonacci :

_F_0 _F_1 _F_2 _F_3 _F_4 _F_5 _F_6 _F_7 _F_8 _F_9 _F_10 _F_11 _F_12 _F_13 _F_14 _F_15 ... Fn
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... F n – 1 + F n – 2

Dans cet article, nous avons fait commencer la suite à n = 0 {\displaystyle n=0} {\displaystyle n=0} avec F 0 = 0 {\displaystyle F_{0}=0} {\displaystyle F_{0}=0}, comme le fait Édouard Lucas[1]. D'autres auteurs font débuter la suite à 1[2] : f 0 = f 1 = 1 , f 2 = 2 , f 3 = 3 , f 4 = 5 {\displaystyle f_{0}=f_{1}=1,f_{2}=2,f_{3}=3,f_{4}=5} {\displaystyle f_{0}=f_{1}=1,f_{2}=2,f_{3}=3,f_{4}=5}, etc. Le nombre Fn s'appelle parfois le _n_-ième nombre de Fibonacci[2] (bien qu'il soit techniquement le n+1-ième si on commence à 0).

Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.

Treize (_F_7) façons d'alterner courtes et longues syllabes dans un vers de six mātrās. Huit (_F_6) finissent par une courte syllabe et cinq (_F_5) par une longue syllabe.

Dans la branche des mathématiques concernant la combinatoire, les mathématiciens indiens s'intéressent à des problèmes de lexicographie et de métrique. Le mètre āryā (en) est composé de syllabes pouvant être brèves (de longueur un mātrā) ou longues (de longueur deux mātrās).

La question est de savoir comment peuvent s'alterner les brèves et les longues dans un vers de n mātrās. Ce problème apparaît très tôt en Inde, sous le nom maatraameru (montagne de cadence), dans le travail du grammairien du sanskrit, Pingala, auteur du Chhandah-shastra (l'art de la Prosodie), vers 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) ainsi que Gopala (c. 1135) ont revisité le problème de manière assez détaillée[3].

Si la syllabe longue L est deux fois plus longue que la syllabe courte C, 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.

Si on note Sn, le nombre de manière d'alterner les brèves et les longues dans un vers de n mātrās, cette remarque conduit naturellement à la relation de récurrence suivante : S n = S n − 1 + S n − 2 {\displaystyle S_{n}=S_{n-1}+S_{n-2}} {\displaystyle S_{n}=S_{n-1}+S_{n-2}},formule explicitement donnée dans l’œuvre de Virahanka[4].

Une page du Liber abaci de Fibonacci à la bibliothèque nationale de Florence. Sur la droite se trouve la suite de Fibonacci, chaque terme ayant sa position en latin et chiffres romains suivi de sa valeur en chiffres arabes.

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 : « 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. »[5]

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 :

Notons Fn 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 ; on note _F_1 = _F_2 = 1.

Dès le début du troisième mois, le premier couple de lapins atteint l'âge de deux mois et engendre un second couple de lapins ; on note alors _F_3 = 2.

Plaçons-nous maintenant au mois n et cherchons à exprimer ce qu'il en sera deux mois plus tard, soit au mois n + 2 : les F n + 2 couples de lapins sont formés des F n + 1 couples du mois précédent et des couples nouvellement engendrés.

Or, n'engendrent au mois n + 2 que les couples pubères, c'est-à-dire ceux qui existaient déjà deux mois auparavant, qui sont en nombre Fn. On a donc, pour tout entier n strictement positif :

F n + 2 = F n + 1 + F n {\displaystyle F_{n+2}=F_{n+1}+F_{n}} {\displaystyle F_{n+2}=F_{n+1}+F_{n}}.

On choisit alors de poser F 0 = 0 {\displaystyle F_{0}=0} {\displaystyle F_{0}=0}, de manière que cette relation soit encore vérifiée pour n = 0 {\displaystyle n=0} {\displaystyle 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, _F_1 et _F_0, qui sont connus.

Chez une population à la croissance idéale, les nombres de couples de lapins forment la suite de Fibonacci. À la fin du _n_-ième mois, le nombre de couples est égal à Fn.

Il existe plusieurs façons d'obtenir une expression mathématique du n-ième terme de la suite de Fibonacci.

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[6], qui avait déjà été obtenue par de Moivre[réf. nécessaire] en 1718 et par Euler en 1765[7]. Cette expression fonctionnelle s'appelle la formule de Binet :

F n = 1 5 ( φ n − φ ′ n ) , avec φ = 1 + 5 2 et φ ′ = 1 − 5 2 = − 1 φ {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(\varphi ^{n}-\varphi '^{n}),\qquad {\text{avec}}\qquad \varphi ={\frac {1+{\sqrt {5}}}{2}}\qquad {\text{et}}\qquad \varphi '={\frac {1-{\sqrt {5}}}{2}}=-{\frac {1}{\varphi }}} {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(\varphi ^{n}-\varphi '^{n}),\qquad {\text{avec}}\qquad \varphi ={\frac {1+{\sqrt {5}}}{2}}\qquad {\text{et}}\qquad \varphi '={\frac {1-{\sqrt {5}}}{2}}=-{\frac {1}{\varphi }}}

Démonstration

Comme la suite de Fibonacci est linéairement récurrente d’ordre 2, son équation caractéristique est une équation du second degré :

x 2 − x − 1 = 0 {\displaystyle x^{2}-x-1=0} {\displaystyle x^{2}-x-1=0},

dont les deux solutions sont :

φ = 1 + 5 2 et φ ′ = − 1 φ = 1 − 5 2 {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\qquad {\text{et}}\qquad \varphi '=-{\frac {1}{\varphi }}={\frac {1-{\sqrt {5}}}{2}}} {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\qquad {\text{et}}\qquad \varphi '=-{\frac {1}{\varphi }}={\frac {1-{\sqrt {5}}}{2}}},

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 + un. Il en résulte que :

F n = α φ n + β φ ′ n {\displaystyle F_{n}=\alpha {}\varphi ^{n}+\beta \varphi '^{n}} {\displaystyle F_{n}=\alpha {}\varphi ^{n}+\beta \varphi '^{n}} où α et β sont des constantes à déterminer à partir de _F_0 et _F_1.

Les conditions initiales _F_0 = 0 et _F_1 = 1 conduisent au système suivant :

{ α + β = 0 α − β = 2 5 {\displaystyle \left\{{\begin{matrix}\alpha +\beta =0\\\alpha -\beta ={\frac {2}{\sqrt {5}}}\end{matrix}}\right.} {\displaystyle \left\{{\begin{matrix}\alpha +\beta =0\\\alpha -\beta ={\frac {2}{\sqrt {5}}}\end{matrix}}\right.}

On obtient alors :

α = 1 5 et β = − 1 5 . {\displaystyle \alpha ={\frac {1}{\sqrt {5}}}\qquad {\text{et}}\qquad \beta =-{\frac {1}{\sqrt {5}}}.} {\displaystyle \alpha ={\frac {1}{\sqrt {5}}}\qquad {\text{et}}\qquad \beta =-{\frac {1}{\sqrt {5}}}.}

Nous obtenons finalement l'expression fonctionnelle recherchée.

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

Quand n tend vers +∞, Fn est équivalent à φ n 5 {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}. Plus précisément, φn tend vers l'infini et φ' n tend vers zéro car | φ ′ | < 1 < φ {\displaystyle |\varphi '|<1<\varphi } {\displaystyle |\varphi '|<1<\varphi }.

En fait, dès le rang n = 1, φ ′ n 5 {\displaystyle {\varphi '^{n} \over {\sqrt {5}}}} {\displaystyle {\varphi '^{n} \over {\sqrt {5}}}} est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir de φ n 5 {\displaystyle {\varphi ^{n} \over {\sqrt {5}}}} {\displaystyle {\varphi ^{n} \over {\sqrt {5}}}}:

Fn est l'entier le plus proche de φ n 5 {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} (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[8]. Remarquons qu'une fois découverte, cette formule se démontre aussi par récurrence (y compris pour n entier négatif).

De la relation [ F n F n − 1 ] = [ 1 1 1 0 ] [ F n − 1 F n − 2 ] {\displaystyle {\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}{\begin{bmatrix}F_{n-1}\\F_{n-2}\end{bmatrix}}} {\displaystyle {\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}{\begin{bmatrix}F_{n-1}\\F_{n-2}\end{bmatrix}}}, on déduit [ F n F n − 1 ] = [ 1 1 1 0 ] n [ 0 1 ] {\displaystyle {\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}0\\1\end{bmatrix}}} {\displaystyle {\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}0\\1\end{bmatrix}}} et [ F n + 1 F n ] = [ 1 1 1 0 ] n [ 1 0 ] {\displaystyle {\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1\\0\end{bmatrix}}} {\displaystyle {\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1\\0\end{bmatrix}}}; ceci permet d'écrire la forme matricielle :

[ 1 1 1 0 ] n = [ F n + 1 F n F n F n − 1 ] {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}} {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}}

En appliquant le déterminant, on obtient simplement l'identité de Cassini (propriété 5 ci-dessous) : F n + 1 F n − 1 − F n 2 = ( − 1 ) n {\displaystyle F_{n+1}F_{n-1}-F_{n}^{2}=(-1)^{n}} {\displaystyle F_{n+1}F_{n-1}-F_{n}^{2}=(-1)^{n}}.

Et en calculant de deux façons [ 1 1 1 0 ] n + m {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n+m}} {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n+m}}, on obtient (propriété 2 ci-dessous) : F n F m + 1 + F n − 1 F m = F n + m {\displaystyle F_{n}F_{m+1}+F_{n-1}F_{m}=F_{n+m}} {\displaystyle F_{n}F_{m+1}+F_{n-1}F_{m}=F_{n+m}}.

En développant par rapport à la première colonne le déterminant d'ordre n :

D n = | 1 b 0 0 ⋯ 0 0 0 0 a 1 b 0 ⋯ 0 0 0 0 0 a 1 b ⋯ 0 0 0 0 0 0 a 1 ⋯ 0 0 0 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0 0 0 0 ⋯ 1 b 0 0 0 0 0 0 ⋯ a 1 b 0 0 0 0 0 ⋯ 0 a 1 b 0 0 0 0 ⋯ 0 0 a 1 | {\displaystyle D_{n}={\begin{vmatrix}1&b&0&0&\cdots &0&0&0&0\\a&1&b&0&\cdots &0&0&0&0\\0&a&1&b&\cdots &0&0&0&0\\0&0&a&1&\cdots &0&0&0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\vdots \\0&0&0&0&\cdots &1&b&0&0\\0&0&0&0&\cdots &a&1&b&0\\0&0&0&0&\cdots &0&a&1&b\\0&0&0&0&\cdots &0&0&a&1\\\end{vmatrix}}} {\displaystyle D_{n}={\begin{vmatrix}1&b&0&0&\cdots &0&0&0&0\\a&1&b&0&\cdots &0&0&0&0\\0&a&1&b&\cdots &0&0&0&0\\0&0&a&1&\cdots &0&0&0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\vdots \\0&0&0&0&\cdots &1&b&0&0\\0&0&0&0&\cdots &a&1&b&0\\0&0&0&0&\cdots &0&a&1&b\\0&0&0&0&\cdots &0&0&a&1\\\end{vmatrix}}},

on obtient Dn = D n – 1 – abD n – 2.

Comme D 1 = 1 , D 2 = 1 − a b {\displaystyle D_{1}=1,D_{2}=1-ab} {\displaystyle D_{1}=1,D_{2}=1-ab}, si ab = –1, on obtient : Dn = F n + 1 d'où, pour n ⩾ 2 {\displaystyle n\geqslant 2} {\displaystyle n\geqslant 2}:

F n = | 1 − 1 0 0 ⋯ 0 0 0 1 1 − 1 0 ⋯ 0 0 0 0 1 1 − 1 ⋯ 0 0 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 0 0 ⋯ 1 1 − 1 0 0 0 0 ⋯ 0 1 1 | ( n − 1 ) × ( n − 1 ) = | 1 i 0 0 ⋯ 0 0 0 i 1 i 0 ⋯ 0 0 0 0 i 1 i ⋯ 0 0 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 0 0 ⋯ i 1 i 0 0 0 0 ⋯ 0 i 1 | ( n − 1 ) × ( n − 1 ) {\displaystyle F_{n}={\begin{vmatrix}1&-1&0&0&\cdots &0&0&0\\1&1&-1&0&\cdots &0&0&0\\0&1&1&-1&\cdots &0&0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots \\0&0&0&0&\cdots &1&1&-1\\0&0&0&0&\cdots &0&1&1\\\end{vmatrix}}_{(n-1)\times {(n-1)}}={\begin{vmatrix}1&i&0&0&\cdots &0&0&0\\i&1&i&0&\cdots &0&0&0\\0&i&1&i&\cdots &0&0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots \\0&0&0&0&\cdots &i&1&i\\0&0&0&0&\cdots &0&i&1\\\end{vmatrix}}_{(n-1)\times {(n-1)}}} {\displaystyle F_{n}={\begin{vmatrix}1&-1&0&0&\cdots &0&0&0\\1&1&-1&0&\cdots &0&0&0\\0&1&1&-1&\cdots &0&0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots \\0&0&0&0&\cdots &1&1&-1\\0&0&0&0&\cdots &0&1&1\\\end{vmatrix}}_{(n-1)\times {(n-1)}}={\begin{vmatrix}1&i&0&0&\cdots &0&0&0\\i&1&i&0&\cdots &0&0&0\\0&i&1&i&\cdots &0&0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots \\0&0&0&0&\cdots &i&1&i\\0&0&0&0&\cdots &0&i&1\\\end{vmatrix}}_{(n-1)\times {(n-1)}}}

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

En effet, puisque la suite Fn est équivalente à φ n 5 {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} {\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}} (cf. supra, section Expression fonctionnelle), la suite F n + 1 F n {\displaystyle {\frac {F_{n+1}}{F_{n}}}} {\displaystyle {\frac {F_{n+1}}{F_{n}}}} est équivalente à φ n + 1 5 φ n 5 = φ {\displaystyle {\frac {\frac {\varphi ^{n+1}}{\sqrt {5}}}{\frac {\varphi ^{n}}{\sqrt {5}}}}=\varphi } {\displaystyle {\frac {\frac {\varphi ^{n+1}}{\sqrt {5}}}{\frac {\varphi ^{n}}{\sqrt {5}}}}=\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é, sauf celles commençant par a et aφ'.

Il a été démontré que la somme ∑ n = 1 ∞ 1 ( F n ) 2 = 2,426 323 … {\displaystyle \sum _{n=1}^{\infty }{\frac {1}{(F_{n})^{2}}}=2{,}426323\dots } {\displaystyle \sum _{n=1}^{\infty }{\frac {1}{(F_{n})^{2}}}=2{,}426323\dots } est un nombre transcendant, voir la suite A105393 de l'OEIS.

F n+1 est égal au nombre de suites finies d'entiers égaux à 1 ou 2 dont la somme est égale à n (ou compositions de n formées des entiers 1 ou 2) [14]. Par exemple F 4 = 3 {\displaystyle F_{4}=3} {\displaystyle F_{4}=3} car 3 = 1 + 1 + 1 = 1 + 2 = 2 + 1 {\displaystyle 3=1+1+1=1+2=2+1} {\displaystyle 3=1+1+1=1+2=2+1}. On peut donc interpréter F n+1 comme :

Démonstration : les compositions de n se terminant par 1 sont obtenues en ajoutant 1 à la fin d'une composition de n − 1 {\displaystyle n-1} {\displaystyle n-1}, celles se terminant par 2 sont obtenues en ajoutant 2 à la fin d'une composition de n − 2 {\displaystyle n-2} {\displaystyle n-2}, donc le nombre C n {\displaystyle C_{n}} {\displaystyle C_{n}} de compositions de n vérifie C n = C n − 1 + C n − 2 {\displaystyle C_{n}=C_{n-1}+C_{n-2}} {\displaystyle C_{n}=C_{n-1}+C_{n-2}}. De plus, C 0 = F 1 = 1 {\displaystyle C_{0}=F_{1}=1} {\displaystyle C_{0}=F_{1}=1} (la composition vide), C 1 = F 2 = 1 {\displaystyle C_{1}=F_{2}=1} {\displaystyle C_{1}=F_{2}=1} (la composition (1)), ce qui montre la relation.

F n+2 est égal au nombre de jeux de pile ou face de longueur n qui ne contiennent pas 2 "pile" consécutifs.

Démonstration : pour former un jeu de longueur n qui ne contient pas 2 "pile" consécutifs on peut commencer par 0, et continuer avec un jeu de longueur n – 1 du même type, soit commencer par 1, 0 et continuer avec un jeu de longueur n – 2 du même type, donc le nombre P n {\displaystyle P_{n}} {\displaystyle P_{n}} de tels jeux vérifie P n = P n − 1 + P n − 2 {\displaystyle P_{n}=P_{n-1}+P_{n-2}} {\displaystyle P_{n}=P_{n-1}+P_{n-2}} ; De plus, P 0 = F 2 = 1 {\displaystyle P_{0}=F_{2}=1} {\displaystyle P_{0}=F_{2}=1} ( jeu de longueur nulle), P 1 = F 3 = 2 {\displaystyle P_{1}=F_{3}=2} {\displaystyle P_{1}=F_{3}=2} ((1) et (0)), ce qui montre la relation.

On en déduit que F n+2 est aussi le nombre de parties de [ [ 1 , n ] ] {\displaystyle [\![1,n]\!]} ![{\displaystyle [![1,n]!]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9742260f2c04dfe897a9b8702005a64dcc12a34) ne contenant pas 2 entiers consécutifs.

Le calcul des nombres de Fibonacci est souvent donné en exemple pour introduire des notions d'algorithmique, comme dans le chapitre 0 du livre Algorithms de Dasgupta et al.[15] ou alors dans le problème 31.3 laissé en exercice dans Introduction à l'algorithmique de Cormen et al.[16] ou l'exercice 2 de la section 1.2.8 de TAOCP, qui est précisément consacrée aux nombres de Fibonacci.

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

Notons[réf. nécessaire] qu’au-delà de _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.

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

Le nombre d’or vaut φ = 1 + 5 2 ≈ 1,618 {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618} {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618} et d'après la formule de Binet, F 50 {\displaystyle F_{50}} {\displaystyle F_{50}} est l'entier le plus proche du réel φ 50 5 {\displaystyle {\frac {\varphi ^{50}}{\sqrt {5}}}} {\displaystyle {\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 , 61803398874989 50 5 {\displaystyle {\frac {1,61803398874989^{50}}{\sqrt {5}}}} {\displaystyle {\frac {1,61803398874989^{50}}{\sqrt {5}}}} est à peine inférieur à l'entier 12 586 269 025, d'où

F 50 ≈ φ 50 5 ≈ 12 586 269 025 {\displaystyle F_{50}\approx {\frac {\varphi ^{50}}{\sqrt {5}}}\approx 12\,586\,269\,025} {\displaystyle F_{50}\approx {\frac {\varphi ^{50}}{\sqrt {5}}}\approx 12\,586\,269\,025},

si bien que

F 50 = 12 586 269 025 {\displaystyle F_{50}=12\,586\,269\,025} {\displaystyle F_{50}=12\,586\,269\,025}.

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 fib(n) si n = 0 renvoyer 0 sinon si n = 1 renvoyer 1 sinon renvoyer fib(n - 1) + fib(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.

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

fonction fib(n) (a, b) ← (0, 1) pour i de 1 à n (a, b) ← (b, a + b) renvoyer a

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(_n_2)[15]. 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[18] pour calculer la suite de Fibonacci.

fonction fib(n, a, b) si n = 0 renvoyer a sinon si n = 1 renvoyer b sinon renvoyer fib(n - 1, b, a + b)

L'appel à fib(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.

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

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

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

fibs !! n

Comme vu ci-dessus, [ 1 1 1 0 ] n = [ F n + 1 F n F n F n − 1 ] {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}} {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}}, on écrit un algorithme qui utilise l'exponentiation rapide pour calculer [ 1 1 1 0 ] n {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}} {\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}}, afin d'en déduire le _n_-iè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 [15]).

La série génératrice de la suite de Fibonacci[8] 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 à ∑ n ∈ N F n z n = z 1 − z − z 2 {\displaystyle \sum _{n\in \mathbb {N} }F_{n}z^{n}={\frac {z}{1-z-z^{2}}}} {\displaystyle \sum _{n\in \mathbb {N} }F_{n}z^{n}={\frac {z}{1-z-z^{2}}}}(donc à z ∑ m ∈ N ( z + z 2 ) m = ∑ m , k ∈ N ( m k ) z 1 + m + k {\displaystyle z\sum _{m\in \mathbb {N} }(z+z^{2})^{m}=\sum _{m,k\in \mathbb {N} }{m \choose k}z^{1+m+k}} {\displaystyle z\sum _{m\in \mathbb {N} }(z+z^{2})^{m}=\sum _{m,k\in \mathbb {N} }{m \choose k}z^{1+m+k}}, où les coefficients binomiaux ( m k ) {\displaystyle m \choose k} {\displaystyle m \choose k} sont nuls pour k > m).

Démonstration

Notons s ( z ) = ∑ n ∈ N F n z n {\displaystyle s(z)=\sum _{n\in \mathbb {N} }F_{n}z^{n}} {\displaystyle s(z)=\sum _{n\in \mathbb {N} }F_{n}z^{n}}.En multipliant les deux membres de la relation de récurrence par z n+2 puis en sommant sur tous les entiers naturels n, on obtient : s ( z ) − F 0 − F 1 z = z ( s ( z ) − F 0 ) + z 2 s ( z ) {\displaystyle s(z)-F_{0}-F_{1}z=z\left(s(z)-F_{0}\right)+z^{2}s(z)} {\displaystyle s(z)-F_{0}-F_{1}z=z\left(s(z)-F_{0}\right)+z^{2}s(z)},c'est-à-dire, compte tenu de _F_0 = 0 et _F_1 = 1 : s ( z ) − z = z s ( z ) + z 2 s ( z ) {\displaystyle s(z)-z=zs(z)+z^{2}s(z)} {\displaystyle s(z)-z=zs(z)+z^{2}s(z)},ou encore ( 1 − z − z 2 ) s ( z ) = z {\displaystyle (1-z-z^{2})s(z)=z} {\displaystyle (1-z-z^{2})s(z)=z}.On peut diviser les deux membres par 1 – z – z_2 puisque z est différent des deux racines –_φ et 1/φ.

En particulier, pour tout réel k > φ, 1 k 2 − k − 1 = ∑ n = 1 ∞ F n × k − ( n + 1 ) {\displaystyle {\frac {1}{k^{2}-k-1}}=\sum _{n=1}^{\infty }F_{n}\times k^{-(n+1)}} {\displaystyle {\frac {1}{k^{2}-k-1}}=\sum _{n=1}^{\infty }F_{n}\times k^{-(n+1)}}.

La suite de Fibonacci présente de remarquables propriétés. Leur recherche et leur étude font l'objet de publications régulières, notamment par l'association d'universitaires « The Fibonacci Association » dans sa revue « The Fibonacci Quarterly », consultable en ligne[21]. Certaines de ces propriétés, que l'on peut démontrer à partir de la formule de Binet, ou par récurrence ou encore à l'aide de l'expression matricielle de la suite, sont indiquées dans cette section. Nous donnons également quelques propriétés liant la suite de Fibonacci et la suite de Lucas (Ln ) définie par la même relation de récurrence mais avec pour initialisation _L_0 = 2 et _L_1 = 1, et pour laquelle l'analogue de la formule de Binet est : L n = φ n + φ ′ n {\displaystyle L_{n}=\varphi ^{n}+\varphi '^{n}} {\displaystyle L_{n}=\varphi ^{n}+\varphi '^{n}}.

Propriété 1 : ∀ ( p , q , r ) ∈ Z 3 , F p F q + r − ( − 1 ) r F p − r F q = F p + q F r {\displaystyle \forall (p,q,r)\in \mathbb {Z} ^{3},F_{p}F_{q+r}-(-1)^{r}F_{p-r}F_{q}=F_{p+q}F_{r}} {\displaystyle \forall (p,q,r)\in \mathbb {Z} ^{3},F_{p}F_{q+r}-(-1)^{r}F_{p-r}F_{q}=F_{p+q}F_{r}}, ou encore : F p F q + r − F r F p + q = ( − 1 ) r F p − r F q {\displaystyle F_{p}F_{q+r}-F_{r}F_{p+q}=(-1)^{r}F_{p-r}F_{q}} {\displaystyle F_{p}F_{q+r}-F_{r}F_{p+q}=(-1)^{r}F_{p-r}F_{q}}.

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 : ∀ ( p , q ) ∈ Z 2 , F p F q + 1 + F p − 1 F q = F p + q {\displaystyle \forall (p,q)\in \mathbb {Z} ^{2},F_{p}F_{q+1}+F_{p-1}F_{q}=F_{p+q}} {\displaystyle \forall (p,q)\in \mathbb {Z} ^{2},F_{p}F_{q+1}+F_{p-1}F_{q}=F_{p+q}}.

C'est le cas r = 1 de la propriété 1[22]. On peut aussi la démontrer à l'aide de l'expression matricielle :

Démonstration

On pose M = [ 1 1 1 0 ] {\displaystyle {\mathcal {M}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}} {\displaystyle {\mathcal {M}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}} et on a donc : M n = [ 1 1 1 0 ] n = [ F n + 1 F n F n F n − 1 ] {\displaystyle {\mathcal {M}}^{n}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}} {\displaystyle {\mathcal {M}}^{n}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}}

On a également : M p + q = M p × M q {\displaystyle {\mathcal {M}}^{p+q}={\mathcal {M}}^{p}\times {\mathcal {M}}^{q}} {\displaystyle {\mathcal {M}}^{p+q}={\mathcal {M}}^{p}\times {\mathcal {M}}^{q}}

Donc : [ F p + q + 1 F p + q F p + q F p + q − 1 ] = [ F p + 1 F p F p F p − 1 ] × [ F q + 1 F q F q F q − 1 ] {\displaystyle {\begin{bmatrix}F_{p+q+1}&F_{p+q}\\F_{p+q}&F_{p+q-1}\end{bmatrix}}={\begin{bmatrix}F_{p+1}&F_{p}\\F_{p}&F_{p-1}\end{bmatrix}}\times {\begin{bmatrix}F_{q+1}&F_{q}\\F_{q}&F_{q-1}\end{bmatrix}}} {\displaystyle {\begin{bmatrix}F_{p+q+1}&F_{p+q}\\F_{p+q}&F_{p+q-1}\end{bmatrix}}={\begin{bmatrix}F_{p+1}&F_{p}\\F_{p}&F_{p-1}\end{bmatrix}}\times {\begin{bmatrix}F_{q+1}&F_{q}\\F_{q}&F_{q-1}\end{bmatrix}}}

En calculant explicitement la valeur de F p + q {\displaystyle F_{p+q}} {\displaystyle F_{p+q}} dans la ligne du bas et colonne de gauche de la première matrice, on trouve la formule recherchée : F p + q = F p × F q + 1 + F p − 1 × F q {\displaystyle F_{p+q}=F_{p}\times F_{q+1}+F_{p-1}\times F_{q}} {\displaystyle F_{p+q}=F_{p}\times F_{q+1}+F_{p-1}\times F_{q}}

Propriété 3 : ∀ p ∈ Z , F 2 p − 1 = F p − 1 2 + F p 2 {\displaystyle \forall p\in \mathbb {Z} ,F_{2p-1}=F_{p-1}^{2}+F_{p}^{2}} {\displaystyle \forall p\in \mathbb {Z} ,F_{2p-1}=F_{p-1}^{2}+F_{p}^{2}}.

C'est le cas q = p − 1 {\displaystyle q=p-1} {\displaystyle q=p-1} de la propriété 2.

Propriété 4 (identité d'Ocagne) : ∀ ( p , r ) ∈ Z 2 , F p F r + 1 − F r F p + 1 = ( − 1 ) r F p − r {\displaystyle \forall (p,r)\in \mathbb {Z} ^{2},F_{p}F_{r+1}-F_{r}F_{p+1}=(-1)^{r}F_{p-r}} {\displaystyle \forall (p,r)\in \mathbb {Z} ^{2},F_{p}F_{r+1}-F_{r}F_{p+1}=(-1)^{r}F_{p-r}}.

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

Propriété 5 : ∀ ( p , q ) ∈ Z 2 , F p 2 − F p − q F p + q = ( − 1 ) p − q F q 2 {\displaystyle \forall (p,q)\in \mathbb {Z} ^{2},F_{p}^{2}-F_{p-q}F_{p+q}=(-1)^{p-q}F_{q}^{2}} {\displaystyle \forall (p,q)\in \mathbb {Z} ^{2},F_{p}^{2}-F_{p-q}F_{p+q}=(-1)^{p-q}F_{q}^{2}} (identité de Catalan) et F p + 1 F p − 1 − F p 2 = ( − 1 ) p {\displaystyle F_{p+1}F_{p-1}-F_{p}^{2}=(-1)^{p}} {\displaystyle F_{p+1}F_{p-1}-F_{p}^{2}=(-1)^{p}} (identité de Cassini[14],[23]).

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). L'identité de Cassini peut aussi se démontrer à l'aide de l'expression matricielle :

Démonstration

On pose M = [ 1 1 1 0 ] {\displaystyle {\mathcal {M}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}} {\displaystyle {\mathcal {M}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}} et on a donc : M p = [ 1 1 1 0 ] p = [ F p + 1 F p F p F p − 1 ] {\displaystyle {\mathcal {M}}^{p}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{p}={\begin{bmatrix}F_{p+1}&F_{p}\\F_{p}&F_{p-1}\end{bmatrix}}} {\displaystyle {\mathcal {M}}^{p}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{p}={\begin{bmatrix}F_{p+1}&F_{p}\\F_{p}&F_{p-1}\end{bmatrix}}}. Les déterminants de ces deux dernières matrices sont donc égaux, ce qui donne : F p + 1 × F p − 1 − F p 2 = ( − 1 ) p {\displaystyle F_{p+1}\times F_{p-1}-F_{p}^{2}=(-1)^{p}} {\displaystyle F_{p+1}\times F_{p-1}-F_{p}^{2}=(-1)^{p}}, qui est la formule recherchée.

Corollaire 1 : ∀ p ∈ Z , F p = F p − 1 + 5 F p − 1 2 − 4 ( − 1 ) p 2 et 5 F p 2 + 4 ( − 1 ) p ∈ N {\displaystyle \forall p\in \mathbb {Z} ,F_{p}={\frac {F_{p-1}+{\sqrt {5F_{p-1}^{2}-4(-1)^{p}}}}{2}}~{\text{et}}~{\sqrt {5F_{p}^{2}+4(-1)^{p}}}\in \mathbb {N} } {\displaystyle \forall p\in \mathbb {Z} ,F_{p}={\frac {F_{p-1}+{\sqrt {5F_{p-1}^{2}-4(-1)^{p}}}}{2}}~{\text{et}}~{\sqrt {5F_{p}^{2}+4(-1)^{p}}}\in \mathbb {N} }.

Démonstration

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

La suite de Fibonacci 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 : ∀ p ∈ Z , F p + 2 F p + 1 F p − 1 F p − 2 − F p 4 + 1 = 0 {\displaystyle \forall p\in \mathbb {Z} ,F_{p+2}F_{p+1}F_{p-1}F_{p-2}-F_{p}^{4}+1=0} {\displaystyle \forall p\in \mathbb {Z} ,F_{p+2}F_{p+1}F_{p-1}F_{p-2}-F_{p}^{4}+1=0}.

Démonstration

F p + 1 F p − 1 F p + 2 F p − 2 = ( F p 2 − ( − 1 ) p − 1 F 1 2 ) ( F p 2 − ( − 1 ) p − 2 F 2 2 ) = ( F p 2 ± 1 ) ( F p 2 ∓ 1 ) = F p 4 − 1. {\displaystyle {\begin{aligned}F_{p+1}F_{p-1}F_{p+2}F_{p-2}&=(F_{p}^{2}-(-1)^{p-1}F_{1}^{2})(F_{p}^{2}-(-1)^{p-2}F_{2}^{2})\\&=(F_{p}^{2}\pm 1)(F_{p}^{2}\mp 1)\\&=F_{p}^{4}-1.\end{aligned}}} {\displaystyle {\begin{aligned}F_{p+1}F_{p-1}F_{p+2}F_{p-2}&=(F_{p}^{2}-(-1)^{p-1}F_{1}^{2})(F_{p}^{2}-(-1)^{p-2}F_{2}^{2})\\&=(F_{p}^{2}\pm 1)(F_{p}^{2}\mp 1)\\&=F_{p}^{4}-1.\end{aligned}}}

Propriété 6 : La suite de Fibonacci est à divisibilité faible[24] : ∀ ( k , n ) ∈ Z 2 F n ∣ F n k {\displaystyle \forall (k,n)\in \mathbb {Z} ^{2}\quad F_{n}\mid F_{nk}} {\displaystyle \forall (k,n)\in \mathbb {Z} ^{2}\quad F_{n}\mid F_{nk}}[25].

Cela résulte de la propriété 2.

On peut aussi démontrer cette propriété par la proposition 4 (par récurrence sur |k|), ou par un calcul explicite du quotient (en particulier, F 2 n = F n L n {\displaystyle F_{2n}=F_{n}L_{n}} {\displaystyle F_{2n}=F_{n}L_{n}}).

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

Démonstration

Il est plus facile de démontrer la contraposée de cette proposition : si n est composé alors Fn 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, Fm est alors un diviseur propre de Fn, qui n'est donc pas premier.

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

Propriété 8 : La suite de Fibonacci est même à divisibilité forte[26] : ∀ ( a , b ) ∈ Z × Z ∗ , F a ∧ F b = F a ∧ b {\displaystyle \forall (a,b)\in \mathbb {Z} \times \mathbb {Z} ^{*},~F_{a}\land F_{b}=F_{a\land b}} {\displaystyle \forall (a,b)\in \mathbb {Z} \times \mathbb {Z} ^{*},~F_{a}\land F_{b}=F_{a\land b}}, où ∧ désigne le PGCD de nombres entiers.

En particulier pour tout entier n, Fn et F n + 1 sont premiers entre eux[27].

Propriété 9 : ∀ ( p , r ) ∈ Z 2 , F p + r − ( − 1 ) r F p − r = F r L p {\displaystyle \forall (p,r)\in \mathbb {Z} ^{2},F_{p+r}-(-1)^{r}F_{p-r}=F_{r}L_{p}} {\displaystyle \forall (p,r)\in \mathbb {Z} ^{2},F_{p+r}-(-1)^{r}F_{p-r}=F_{r}L_{p}}. En particulier :

F p + 1 + F p − 1 = L p , F p + 2 − F p − 2 = L p , F p + 3 + F p − 3 = 2 L p {\displaystyle F_{p+1}+F_{p-1}=L_{p},\quad F_{p+2}-F_{p-2}=L_{p},\quad F_{p+3}+F_{p-3}=2L_{p}} {\displaystyle F_{p+1}+F_{p-1}=L_{p},\quad F_{p+2}-F_{p-2}=L_{p},\quad F_{p+3}+F_{p-3}=2L_{p}}.

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 : ∀ n ∈ Z , φ n = F n φ + F n − 1 et φ ′ n = F n φ ′ + F n − 1 {\displaystyle \forall n\in \mathbb {Z} ,\varphi ^{n}=F_{n}\varphi +F_{n-1}~{\text{et}}~\varphi '^{n}=F_{n}\varphi '+F_{n-1}} {\displaystyle \forall n\in \mathbb {Z} ,\varphi ^{n}=F_{n}\varphi +F_{n-1}~{\text{et}}~\varphi '^{n}=F_{n}\varphi '+F_{n-1}}.

Démonstration

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

L n = F n L 1 + 2 F n − 1 et F n = F n F 1 {\displaystyle L_{n}=F_{n}L_{1}+2F_{n-1}~{\text{et}}~F_{n}=F_{n}F_{1}} {\displaystyle L_{n}=F_{n}L_{1}+2F_{n-1}~{\text{et}}~F_{n}=F_{n}F_{1}}.

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

L n = F n + 1 + F n − 1 = ( F n + F n − 1 ) + F n − 1 {\displaystyle L_{n}=F_{n+1}+F_{n-1}=(F_{n}+F_{n-1})+F_{n-1}} {\displaystyle L_{n}=F_{n+1}+F_{n-1}=(F_{n}+F_{n-1})+F_{n-1}}.

Propriété 11 : La suite de Fibonacci possède plusieurs propriétés de récurrence additive forte, notamment : ∀ n ∈ N ∗ ∑ i = 1 n F 2 i − 1 = F 2 n , 1 + ∑ i = 0 n − 1 F 2 i = F 2 n − 1 et 1 + ∑ i = 0 n − 1 F i = F n + 1 {\displaystyle \forall n\in \mathbb {N} ^{*}\quad \sum _{i=1}^{n}F_{2i-1}=F_{2n},\quad 1+\sum _{i=0}^{n-1}F_{2i}=F_{2n-1}\quad {\text{et}}\quad 1+\sum _{i=0}^{n-1}F_{i}=F_{n+1}} {\displaystyle \forall n\in \mathbb {N} ^{*}\quad \sum _{i=1}^{n}F_{2i-1}=F_{2n},\quad 1+\sum _{i=0}^{n-1}F_{2i}=F_{2n-1}\quad {\text{et}}\quad 1+\sum _{i=0}^{n-1}F_{i}=F_{n+1}}[28].

La suite ( F 2 n ) {\displaystyle (F_{2n})} {\displaystyle (F_{2n})} vérifie en outre : F 2 n = n + ∑ k = 1 n − 1 ( n − k ) F 2 k {\displaystyle F_{2n}=n+\sum _{k=1}^{n-1}(n-k)F_{2k}} {\displaystyle F_{2n}=n+\sum _{k=1}^{n-1}(n-k)F_{2k}} pour n ⩾ 2 {\displaystyle n\geqslant 2} {\displaystyle n\geqslant 2} ; voir la suite A088305 de l'OEIS.

Démonstration

Les trois premières formules peuvent se démontrer par la même méthode, dite de somme télescopique :

a) pour la première, on remplace dans la somme chaque F 2 i − 1 {\displaystyle F_{2i-1}} {\displaystyle F_{2i-1}} par son égal : ( F 2 i − F 2 i − 2 ) {\displaystyle (F_{2i}-F_{2i-2})} {\displaystyle (F_{2i}-F_{2i-2})}, et, comme F 0 = 0 {\displaystyle F_{0}=0} {\displaystyle F_{0}=0}, on trouve l'égalité recherchée.

b) pour la deuxième, on remplace dans la somme chaque F 2 i {\displaystyle F_{2i}} {\displaystyle F_{2i}} par son égal : ( F 2 i + 1 − F 2 i − 1 ) {\displaystyle (F_{2i+1}-F_{2i-1})} {\displaystyle (F_{2i+1}-F_{2i-1})}, et, comme F − 1 = 1 {\displaystyle F_{-1}=1} {\displaystyle F_{-1}=1}, on trouve l'égalité recherchée.

c) pour la troisième on remplace dans la somme chaque F i {\displaystyle F_{i}} {\displaystyle F_{i}} par son égal : ( F i + 1 − F i − 1 ) {\displaystyle (F_{i+1}-F_{i-1})} {\displaystyle (F_{i+1}-F_{i-1})}, et, comme F − 1 = 1 {\displaystyle F_{-1}=1} {\displaystyle F_{-1}=1}, on trouve l'égalité recherchée. Cette troisième formule peut aussi se démontrer par récurrence directe à partir de n = 1 {\displaystyle n=1} {\displaystyle n=1}, ou, après avoir démontré les deux formules mentionnées en a) et b), en remarquant qu'elle en découle par addition.

La quatrième formule se démontre par récurrence et en utilisant les deux premières formules.

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

Propriété 12 : ∀ n ∈ N , F n = ∑ k ∈ Z ( n − 1 − k k ) {\displaystyle \forall n\in \mathbb {N} ,~F_{n}=\sum _{k\in \mathbb {Z} }{n-1-k \choose k}} {\displaystyle \forall n\in \mathbb {N} ,~F_{n}=\sum _{k\in \mathbb {Z} }{n-1-k \choose k}} (somme finie car les coefficients binomiaux ( n − 1 − k k ) {\displaystyle {n-1-k \choose k}} {\displaystyle {n-1-k \choose k}} 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[22] :

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, F 6 ( x ) = x 5 + 4 x 3 + 3 x {\displaystyle F_{6}(x)=x^{5}+4x^{3}+3x} {\displaystyle F_{6}(x)=x^{5}+4x^{3}+3x} et F 9 ( x ) = x 8 + 7 x 6 + 15 x 4 + 10 x 2 + 1 {\displaystyle F_{9}(x)=x^{8}+7x^{6}+15x^{4}+10x^{2}+1} {\displaystyle F_{9}(x)=x^{8}+7x^{6}+15x^{4}+10x^{2}+1}.

Propriété 13 : ∀ n ∈ N , 2 n − 1 F n = ∑ 0 ≤ k ≤ n / 2 ( n 2 k + 1 ) 5 k {\displaystyle \forall n\in \mathbb {N} ,~2^{n-1}F_{n}=\sum _{0\leq k\leq n/2}{n \choose 2k+1}5^{k}} {\displaystyle \forall n\in \mathbb {N} ,~2^{n-1}F_{n}=\sum _{0\leq k\leq n/2}{n \choose 2k+1}5^{k}}.

Cette propriété découle du développement binomial de la formule de Binet[29] ; on a d'ailleurs une formule analogue pour les nombres de Lucas : ∀ n ∈ N , 2 n − 1 L n = ∑ 0 ≤ k ≤ n / 2 ( n 2 k ) 5 k {\displaystyle \forall n\in \mathbb {N} ,~2^{n-1}L_{n}=\sum _{0\leq k\leq n/2}{n \choose 2k}5^{k}} {\displaystyle \forall n\in \mathbb {N} ,~2^{n-1}L_{n}=\sum _{0\leq k\leq n/2}{n \choose 2k}5^{k}}.

Propriété 14 : La suite ( u n ) n ∈ N ∗ {\displaystyle (u_{n})_{n\in \mathbb {N} ^{*}}} {\displaystyle (u_{n})_{n\in \mathbb {N} ^{*}}} définie par u n = F n + 1 / F n {\displaystyle u_{n}=F_{n+1}/F_{n}} {\displaystyle u_{n}=F_{n+1}/F_{n}} vérifie u n + 1 = 1 + 1 / u n et u n 2 − u n − 1 = ( − 1 ) n / F n 2 {\displaystyle u_{n+1}=1+1/u_{n}{\text{ et }}u_{n}^{2}-u_{n}-1=(-1)^{n}/F_{n}^{2}} {\displaystyle u_{n+1}=1+1/u_{n}{\text{ et }}u_{n}^{2}-u_{n}-1=(-1)^{n}/F_{n}^{2}}.

Propriété 15 : La factorisation des polynômes de Fibonacci permet d'exprimer les F n {\displaystyle {F}_{n}} {\displaystyle {F}_{n}} (pour n ≥ 1) sous forme de produits trigonométriques[30] : F n = ∏ 1 ≤ k ≤ ( n − 1 ) / 2 3 + 2 cos ⁡ ( 2 k π n ) {\displaystyle {F}_{n}=\prod _{1\leq k\leq (n-1)/2}3+2\cos \left({\frac {2k\pi }{n}}\right)} {\displaystyle {F}_{n}=\prod _{1\leq k\leq (n-1)/2}3+2\cos \left({\frac {2k\pi }{n}}\right)}.

Une première approche de la question de la divisibilité de Fn par un entier a {\displaystyle a} {\displaystyle a} consiste à étudier la suite des restes de Fn modulo a {\displaystyle a} {\displaystyle a} : cette suite ( r n ) {\displaystyle (r_{n})} {\displaystyle (r_{n})} vérifie (dans Z / a Z {\displaystyle \mathbb {Z} /a\mathbb {Z} } {\displaystyle \mathbb {Z} /a\mathbb {Z} }) la même récurrence ( r n + 2 = r n + 1 + r n ) {\displaystyle (r_{n+2}=r_{n+1}+r_{n})} {\displaystyle (r_{n+2}=r_{n+1}+r_{n})} et est donc périodique de période au plus a 2 {\displaystyle a^{2}} {\displaystyle a^{2}} (les longueurs des périodes en fonction de a {\displaystyle a} {\displaystyle a} forment la suite des périodes de Pisano, suite A001175 de l'OEIS) ; on en déduit que pour tout a {\displaystyle a} {\displaystyle a}, il existe n inférieur ou égal à a 2 {\displaystyle a^{2}} {\displaystyle a^{2}} tel que Fn (et donc Fkn) soit divisible par a {\displaystyle a} {\displaystyle a}. Plus précisément, l'étude de cette récurrence dans le corps Z / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } {\displaystyle \mathbb {Z} /p\mathbb {Z} } (où p {\displaystyle p} {\displaystyle 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 {\displaystyle p} {\displaystyle p} ; voir la loi de réciprocité quadratique) que F 5 n {\displaystyle F_{5n}} {\displaystyle F_{5n}} est divisible par 5, et que si p {\displaystyle p} {\displaystyle p} est premier autre que 5, F ( p − 1 ) n {\displaystyle F_{(p-1)n}} {\displaystyle F_{(p-1)n}} est divisible par p {\displaystyle p} {\displaystyle p} si p {\displaystyle p} {\displaystyle p} est de la forme 5 m + 1 {\displaystyle 5m+1} {\displaystyle 5m+1} ou 5 m + 4 {\displaystyle 5m+4} {\displaystyle 5m+4}, et F ( p + 1 ) n {\displaystyle F_{(p+1)n}} {\displaystyle F_{(p+1)n}} est divisible par p {\displaystyle p} {\displaystyle p} sinon. Des résultats plus précis peuvent d'ailleurs être obtenus ; ainsi, dans le premier cas, F ( p − 1 ) / 2 {\displaystyle F_{(p-1)/2}} {\displaystyle F_{(p-1)/2}} est divisible par p {\displaystyle p} {\displaystyle p} si ( p − 1 ) / 2 {\displaystyle (p-1)/2} {\displaystyle (p-1)/2} est pair[31]. Enfin, si p > 2 {\displaystyle p>2} {\displaystyle p>2} est premier et divise Fn, p k {\displaystyle p^{k}} {\displaystyle p^{k}} divise F p k − 1 n {\displaystyle F_{p^{k-1}n}} {\displaystyle F_{p^{k-1}n}}, et 2 k + 1 {\displaystyle 2^{k+1}} {\displaystyle 2^{k+1}} divise F 3 × 2 k − 1 {\displaystyle F_{3\times 2^{k-1}}} {\displaystyle F_{3\times 2^{k-1}}} (si k > 1 {\displaystyle k>1} {\displaystyle k>1}) ; ces derniers résultats sont des conséquences du lemme de Hensel[32],[33] ; les mêmes méthodes permettent d'obtenir des résultats analogues pour les nombres de Lucas[31],[34].

Un nombre premier de Fibonacci est un nombre de Fibonacci qui est également premier.

Les sept plus petits nombres premiers de Fibonacci F n {\displaystyle F_{n}} {\displaystyle F_{n}} sont[35] 2, 3, 5, 13, 89, 233 et 1 597, et les indices n correspondants sont 3, 4, 5, 7, 11, 13 et 17 (sauf pour F 4 {\displaystyle F_{4}} {\displaystyle F_{4}}, ces indices sont nécessairement premiers[36]) .

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

Tout entier positif se décompose de manière unique comme somme de nombres de Fibonacci distincts, d'indice supérieur ou égal à deux, et non consécutifs.

Exemple

25 = 21 + 3 + 1 = F 8 + F 4 + F 2 {\displaystyle 25=21+3+1=F_{8}+F_{4}+F_{2}} {\displaystyle 25=21+3+1=F_{8}+F_{4}+F_{2}}.

Animation GIF représentant Fibonacci

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_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_-ième génération sont constitués :pour les femelles, de Fn mâles et F n + 1 femelles,pour les mâles, de F n – 1 mâles et Fn 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 ce seraient en fait les apiculteurs de Béjaïa et la connaissance de la reproduction des abeilles qui, plutôt que la reproduction des lapins, auraient inspiré la découverte de Fibonacci[39].

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

Il existe plusieurs façons de généraliser la suite de Fibonacci : étendre aux indices négatifs, 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. Si on modifie tout à la fois (initialisation, récurrence, ordre) on arrive à l'ensemble général des suites à récurrence linéaire. Un bon nombre de propriétés se généralisent au cas où le polynôme minimal de la suite récurrente linéaire définit un nombre de Pisot. Ces propriétés ont été étudiées en lien avec la théorie des automates finis (sur les mots finis et les mots infinis) dans la thèse d'État de Christiane Frougny sur la représentation des entiers et des réels en base Pisot, sur une suggestion de Marcel-Paul Schützenberger.

La suite est étendue aux indices négatifs et Knuth parle de nombres de negafibonacci[40]. La formule de récurrence les définit aussi de proche en proche : F n = F n + 2 − F n + 1 {\displaystyle F_{n}=F_{n+2}-F_{n+1}} {\displaystyle F_{n}=F_{n+2}-F_{n+1}}

Ainsi, autour de 0, la suite est :

_F_–6 _F_–5 _F_–4 _F_–3 _F_–2 _F_–1 _F_0 _F_1 _F_2 _F_3 _F_4 _F_5 _F_6
−8 5 −3 2 −1 1 0 1 1 2 3 5 8

On remarque, sur ces premières valeurs, que

ou plus synthétiquement :

F − n = ( − 1 ) n + 1 F n {\displaystyle F_{-n}=(-1)^{n+1}F_{n}} {\displaystyle F_{-n}=(-1)^{n+1}F_{n}}.

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

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[réf. nécessaire]. 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 où φ est le nombre d'or et φ ′ = − 1 / φ {\displaystyle \varphi '=-1/\varphi } {\displaystyle \varphi '=-1/\varphi }. Elle est donc équivalente à αφn, sauf si α = 0 (ce qui ne se produit que si u 1 = φ ′ u 0 {\displaystyle u_{1}=\varphi 'u_{0}} {\displaystyle u_{1}=\varphi 'u_{0}}), si bien que (comme la suite des quotients de la suite de Fibonacci) la suite u n + 1 u n {\displaystyle {\frac {u_{n+1}}{u_{n}}}} {\displaystyle {\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 : L 0 = 2 {\displaystyle L_{0}=2} {\displaystyle L_{0}=2} et L 1 = 1 {\displaystyle L_{1}=1} {\displaystyle L_{1}=1}. Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29,… On trouve parfois une initialisation L 0 = 1 {\displaystyle L_{0}=1} {\displaystyle L_{0}=1} et L 1 = 3 {\displaystyle L_{1}=3} {\displaystyle 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 par la relation suivante : L n = F n + 1 + F n − 1 {\displaystyle L_{n}=F_{n+1}+F_{n-1}} {\displaystyle L_{n}=F_{n+1}+F_{n-1}} pour tout entier n > 0 (voir Propriétés, Propriété 9).

Ce sont les suites où la relation de récurrence a changé et est devenue[réf. nécessaire]

X n + 2 = P X n − Q X n + 1 {\displaystyle X_{n+2}=PX_{n}-QX_{n+1}} {\displaystyle X_{n+2}=PX_{n}-QX_{n+1}}.

Elles sont de deux types, notés X = U et X = V, selon que l'initialisation est _U_0 = 0 et _U_1 = 1 ou qu'elle est _V_0 = 2 et _V_1 = 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.

Ce sont des suites dont la relation de récurrence est d'ordre k {\displaystyle k} {\displaystyle k}[41]. Un terme est la somme des k {\displaystyle k} {\displaystyle k} termes qui le précèdent :

u n + k = u n + u n + 1 + u n + 2 + ⋯ + u n + k − 1 {\displaystyle u_{n+k}\,=\,u_{n}+u_{n+1}+u_{n+2}+\dots +u_{n+k-1}} {\displaystyle 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.

Coeur d'une fleur jaune avec des petites fleurs disposées en spirales concentriques

Centre d'une fleur de tournesol. Le réceptacle forme des spirales régulières, dextres et sénestres, dans lesquelles on peut retrouver la suite de Fibonacci.

La suite de Fibonacci apparaît sous de nombreuses formes biologiques[42], comme la ramification des arbres, la disposition des feuilles sur une tige, les fruits de l'ananas[43], la floraison de l'artichaut, le déroulement des feuilles de fougères, la disposition d'une pomme de pin[44], la coquille de l’escargot et la disposition des nuages lors des ouragans. Quant aux marguerites, elles ont le plus souvent un nombre de pétales issu de la suite de Fibonacci.

Chez les Astéracées, dans les inflorescences en capitule, la disposition des fleurons sur le réceptacle forme des spirales régulières, dextres et sénestres, qui suivent les règles de la phyllotaxie dans lesquelles on peut retrouver la suite de Fibonacci[43].

Les abeilles domestiques ont une reproduction haplodiploïde : un œuf non fécondé donnera un mâle et un œuf fécondé donnera une ouvrière ou une reine. Ainsi, un mâle aura une mère, quand les ouvrières et reine auront une mère et un père. Par conséquent, le pedigree d'un mâle est constitué d'un parent, de deux grands-parents, de trois arrière-grands-parents, de cinq arrière-arrière-grands-parents, etc. ; il s'agit d'une suite de Fibonacci[45].

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

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.

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.

En méthodologie scrum, la suite de Fibonacci est utilisée pour chiffrer les développements lors du planning poker.[réf. nécessaire]

La suite de Fibonacci peut servir à effectuer des conversions de milles américains en kilomètres[réf. nécessaire]. En effet, 1 mi = 1,609 km, or le nombre d'or φ ≈ 1,6 et F n + 1 ≈ φFn, donc on a la relation approchée Fn mi ≈ F n + 1 km.

Par exemple, 3 mi ≈ 5 km (en réalité 4,83 km), 5 mi ≈ 8 km (en réalité 8,05 km), 8 mi ≈ 13 km (en réalité 12,87 km).

Pour convertir des distances ne correspondant pas aux nombres de Fibonacci, on peut additionner plusieurs relations ou multiplier par une constante adéquate.

Par exemple, 3 mi ≈ 5 km donc, en multipliant par 2, 6 mi ≈ 10 km. De même, 5 mi ≈ 8 km donc, en multipliant par 10, 50 mi ≈ 80 km.

  1. ↑ a et b Edouard Lucas, Théorie des nombres, 1891 (lire en ligne), p. 3.
  2. ↑ a et b (en) Miklos Bona, Walk Through Combinatorics, A: An Introduction To Enumeration And Graph Theory, Wspc, 9 mai 2011 (ISBN 978-981-4460-00-2).
  3. ↑ (en) Susantha Goonatilake, Toward a Global Science: Mining Civilizational Knowledge, Indiana University Press, 1998, p. 126.
  4. ↑ (en) Jayant Shah, A history of Pingala's combinatorics, Northeastern University, Boston, p. 38.
  5. ↑ Pour la version latine, voir ce document p. 283-284 et pour la traduction, ce recueil d'extraits par Jérôme Gavin et Alain Schärlig, p. 11.
  6. ↑ J. Binet, « Mémoire sur l'intégration des équations linéaires aux différences finies, d'un ordre quelconque, à coefficients variables », Comptes rendus des séances de l'Académie des sciences, vol. 17,‎ 1843, p. 559-567 (lire en ligne).
  7. ↑ E326, Opera Omnia, série 1, vol. 15, p. 50-69.
  8. ↑ a et b Cet exemple de la théorie développée dans (la) Abraham de Moivre, Miscellanea analytica de seriebus et quadraturis, 1730 (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.
  9. ↑ (la) J. Kepler, « Strena seu de nive sexangula », 1611.
  10. ↑ Richard André-Jeannin, « Irrationalité de la somme des inverses de certaines suites récurrentes », C. R. Acad. Sci. Paris, i Math., vol. 308,‎ 1989, p. 539-541 (lire en ligne).
  11. ↑ Voir (en) Eric W. Weisstein, « Reciprocal Fibonacci Constant », sur MathWorld, ainsi que la suite A079586 de l'OEIS (développement décimal) et OEIS A079587 (fraction continue).
  12. ↑ (en) Roger Cuculière, « Problem E2922 », Amer. Math. Monthly, vol. 89, no 1,‎ 1982, p. 63 (JSTOR 2321000) et (en) « Solution to Problem E2922 », ibid., vol. 91, no 7,‎ 1984, p. 438 (JSTOR 2323005).
  13. ↑ a et b (en) Catalin Badea, « A theorem on irrationality of infinite series and applications », Acta Arithmetica, vol. 63,‎ 1993, p. 313-323 (lire en ligne).
  14. ↑ a et b (en) M. Werman et D. Zeilberger, « A bijective proof of Cassini's Fibonacci identity », Discrete Math., vol. 58, no 1,‎ 1986, p. 109 (DOI 10.1016/0012-365X(86)90194-9, MR 0820846).
  15. ↑ a b et c (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill, 2008.
  16. ↑ a et b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, 1176 p., Section 31.2.
  17. ↑ Cf. discussion à la fin de l'exercice 0.4 de Dasgupta, Papadimitriou et Vazirani 2008.
  18. ↑ (en) « https://www.geeksforgeeks.org/tail-recursion-fibonacci/ », sur geeksforgeeks.org.
  19. ↑ Voir par exemple l'évaluation similaire de la factorielle.
  20. ↑ (en) Antony J. T. Davie, Introduction to Functional Programming Systems Using Haskell, Cambridge University, coll. « Cambridge Computer Science Texts », 1992 (lire en ligne), chap. 7 (« Lazy evaluation »), Section 7.3 : Streams.
  21. ↑ « The Fibonacci Quarterly », sur www.fq.math.ca (consulté le 7 février 2023)
  22. ↑ 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, 2003 (lire en ligne), p. 4.
  23. ↑ Pour une preuve combinatoire, voir Benjamin et Quinn 2003, p. 8.
  24. ↑ Plus généralement, toute suite de Lucas U(P, Q) est à divisibilité faible.
  25. ↑ Pour une preuve combinatoire, voir Benjamin et Quinn 2003, p. 11.
  26. ↑ Plus généralement, 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.
  27. ↑ Car deux entiers consécutifs sont toujours premiers entre eux.
  28. ↑ 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é.
  29. ↑ Voir (en) Steven Vajda, Fibonacci and Lucas Numbers, and the Golden Section, Dover, 2008 (1re éd. 1989) (lire en ligne), p. 68-69.
  30. ↑ (en) Bala Sury, « Trigonometric expressions for Fibonacci and Lucas Numbers », Acta Math. Univ. Comenianae, vol. 79, no 2,‎ 2010, p. 199-208 (lire en ligne).
  31. ↑ a et b (en) T. Lengyel, The order of the Fibonacci and the Lucas numbers, Fibonacci Quarterly, 1995.
  32. ↑ (en) Paulo Ribenboim, The New Book of Prime Number Records, New York, Springer, 1996 (ISBN 0-387-94457-5), p. 64.
  33. ↑ (en) Franz Lemmermeyer, Reciprocity Laws, New York, Springer, 2000 (ISBN 3-540-66957-4), ex. 2.25-2.28, p. 73-74.
  34. ↑ (en) Thomas Jeffery et Rajesh Pereira, Divisibility Properties of the Fibonacci, Lucas, and Related Sequences, 2013.
  35. ↑ Voir les suites OEIS A005478 et OEIS A001605 de l'OEIS pour plus de termes de cette sous-suite et de ses indices.
  36. ↑ Voir propriété 7.
  37. ↑ (en) Victor H. Moll, Numbers and Functions : From a Classical-experimental Mathematician's Point of View, AMS, 2012 (lire en ligne), p. 113, reproduit dans « Infinitude of Primes - via Fibonacci Numbers », sur Cut The Knot.
  38. ↑ (en) D. Avis et V. Chvátal, « Notes on Bland’s pivoting rule », dans Polyhedral Combinatorics: Dedicated to the memory of D.R. Fulkerson, Springer, coll. « Mathematical Programming Studies », 1978 (ISBN 978-3-642-00790-3, DOI 10.1007/bfb0121192, lire en ligne), p. 24–34
  39. ↑ (en) T.C. Scott et P. Marketos, « On the Origin of the Fibonacci Sequence », MacTutor History of Mathematics archive, University of St Andrews,‎ mars 2014 (lire en ligne).
  40. ↑ (en) Donald Knuth (2008-12-11), « Negafibonacci Numbers and the Hyperbolic Plane », Annual meeting, The Fairmont Hotel, San Jose, CA: The Mathematical Association of America.
  41. ↑ Martin Gardner, The Scientific American Book of Mathematical Puzzles and Diversions, Vol. II, Simon and Schuster, 1961, p. 101
  42. ↑ (en) Mario Livio, The Golden Ratio : The Story of PHI, the World's Most Astonishing Number Paperback, Broadway Books; Reprint edition, 23 septembre 2003, 294 p. (ISBN 978-0-7679-0816-0).
  43. ↑ a et b (en) Yafei Zhao et al., « Evolutionary Co-Option of Floral Meristem Identity Genes for Patterning of the Flower-Like Asteraceae Inflorescence », Plant Physiology, vol. 172, no 1,‎ septembre 2016, p. 284-296 (DOI 10.1104/pp.16.00779).
  44. ↑ (en) Brousseau, A, « Fibonacci Statistics in Conifers », Fibonacci Quarterly, vol. 7,‎ 1969, p. 525–532 (lire en ligne).
  45. ↑ (en) S.L. Basin, « The Fibonacci sequence as it appears in nature », The Fibonacci Quarterly, vol. 1, no 1,‎ 1963, p. 53–56 (lire en ligne).
  46. ↑ C. Pasquet, « Du nombre d'or à la Section d'or », Dossier de l'Art, no 257,‎ mars 2018, p. 70-71.
  47. ↑ 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
  48. ↑ Détails et explications dans l'article «Nymphomaniac», un film fourré aux mathématiques de Thomas Messias sur Slate
  49. ↑ « X + Y Review [TIFF 2014] » (consulté le 13 juin 2015)
  50. ↑ (en) Christopher diCarlo, Interview with Maynard James Keenan [lire en ligne].
  51. ↑ Voir la liste des chansons de l'album sur la boutique en ligne de l'artiste.
  52. ↑ (en) Ernő Lendvai, Béla Bartók: An Analysis of His Music — With an Introduction by Alan Bush, Kahn & Averill, 1971 (ISBN 978-0-900707-81-0).
  53. ↑ Voir par exemple (en) Gareth E. Roberts, « The Bartók Controversy », 2015.
  54. ↑ Sven Sterken, « Iannis Xenakis, Ingénieur et Architecte. p122 » [PDF], 2004
  55. ↑ http://s1.lprs1.fr/images/2016/11/15/6332622_the-cure007.jpg
  56. ↑ « Mes échecs et mes réussites forment la suite de Fibonacci », sur Genius (consulté le 8 août 2025)