Suite de Fibonacci
13991
31643312
2008-07-17T06:19:18Z
Theon
10024
/* Suites de Fibonacci généralisées */ suppr lien non encyclopédique
La '''suite de Fibonacci''' est l'une des [[Suite (mathématiques)|suites]] [[mathématiques]] les plus connues. Elle doit son nom au mathématicien [[italie]]n [[Leonardo Pisano]], plus connu sous le pseudonyme de ''Fibonacci'' ([[1175]] - [[1250]]). Dans un problème récréatif posé dans un de ses ouvrages, le ''Liber Abaci'', Fibonacci décrit la croissance d'une population de lapins :
:« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? »
Ce problème est à l'origine de la suite dont le <math>n\,</math>-ème terme correspond au nombre de paires de lapins au <math>n\,</math>-ème mois. Dans cette population (idéale), on suppose que :
* le premier mois, il y a juste ''une'' paire de lapereaux ;
* les lapereaux ne sont pubères qu'à partir du deuxième mois ;
* chaque 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).
== Présentation mathématique ==
===Formule de réccurence===
Notons <math>\mathcal{F}_n</math> le nombre de couples de lapins au mois <math>n\,</math>. Jusqu’à la fin du deuxième mois, la population se limite à un couple (ce qu'on note : <math>\mathcal{F}_1=\mathcal{F}_2=1</math>). 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 <math>\mathcal{F}_3=2</math>. Plaçons-nous maintenant au mois <math>n\,</math> et cherchons à exprimer ce qu'il en sera deux mois plus tard <math>(n + 2)\,</math> : <math>\mathcal{F}_{n+2}</math> désigne la somme des couples de lapins au mois <math>n + 2\,</math> et des couples nouvellement engendrés. Or, n'engendrent au mois <math>(n + 2)\,</math> que les couples pubères, c'est à dire ceux qui existent deux mois auparavant. On a donc :
:<math>\mathcal{F}_{n+2}=\mathcal{F}_{n+1}+\mathcal{F}_n</math>.
Nous obtenons ainsi la ''[[Relation de récurrence|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, <math>\mathcal{F}_1</math> et <math>\mathcal{F}_2</math>, qui sont connus.
===Nombres de Fibonacci===
Les premières valeurs des nombres de Fibonacci, dans l'ordre croissant en commençant avec <math>n=0</math>, sont donc données par :
:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
Les termes de cette suite sont appelés ''nombres de Fibonacci''.
{| class="wikitable" style="text-align:center;"
|-
| <math>\mathcal{F}_0</math>
| <math>\mathcal{F}_1</math>
| <math>\mathcal{F}_2</math>
| <math>\mathcal{F}_3</math>
| <math>\mathcal{F}_4</math>
| <math>\mathcal{F}_5</math>
| <math>\mathcal{F}_6</math>
| <math>\mathcal{F}_7</math>
| <math>\mathcal{F}_8</math>
| <math>\mathcal{F}_9</math>
| <math>\mathcal{F}_{10}</math>
| <math>\mathcal{F}_{11}</math>
| <math>\mathcal{F}_{12}</math>
| <math>\mathcal{F}_{13}</math>
| <math>\mathcal{F}_{14}</math>
| <math>\mathcal{F}_{15}</math>
| <math>\mathcal{F}_{16}</math>
| <math>\mathcal{F}_{17}</math>
| <math>\mathcal{F}_{18}</math>
| <math>\mathcal{F}_{19}</math>
| <math>\mathcal{F}_{20}</math>
| <math>\mathcal{F}_{21}</math>
|-
| 0
| 1
| 1
| 2
| 3
| 5
| 8
| 13
| 21
| 34
| 55
| 89
| 144
| 233
| 377
| 610
| 987
| 1597
| 2584
| 4181
| 6765
| 10946
| …
|}
== 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 <math>n\,</math> donnée ne présuppose la connaissance d’aucun nombre de couples pour une quelconque autre valeur de <math>n\,</math>, ce que ne permet pas la formule de récurrence. Comme la suite de Fibonacci est [[Suite récurrente linéaire|récurrente d’ordre deux]], on peut écrire son [[équation caractéristique]]. On obtient une [[équation du second degré]] : <math>x^2 = x + 1\,</math>
:<math>x^2 - x - 1 =0\,</math>.
Le calcul du [[discriminant]] de cette équation donne les deux solutions du [[polynôme]] :
:<math>x_1 = \varphi = \frac{1+\sqrt{5}}{2}\,</math> et <math>x_2 = \varphi' = \frac{1-\sqrt{5}}{2}\,</math>. (<math>\varphi\,</math> est le [[nombre d'or]], et <math>\varphi'\,</math> l'opposé de la section dorée).
Les suites <math>(\varphi^n)</math> et <math>(\varphi'^n)</math> engendrent alors l'[[espace vectoriel]] des suites vérifiant <math>u_{n+2}=u_{n+1}+u_n</math>. Il en résulte que :
:<math>\mathcal{F}_n = \alpha{}\varphi^n+\beta\varphi'^n</math> (<math>\alpha\,</math> et <math>\beta\,</math> sont des constantes à déterminer à partir de <math>\mathcal{F}_1</math> et <math>\mathcal{F}_2</math>.)
Les conditions initiales <math>\mathcal{F}_1=\mathcal{F}_2=1</math> conduisent au système suivant :
:<math>\left\{\begin{matrix} \alpha + \beta = 0 \\ \alpha - \beta = \frac{2}{\sqrt{5}}\end{matrix}\right.</math>
Ce qui donne le résultat suivant :
:<math>\alpha = \frac{1}{\sqrt{5}}</math> et <math>\beta = -\frac{1}{\sqrt{5}}</math>.
Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de ''[[Jacques Philippe Marie Binet#Formule de Binet|formule de Binet]]'' :
:<math>\mathcal{F}_n = \frac{1}{\sqrt{5}}(\varphi^n-\varphi'^n)</math>.
Il existe d'autres démonstrations. Une démonstration utilisant la [[transformée en Z]] est donnée dans l'article du même nom (éponyme). Le résultat s'obtient également en utilisant la technique des [[Fonction génératrice|fonctions génératrices]].
Remarquons qu'une fois découverte cette formule se démontre aussi par récurrence.
== 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 <math>n<0</math> :
* si n est pair alors <math>\mathcal{F}_{-n} = -\mathcal{F}_n</math>
* si n est impair alors <math>\mathcal{F}_{-n} = \mathcal{F}_n</math>
== Limite des quotients ==
Comme l'a remarqué [[Johannes Kepler]], le taux de croissance des nombres de Fibonacci, c'est-à-dire <math>\frac{\mathcal{F}_{n+1}}{\mathcal{F}_n}</math>, converge vers le [[nombre d'or]], noté <math>\varphi\,</math>. Mathématiquement, le résultat s'obtient ainsi :
:{| border=0
|<math>\lim_{n \to \infty}\frac{\mathcal{F}_{n+1}}{\mathcal{F}_n}</math>
|<math>=\lim_{n \to \infty}\frac{\varphi^{n+1}-\varphi'^{n+1}}{\varphi^n-\varphi'^n}</math>
|-
|
|<math>=\lim_{n \to \infty}\varphi\frac{1-(\varphi'/\varphi)^{n+1}}{1-(\varphi'/\varphi)^n}</math>
|(en simplifiant par <math>\varphi^n\,</math>)
|-
|
|<math>=\varphi\,</math>
|(comme <math>\varphi'/\varphi \in ]-1;1[</math>, <math>\lim_{n \to \infty}(\varphi'/\varphi)^n = 0</math>)
|}
Plus précisément, quand <math>n\,</math> tend vers l'infini, le second terme tend vers zéro car <math>\varphi' \in ]-1 ; 1[</math>, ainsi les nombres de Fibonacci se comportent comme une exponentielle multipliée par le facteur <math>\frac{1}{\sqrt{5}}</math>, soit <math>\frac{\varphi^n}{\sqrt{5}}</math>.
En fait, dès le rang <math>n=1\,</math>, le deuxième terme <math>{\varphi'^n \over \sqrt{5}}</math> est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir du premier terme, en arrondissant à l'entier le plus proche.
== Bases et espaces vectoriels ==
* La dénomination de « suite de Fibonacci généralisée » est attribuée plus généralement à toute [[fonction (mathématiques)|fonction]] <math>\mathcal{G}</math> définie sur <math>\mathbb N</math> vérifiant pour tout entier naturel <math>n\,</math>, <math>\mathcal{G}_{n+2}=\mathcal{G}_{n+1}+\mathcal{G}_n</math>. Ces fonctions sont précisément celles pour lesquelles il existe des nombres ''a'' et ''b'', tels que pour tout entier naturel ''n'', <math>\mathcal{G}_n = a{}\cdot{}\mathcal{F}_n+b{}\cdot{}\mathcal{F}_{n+1}</math>. Ainsi, l'ensemble des suites de Fibonacci est un [[espace vectoriel]], et les suites <math>(\mathcal{F}_n)</math> et <math>(\mathcal{F}_{n+1})</math> en forment une [[base]].
* Le [[nombre d'or]] est la racine positive de l'équation du second degré <math>x^2 - x - 1 = 0\,</math>, ainsi <math>\varphi^2 = \varphi + 1\,</math>. Si on multiplie les deux côtés par <math>\varphi^n\,</math>, on obtient <math>\varphi^{n+2} = \varphi^{n+1} + \varphi^n\,</math>, donc la fonction <math>n\mapsto \varphi^n</math> est une suite de Fibonacci. La racine négative de l'équation du second degré, <math>\varphi'=1-\varphi\,</math>, possède les mêmes propriétés, et les deux fonctions linéairement indépendantes <math>n\mapsto \varphi^n</math> et <math>n\mapsto \left(1-\varphi\right)^n</math>, forment une autre base de l'espace vectoriel.
== Algorithmes de calcul des nombres de Fibonacci ==
=== 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’à <math>\mathcal{F}_{71} = 308061521170130</math>, sur ordinateur ou sur calculatrice.
Notons qu’au-delà de <math>\mathcal{F}_{79}</math>, 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 <math>\mathcal{F}_{50}</math>.
Le nombre d’or vaut : <math>\frac{1+\sqrt{5}}{2}\ = 1,61803398874989\dots</math>
Appliquons la formule de Binet, (en ne retenant que le terme significatif) soit :
<math>\mathcal{F}_{50} \approx \frac{(1,61803398874989)^{50}}{\sqrt{5}} \approx 12586269024,9981</math>
Arrondissons à l’entier le plus proche soit :
<math>\mathcal{F}_{50} = 12586269025</math>
=== Algorithme récursif naïf ===
L'implémentation [[Récursivité|récursive]] naïve qui suit la définition de la suite de Fibonacci est immédiate. En [[langage Python|Python]], cela donne :
<source lang="Python">
def fibo(n):
if (n <= 1): # cas de base
return n
else: # récurrence
return fibo(n - 1) + fibo(n - 2)
</source>
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]].
=== 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 (langage)|Python]], un tel algorithme itératif donne :
<source lang="Python">
def fibo(n):
f_n_1 = 1
f_n = 0
for i in range(n): # n fois
f_n_1, f_n = (f_n, f_n + f_n_1)
return f_n
</source>
De manière équivalente, on peut écrire une fonction [[récursion terminale|récursive terminale]] :
<source lang="Python">
def fibo(n, f_n_1 = 1, f_n = 0):
if (n == 0): # cas de base
return f_n
else: # récurrence
return fibo(n - 1, f_n, f_n + f_n_1)
</source>
Le temps de calcul est à chaque fois proportionnel à ''n'' et l'espace mémoire occupé constant.
=== Algorithme logarithmique ===
En utilisant la relation matricielle suivante, que l'on montre par récurrence :
:<math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =
\begin{bmatrix} \mathcal F_{n+1} & \mathcal F_n \\
\mathcal F_n & \mathcal F_{n-1} \end{bmatrix}
</math>
ou avec les [[#Propriétés de la suite de Fibonacci]], on obtient :
:<math>\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</math>
:<math>\mathcal F_{2k+1} = \mathcal F_{k+1}^2 + \mathcal F_k^2</math>
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 (langage)|Python]] :
<source lang="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]
</source>
En retravaillant les relations de récurrence pour le cas pair on obtient :
:<math>\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</math>
Et donc :
:<math>\forall n \in \mathbb{Z}, \mathcal F_{n} = \mathcal F_{\lfloor\frac{n}{2}\rfloor+1}^2 - (-1)^n \mathcal F_{\lfloor\frac{n-1}{2}\rfloor}^2
</math>
=== Curiosité algorithmique ===
Une façon particulièrement curieuse d'obtenir la suite de Fibonacci est la suivante. On considère 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]. Si on part d'un entier de la forme <math>2^{F(n-1)}3^{F(n)}</math> et si on le multiplie itérativement par la première fraction qui redonne un résultat entier, alors le premier nombre entier de la suite ainsi obtenue qui n'aura que 2 et 3 comme facteurs premiers sera le nombre <math>2^{F(n)}3^{F(n+1)}</math>.
Par exemple, si on part de <math>18 = 2^1 3^2</math>, on obtient successivement :
:18 <math>\times</math> 35/2 = 315
:315 <math>\times</math> 13/7 = 585
:585 <math>\times</math> 17/39 = 255
:255 <math>\times</math> 130/17 = 1950
:1950 <math>\times</math> 17/39 = 850
:850 <math>\times</math> 130/17 = 6500
:6500 <math>\times</math> 19/13 = 9500
:9500 <math>\times</math> 23/95 = 2300
:2300 <math>\times</math> 57/23 = 5700
:5700 <math>\times</math> 23/95 = 1380
:1380 <math>\times</math> 57/23 = 3420
:3420 <math>\times</math> 23/95 = 828
:828 <math>\times</math> 57/23 = 2052
:2052 <math>\times</math> 1/19 = 108 = <math>2^2 3^3</math>
Si on itère le procédé, on verra défiler les nombres de Fibonacci dans les exposants des puissances de 2 et 3 décomposant les nombres ainsi obtenus.
== Propriétés de la suite de Fibonacci ==
La suite de Fibonacci, ainsi définie, présente de remarquables propriétés. En voici quelques-unes, données avec leur démonstration (celles-ci font en général appel au [[raisonnement par récurrence]]). Nous donnons également quelques propriétés liant la suite de Fibonacci et les nombres de Lucas.
'''Propriété 1''' : <math>\forall (p,q)\in\mathbb{N}^*\times\mathbb{N}, \mathcal{F}_{p+q} = \mathcal{F}_{p-1}\mathcal{F}_q + \mathcal{F}_p\mathcal{F}_{q+1}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence d'ordre 2 sur <math>q\,</math>
* Initialisation
:(rang <math>q=0\,</math>) : <math>\mathcal{F}_{p-1}\mathcal{F}_0 + \mathcal{F}_p\mathcal{F}_1 = \mathcal{F}_p</math>
:(rang <math>q=1\,</math>) : <math>\mathcal{F}_{p-1}\mathcal{F}_1 + \mathcal{F}_p\mathcal{F}_2 = \mathcal{F}_{p+1}</math> (Définition de la suite de Fibonacci)
* Hypothèses de récurrence :
: (au rang <math>q\,</math>), <math>\mathcal{F}_{p+q} = \mathcal{F}_{p-1}\mathcal{F}_q + \mathcal{F}_p\mathcal{F}_{q+1}</math>
: (au rang <math>q+1\,</math>), <math>\mathcal{F}_{p+q+1} = \mathcal{F}_{p-1}\mathcal{F}_{q+1} + \mathcal{F}_p\mathcal{F}_{q+2}</math>
* Hérédité (rang <math>q+2\,</math>) :
: <math>\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p+q+1} + \mathcal{F}_{p+q}</math> (Définition de la suite de Fibonacci)
:<math>\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p-1}\mathcal{F}_{q+1} + \mathcal{F}_p\mathcal{F}_{q+2} + \mathcal{F}_{p-1}\mathcal{F}_{q} + \mathcal{F}_p\mathcal{F}_{q+1} </math> (Hypothèses de récurrence)
:<math>\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p-1}(\mathcal{F}_{q}+\mathcal{F}_{q+1})+\mathcal{F}_p(\mathcal{F}_{q+1}+\mathcal{F}_{q+2})</math> (Factorisation)
:<math>\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p-1}\mathcal{F}_{q+2} + \mathcal{F}_p\mathcal{F}_{(q+2)+1}</math> (Définition)
}}
'''Propriété 2''' : <math>\forall (k,n)\in\mathbb{N}\times\mathbb{N}^*, \mathcal{F}_n{}|{}\mathcal{F}_{n\cdot k}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence sur <math>k\,</math>
* Initialisation (rang <math>k=0\,</math>) : <math>\mathcal{F}_n{}|{}0</math> (vrai car tout entier naturel divise 0)
* Hypothèse de récurrence : au rang <math>k\,</math>, <math>\mathcal{F}_n{}|{}\mathcal{F}_{n\cdot k}</math>
* Hérédité (rang <math>k+1\,</math>) :
:<math>\mathcal{F}_{n\cdot(k+1)}=\mathcal{F}_{n-1}\mathcal{F}_{n\cdot k}+\mathcal{F}_{n}\mathcal{F}_{n\cdot k + 1}</math> (Propriété 1)
:<math>\mathcal{F}_{n\cdot(k+1)}=\mathcal{F}_n(\lambda\cdot\mathcal{F}_{n-1}+\mathcal{F}_{n\cdot k+1})</math> (Hypothèse de récurrence)
:<math>\mathcal{F}_{n\cdot(k+1)}=\mu\cdot\mathcal{F}_n</math>
}}
:''Corollaire'' : si <math>n\,\neq\,4</math> et <math>\mathcal{F}_n</math> est premier, <math>n\,</math> est premier.
:En effet, supposons <math>n\,</math> composé. Si <math>m\,</math> est un diviseur propre de <math>n\,</math>, on a d'après la propriété 2 : <math>\mathcal{F}_m{}|{}\mathcal{F}_{n}</math>, contrairement à l'hypothèse que <math>\mathcal{F}_n</math> est premier. Donc <math>n\,</math> est premier.
:On peut écrire le corollaire comme suit, en désignant par <math>\mathbb{P}</math> l'ensemble des nombres premiers :
::<math>\forall n \in \mathbb{N}\setminus\{4\}, \mathcal{F}_n\in\mathbb{P}{}\Rightarrow{}n\in\mathbb{P}</math>
:La réciproque est fausse, car <math>2\in\mathbb{P},\mathcal{F}_2{}\not\in{}\mathbb{P}</math>.
'''Propriété 3''' : <math>\forall (k,n)\in\mathbb{N}^2{}/{}n{}\ge{}k{}\ge{}0, \mathcal{F}_n{}\mathcal{F}_{k+1}-\mathcal{F}_k\mathcal{F}_{n+1}=(-1)^k\mathcal{F}_{n-k}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence sur ''k''
* Initialisation (rang ''k'' = 0) : <math>\forall n \geq 0,\quad \mathcal{F}_n\mathcal{F}_1-\mathcal{F}_0\mathcal{F}_{n+1}=\mathcal{F}_n</math> et <math>(-1)^0\mathcal{F}_n = \mathcal{F}_n</math>
* Hypothèse de récurrence : au rang ''k'', <math>\forall n \geq k,\quad \mathcal{F}_n{}\mathcal{F}_{k+1}-\mathcal{F}_k\mathcal{F}_{n+1}=(-1)^k\mathcal{F}_{n-k}</math>
* Hérédité (rang ''k'' + 1) :<math>\forall n \geq k+1</math>
:<math>\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=\mathcal{F}_n(\mathcal{F}_{k+1}+\mathcal{F}_k) - \mathcal{F}_{k+1}(\mathcal{F}_n+\mathcal{F}_{n-1})</math> (Définition de la suite de Fibonacci)
:<math>\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=-(\mathcal{F}_{n-1}\mathcal{F}_{k+1}-\mathcal{F}_k\mathcal{F}_n)</math> (Associativité, commutativité)
:<math>\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=-(-1)^k\mathcal{F}_{n-k-1}</math>(Hypothèse de récurrence pour <math>n-1\,</math> et <math> k\,</math>)
:<math>\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=(-1)^{k+1}\mathcal{F}_{n-(k+1)}</math>
}}
'''Propriété 4''' : <math>\forall (p,q)\in\mathbb{N}^2{}, \mathcal{F}_p{}\land{}\mathcal{F}_q = \mathcal{F}_{p{}\land{}q}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Soient ''p'' et ''q'' deux entiers naturels. Soit <math>\delta = p{}\land{}q</math> et <math>\Delta = \mathcal{F}_p\land\mathcal{F}_q</math>
* <math>p = p'{}\cdot{}\delta</math> et <math>q = q'{}\cdot{}\delta</math> donc <math>\mathcal{F}_\delta{}|{}\mathcal{F}_p</math> et <math>\mathcal{F}_\delta{}|{}\mathcal{F}_q</math> '''(Propriété 2)''', d'où nous tirons que <math>\mathcal{F}_\delta{}|{}\mathcal{F}_p{}\land{}\mathcal{F}_q</math>, et donc <math>\mathcal{F}_\delta{}|{}\Delta</math>.
* La généralisation du théorème de Bézout nous permet d’affirmer qu’il existe deux entiers naturels ''a'' et ''b'' (<math>a{}\ge{}b</math>) tels que <math>\delta = a\cdot p - b\cdot q</math> ou <math>\delta = a\cdot q - b\cdot p</math>. Supposons que <math>\delta = a\cdot p - b\cdot q</math> (une démonstration analogue peut être faite pour l'autre cas). D'autre part, <math>\Delta{}|{}\mathcal{F}_p</math> et <math>\Delta{}|{}\mathcal{F}_q</math> donc <math>\Delta{}|{}\mathcal{F}_{a\cdot p}</math> et <math>\Delta{}|{}\mathcal{F}_{b\cdot q}</math> '''(Propriété 2)'''. Comme <math>\Delta\,</math> en divise aussi toute combinaison linéaire, <math>\Delta{}|{}\mathcal{F}_{a \cdot p}\mathcal{F}_{b\cdot q + 1} - \mathcal{F}_{b \cdot q}\mathcal{F}_{a\cdot p + 1}</math> c'est-à-dire <math>\Delta{}|{}(-1)^{b\cdot q}\mathcal{F}_{a\cdot p^- b\cdot q}</math> '''(Propriété 3)''', soit donc <math>\Delta{}|{}(-1)^{b\cdot q}\mathcal{F}_{\delta}</math> autrement dit <math>\Delta{}|{}\mathcal{F}_{\delta}</math>. Or tout terme de la suite de Fibonacci est positif ou nul, nous en concluons que <math>\Delta=\mathcal{F}_{\delta}</math>.
}}
:En particulier, <math>\forall n\in\mathbb{N}{},\mathcal{F}_n{}\land{}\mathcal{F}_{n+1}=1</math>   c.-à-d. que <math>\mathcal{F}_n \perp \mathcal{F}_{n+1}</math>
'''Propriété 5''' : <math>\forall n\in\mathbb{N}^*{}, \mathcal{L}_n = \mathcal{F}_{n-1}+\mathcal{F}_{n+1}</math>
:(Précision : les nombres de Lucas <math> \mathcal{L}_n</math> ont même relation de récurrence mais ont pour initialisation <math> \mathcal{L}_0 = 2</math> et <math> \mathcal{L}_1 = 1</math>)
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence d'ordre 2 sur ''n''
* Initialisations
:(''n'' = 1) : <math>\mathcal{L}_1 = 1</math> et <math>\mathcal{F}_0 + \mathcal{F}_2 = 1</math>
:(''n'' = 2) : <math>\mathcal{L}_2 = 3</math> et <math>\mathcal{F}_1 + \mathcal{F}_3 = 3</math>
* Hypothèses de récurrence :
:au rang ''n'', <math>\mathcal{L}_n = \mathcal{F}_{n-1}+\mathcal{F}_{n+1}</math>
:au rang ''n+1'', <math>\mathcal{L}_{n+1} = \mathcal{F}_{n}+\mathcal{F}_{n+2}</math>
* Hérédité (rang ''n'' + 2) :
:<math>\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=\mathcal{F}_{n}+\mathcal{F}_{n-1}+\mathcal{F}_{n+2}+\mathcal{F}_{n+1}</math> (Définition de la suite de Fibonacci)
:<math>\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=(\mathcal{F}_{n-1}+\mathcal{F}_{n+1})+(\mathcal{F}_{n}+\mathcal{F}_{n+2})</math> (Associativité, commutativité)
:<math>\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=\mathcal{L}_n+\mathcal{L}_{n+1}</math> (Hypothèses de récurrence)
:<math>\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=\mathcal{L}_{n+2}</math> (Définition des nombres de Lucas)
}}
'''Propriété 6''' : <math>\forall n\in\mathbb{N}-\{0,1,2\}{},2\mathcal{L}_n=\mathcal{F}_{n-3}+\mathcal{F}_{n+3}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
:<math>2\mathcal{L}_n = \mathcal{L}_{n+1} - \mathcal{L}_{n-1} + \mathcal{L}_{n+2} - \mathcal{L}_{n+1} </math> (définition des nombres de Lucas)
:<math>2\mathcal{L}_n = \mathcal{L}_{n+2} - \mathcal{L}_{n-1}</math> (simplification)
:<math>2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n+1} - (\mathcal{F}_{n} + \mathcal{F}_{n-2})</math> (Propriété 5)
:<math>2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n} + \mathcal{F}_{n-1} - (\mathcal{F}_{n} + \mathcal{F}_{n-2})</math> (Définition de la suite de Fibonacci)
:<math>2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n-3} + \mathcal{F}_{n-2} - \mathcal{F}_{n-2}</math> (Simplification, définition de la suite de Fibonacci)
:<math>2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n-3}</math> (Simplication)
}}
'''Propriété 7''' : <math>\forall n\in\mathbb{N}{}, \mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_{n}\mathcal{L}_{n}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
On distinguera deux cas
* Pour ''n'' = 0 : <math>\mathcal{F}_0 = 0</math> et <math>\mathcal{F}_0\mathcal{L}_0 = 0</math>
* Pour ''n > 0'',
:<math>\mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_{n+n}</math>
:<math> \mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_{n-1}\mathcal{F}_n + \mathcal{F}_n\mathcal{F}_{n+1}</math> (Propriété 1)
:<math> \mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_n(\mathcal{F}_{n-1} + \mathcal{F}_{n+1})</math> (Factorisation)
:<math> \mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_n\mathcal{L}_n</math> (Propriété 5)
}}
'''Propriété 8''' : <math>\forall n\in\mathbb{N}^*{}, \mathcal{F}_{2{}\cdot{}n-1} = \mathcal{F}_{n-1}^2+\mathcal{F}_{n}^2</math>
:par application directe de la propriété 1 pour ''p = n'' et ''q = n -1''
'''Propriété 9''' : <math>\forall n\in\mathbb{N}^*{}, \mathcal{F}_{n+1}\mathcal{F}_{n-1} -\mathcal{F}_n^2= (-1)^n</math>   (identité de [[Cassini]])
{{boîte déroulante|align=left|titre=Démonstration|contenu=
En remplaçant ''k'' par ''n - 1'' dans la propriété 3
:<math> \mathcal{F}_{n}\mathcal{F}_{n} - \mathcal{F}_{n-1}\mathcal{F}_{n+1} = (-1)^{n-1}\mathcal{F}_{1}</math>
En multipliant par (-1) et en remplaçant <math>\mathcal{F}_{1}</math> par 1
:<math> \mathcal{F}_{n+1}\mathcal{F}_{n-1} - \mathcal{F}_{n}^2 = (-1)^{n}</math>
}}
'''Propriété 10''' : <math>\forall n\in\mathbb{N}{},1+\sum_{i=0}^n \mathcal{F}_i=\mathcal{F}_{n+2}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence sur ''n''.
*Initialisation (''n'' = 0) : <math>1+\sum_{i=0}^0 \mathcal{F}_i=1</math> et <math>\mathcal{F}_2=1</math>
*Hypothèse de récurrence : au rang ''n'', <math>1+\sum_{i=0}^n \mathcal{F}_i=\mathcal{F}_{n+2}</math>
*Hérédité (rang ''n'' + 1) :
:<math>1+\sum_{i=0}^{n+1} \mathcal{F}_i=1+\sum_{i=0}^n \mathcal{F}_i+\mathcal{F}_{n+1}</math> (Calcul sur les sommes)
:<math>1+\sum_{i=0}^{n+1} \mathcal{F}_i=\mathcal{F}_{n+1}+\mathcal{F}_{n+2}</math> (Hypothèse de récurrence)
:<math>1+\sum_{i=0}^{n+1} \mathcal{F}_i=\mathcal{F}_{(n+1)+2}</math> (Définition de la suite de Fibonacci)
}}
'''Propriété 11''' : <math>\forall n\in\mathbb{N}{},1+\sum_{i=0}^n \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}n+1}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence sur ''n''
*Initialisation (''n'' = 0) : <math>1+\sum_{i=0}^0 \mathcal{F}_{2{}\cdot{}i}=1</math> et <math>\mathcal{F}_1=1</math>
*Hypothèse de récurrence : au rang ''n'', <math>1+\sum_{i=0}^n \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}n+1}</math>
*Hérédité (rang ''n'' + 1) :
:<math>1+\sum_{i=0}^{n+1} \mathcal{F}_{2{}\cdot{}i}=1+\sum_{i=0}^n \mathcal{F}_{2{}\cdot{}i}+\mathcal{F}_{2{}\cdot{}n+2}</math> (Calcul sur les sommes)
:<math>1+\sum_{i=0}^{n+1} \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}n+1}+\mathcal{F}_{2{}\cdot{}n+2}</math> (Hypothèse de récurrence)
:<math>1+\sum_{i=0}^{n+1} \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}(n+1)+1}</math> (Définition de la suite de Fibonacci)
}}
'''Propriété 12''' : <math>\forall n\in\mathbb{N}{},\mathcal{F}_{n+1} = \sum_{k=0}^{\infty} {n-k \choose k}</math> où les <math> n-k \choose k</math> sont des [[Coefficient binomial|coefficients binomiaux]].
{{boîte déroulante|align=left|titre=Démonstration|contenu=
En réalité, la somme n'est pas infinie car tous les <math> n-k \choose k</math> sont nuls pour ''k > n - k'' mais on sommera sur <math>\infty</math> pour faciliter les démonstrations.
Par récurrence d'ordre 2 sur ''n''.
*Initialisation
:(''n'' = 0) : <math>\sum_{k=0}^{\infty} {0-k\choose k} = 1</math> et <math>\mathcal{F}_1 = 1</math>
:(''n'' = 1) : <math>\sum_{k=0}^{\infty} {1-k\choose k} = 1 </math> et <math>\mathcal{F}_2 = 1</math>
*Hypothèses de récurrence :
: au rang ''n'', <math>\mathcal{F}_{n+1} = \sum_{k=0}^{\infty} {n - k \choose k}</math>
: au rang ''n + 1'', <math>\mathcal{F}_{n+2} = \sum_{k=0}^{\infty} {n +1 - k \choose k}</math>
*Hérédité (rang ''n'' + 2) :
:<math>\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \sum_{k=0}^{\infty} {(n+1) - k \choose k} + {(n+1) - k \choose k-1}</math>
:::(Formule du triangle de Pascal)
:<math>\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}</math>
:::Car <math>{n+1 \choose -1} = 0</math>)
:<math>\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+2}+\sum_{m=0}^{\infty}{n - m \choose m}</math>
:::(Hypothèse de récurrence, changement de variable <math>m = k - 1\,</math>)
:<math>\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+2}+ \mathcal{F}_{n+1}</math> (Hypothèse de récurrence)
:<math>\sum_{k=0}^{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+3} </math> (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)
'''Propriété 13''' : <math>\forall n\in\mathbb{N}^*,\varphi^n = \mathcal{F}_n{}\cdot{}\varphi + \mathcal{F}_{n-1}</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence sur <math>n\,</math>
* Initialisation (<math>n = 1\,</math>) : <math>\varphi^1 = \mathcal{F}_1{}\cdot{}\varphi + \mathcal{F}_0</math>
* Hypothèse de récurrence : au rang <math>n\,</math>, <math>\varphi^n = \mathcal{F}_n{}\cdot{}\varphi + \mathcal{F}_{n-1}</math>
* Hérédité (rang <math>n + 1\,</math>) :
:<math>\varphi^{n+1}= \varphi{}\cdot{}\varphi^n</math> (Calculs sur les puissances)
:<math>\varphi^{n+1} =\varphi{}\cdot{}(\mathcal{F}_n{}\cdot{}\varphi + \mathcal{F}_{n-1})</math>
:<math>\varphi^{n+1}=\varphi^2\mathcal{F}_n+\varphi\mathcal{F}_{n-1}</math> (Distributivité)
:<math>\varphi^{n+1}=(1+\varphi)\mathcal{F}_n+\varphi\mathcal{F}_{n-1}</math> (Hypothèse de récurrence appliquée au cas <math>n = 2\,</math>)
:<math>\varphi^{n+1}=\varphi(\mathcal{F}_{n-1}+\mathcal{F}_n)+\mathcal{F}_n</math> (Factorisation)
:<math>\varphi^{n+1}=\mathcal{F}_{n+1}{}\cdot{}\varphi+\mathcal{F}_n</math> (Définition de la suite de Fibonacci)
}}
'''Propriété 14''' : <math>\forall n > 2,\mathcal{F}_{n+2}\mathcal{F}_{n+1}\mathcal{F}_{n-1}\mathcal{F}_{n-2} - \mathcal{F}_{n}^4 + 1 = 0</math>
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Il suffit de remplacer <math>\mathcal{F}_n</math> par son expression en fonction de <math>\varphi</math> et <math>\varphi'</math>, et de simplifier l'expression.
}}
== Formules closes ==
* La formule suivante permet de retrouver tous les nombres de Fibonacci (formule de Binet):
:<math>\forall n \in \mathbb{Z}, \mathcal{F}_{n} = \frac{1}{\sqrt{5}} (\varphi^n - \varphi'^n) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^{n} - \left( \frac{1 - \sqrt{5}}{2} \right)^{n} \right]</math>
* La formule suivante permet de retrouver tous les nombres de Lucas (formule de Maillet):
:<math>\forall n \in \mathbb{Z}, \mathcal{L}_{n} = \varphi^n + \varphi'^n = \left( \frac{1 + \sqrt{5}}{2} \right)^{n} + \left( \frac{1 - \sqrt{5}}{2} \right)^{n}</math>
== Primalité des nombres de Fibonacci ==
On ignore s'il existe une infinité de nombres de Fibonacci premiers. On sait que <math>\mathcal{F}_n</math> divise <math>\mathcal{F}_{k{}\cdot{}n}</math> (voir [[#Propriétés de la suite de Fibonacci|Propriétés]], ''Propriété 2''), et donc que, pour tout <math>n >4\, </math>, si <math>\mathcal{F}_n</math> est premier, alors <math>n\,</math> est premier, mais la réciproque est fausse. Le plus grand nombre de Fibonacci premier connu est <math>\mathcal{F}_{604711}</math> qui possède 126377 chiffres.
Il existe des suites <math>(\mathcal{T}_n)</math> vérifiant en même temps les trois conditions suivantes :
* <math>\mathcal{T}_{n+2}=\mathcal{T}_{n+1}+\mathcal{T}_n</math>
* <math>\mathcal{T}_n{}</math> et <math>\mathcal{T}_{n+1}</math> sont premiers entre eux (ils n'ont aucun [[diviseur]] commun).
* <math>\forall n\in\mathbb{N},\; \mathcal{T}_n</math> n'est pas [[Nombre premier|premier]].
Les plus petits exemples connus sont déterminés par :
* <math>\mathcal{T}_0 = 3794765361567513 = 3\cdot 1264921787189171</math>
* <math>\mathcal{T}_1 = 20615674205555510 = 2\cdot 5\cdot 5623\cdot 366631232537</math>
* <math>\mathcal{T}_0 = 1786772701928802632268715130455793 = 2521\cdot 49993\cdot 14177095479037851751198481</math>
* <math>\mathcal{T}_1 = 1059683225053915111058165141686995 = 3\cdot 5\cdot 84089\cdot 73919059\cdot 150031897\cdot 75754002239</math>
== Applications ==
* 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 a donné des règles explicites au VIII{{e}} siècle. Le philosophe Indien [[Hemachandra]] (c.[[1150]]) (et aussi [[Gopala]]) 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.
* [[Yuri Matiyasevich|Matiyasevich]] a montré que les nombres de Fibonacci pouvaient être définis par une [[équation diophantienne]], ce qui a conduit à la résolution du [[Diophantien|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 <math>2xy^4 + x^2y^3 - 2x^3y^2 - y^5 - x^4y + 2y</math> é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 de la suite de Fibonacci|Propriétés]], ''Propriété 11'').
* Une utilisation intéressante des suites de Fibonacci est la conversion des miles en kilomètres. Par exemple, pour savoir combien de kilomètres font 5 miles, il suffit de considérer le <math>\mathcal{F}_5 = 5</math> et le suivant <math>\mathcal{F}_6 = 8</math>. 5 miles font environ 8 kilomètres. Cela fonctionne parce que le facteur de conversion entre les miles et les kilomètres est grossièrement égal à <math>\varphi\,</math>.
[[Image:FibonacciBlocks.png|thumbnail|right|220px|Carrés de Fibonacci en spirale.]]
* Une bonne approximation d'un [[Nombre d'or#Propriétés géométriques|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 <math>\mathcal{F}_1</math> unités vers la droite, puis de <math>\mathcal{F}_2</math> unités vers le haut, on se déplace de <math>\mathcal{F}_3</math> unités vers la gauche, ensuite de <math>\mathcal{F}_4</math> unités vers le bas, puis de <math>\mathcal{F}_5</math> 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.
* 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<sup>''n''</sup>. Mais les [[Hymenoptera|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 <math>\mathcal F_n</math> mâles et <math>\mathcal F_{n+1}</math> femelles,
::pour les mâles, de <math>\mathcal F_{n-1}</math> mâles et <math>\mathcal F_n</math> femelles.
* Le nombre de façons différentes de [[Pavage|paver]] un [[rectangle]] 2×N au moyen de [[domino (jeu)|dominos]] 2×1 est <math>\mathcal F_{N+1}</math>.
{{boîte déroulante|align=left|titre=Démonstration|contenu=
Par récurrence sur N que l'on considéra comme la longueur horizontale du rectangle 2×N :
* Initialisation :
*: Le rectange 2×1 est un domino 2×1 ; il y a 1 seule façon de paver ce rectangle <math>\left( 1=\mathcal F_2 \right)</math>.
* Supposons qu'il y ait <math>\mathcal F_{N+1}</math> façons de paver le rectangle 2×N.
* Considérons le rectangle 2×<math>\mathcal F_{N+1}</math> :
** 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 <math>\mathcal F_N</math> 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 <math>\mathcal F_{N+1}</math> 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 <math>\mathcal F_{N} + \mathcal F_{N+1} = \mathcal F_{N+2}</math>, ce qui termine le raisonnement par récurrence.
}}
== 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 [[Suite récurrente linéaire|ordre]]) de la relation de récurrence.
=== Suites de Fibonacci généralisées ===
Ce sont des suites qui conservent la même relation de récurrence mais dont les termes initiaux ont changé. Comme l'a démontré la première partie, ces suites sont des combinaisons linéaires des deux suites géométriques <math>(\varphi)^n</math> et <math>(1-\varphi )^n</math> où φ est le [[nombre d'or]]. Le quotient de deux termes consécutifs tend toujours vers φ.
Parmi ces suites de nombres, il faut signaler les nombres de Lucas obtenus en choisissant comme initialisation : <math>\mathcal{L}_0 =2 </math> et <math>\mathcal{L}_1=1</math>. Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29, … On trouve parfois une initialisation <math>\mathcal{L}_0 =1</math> et <math>\mathcal{L}_1=3</math> qui ne consiste qu'à décaler la suite d'un rang. Ces nombres interviennent dans la résolution d'[[Équation diophantienne|équations diophantiennes]]. Ils sont très liés à la suite de Fibonacci, en particulier par la relation suivante : <math>\mathcal{L}_n = \mathcal{F}_{n+1} + \mathcal{F}_{n-1}\,</math> pour tout entier ''n'' strictement positif (voir [[#Propriétés de la suite de Fibonacci|Propriétés]], ''Propriété 5'').
=== Suites de Lucas ===
Ce sont les suites où la relation de récurrence a changé : elle est devenue
:<math> U_{n+2} = P \cdot U_n + Q \cdot U_{n+1}</math>
Elles sont de deux types selon que l'initialisation est de <math> u_0 =0 </math> et <math>u_1=1</math> ou qu'elle est <math> v_0 =2 </math> et <math>v_1=P</math>.
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 <math>P = 1</math> et <math>Q = 1</math>.
{{Article détaillé|Suite de Lucas|Nombre de Lucas}}
=== 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
:<math> u_{n+k} \, = \, u_n + u_{n+1} + u_{n+2} + \dots +u_{n+k - 1}</math>
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 à [[suite récurrente linéaire|récurrence linéaire]].
== Voir aussi ==
=== Articles connexes ===
* [[Leonardo Pisano]]
* [[Groupe de Fibonacci]]
* [[Suite de Padovan]]
* [[Nombre d'or]]
=== Liens externes ===
* [http://www.le-triangle-et-ses-calculs.ch/fibonacci.htm Divisibilité des nombre de Fibonacci]
* [http://framy.free.fr/fibonacci%20dans%20mandelbrot.htm Suite de Fibonacci et nombre d'or dans l'ensemble de Mandelbrot]
* [http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Fibonacc.htm Suite de Fibonacci dans le dictionnaire des nombres]
* [http://gottabook.blogspot.com/2006/04/fib.html Le blog de Gregory Pincus], qui invente des ''fibs'', une forme de [[poésie]] utilisant la suite de Fibonacci
* [http://nacho.myweb.io/espiral.htm La Espiral de Durero y Las Meninas de Velázquez]
* [http://www.cite-sciences.fr/francais/ala_cite/college/v2/html/2007_2008/conferences/conference_431.htm Les suites de Fibonacci aléatoires], conférence de [[Benoît Rittaud]] à la [[Cité des sciences et de l'industrie]]
* (en) [[:en:Zeckendorf's theorem|Zeckendorf's theorem]]
{{Portail mathématiques}}
[[Catégorie:Suite d'entiers|Fibonacci]]
[[ar:متتالية فيبوناتشي]]
[[az:Fibonnaççi ədədləri]]
[[bg:Числа на Фибоначи]]
[[bn:ফিবোনাচ্চি রাশিমালা]]
[[bs:Fibonaccijev broj]]
[[ca:Successió de Fibonacci]]
[[cs:Fibonacciho posloupnost]]
[[da:Fibonacci-tal]]
[[de:Fibonacci-Folge]]
[[el:Ακολουθία Φιμπονάτσι]]
[[en:Fibonacci number]]
[[eo:Fibonaĉi-nombro]]
[[es:Sucesión de Fibonacci]]
[[et:Fibonacci jada]]
[[eu:Fibonacciren zenbakiak]]
[[fa:اعداد فیبوناچی]]
[[fi:Fibonaccin lukujono]]
[[he:סדרת פיבונאצ'י]]
[[hi:हेमचन्द्र श्रेणी]]
[[hr:Fibonaccijev broj]]
[[hu:Fibonacci-számok]]
[[id:Bilangan Fibonacci]]
[[is:Fibonacciruna]]
[[it:Successione di Fibonacci]]
[[ja:フィボナッチ数]]
[[ko:피보나치 수]]
[[lt:Fibonačio skaičius]]
[[lv:Fibonači skaitļi]]
[[ml:ഫിബനാച്ചി സംഖ്യ]]
[[nl:Rij van Fibonacci]]
[[no:Fibonaccifølgen]]
[[pl:Ciąg Fibonacciego]]
[[pms:Sequensa ëd Fibonacci]]
[[pt:Número de Fibonacci]]
[[ro:Numerele Fibonacci]]
[[ru:Числа Фибоначчи]]
[[scn:Succissioni di Fibonacci]]
[[sk:Fibonacciho postupnosť]]
[[sl:Fibonaccijevo število]]
[[sr:Фибоначијев низ]]
[[sv:Fibonaccital]]
[[ta:ஃபிபனாச்சி எண்கள்]]
[[th:เลขฟีโบนัชชี]]
[[tr:Fibonacci serisi]]
[[uk:Послідовність Фібоначчі]]
[[vi:Dãy Fibonacci]]
[[vls:Reke van Fibonacci]]
[[zh:斐波那契数列]]