Une séquence de nombres commençant par 0, 1, dans laquelle chaque nombre est la somme des deux nombres précédents, porte le nom de quel mathématicien italien a conçu le système ?
Fibonacci
En mathématiques, les nombres de Fibonacci sont les nombres de la séquence entière suivante, appelée séquence de Fibonacci : Par définition, les deux premiers nombres de la séquence de Fibonacci sont soit 1 et 1, soit 0 et 1, selon le point de départ choisi de la séquence, et chaque nombre suivant est la somme des deux précédents. En termes mathématiques, la séquence Fn de nombres de Fibonacci est définie par la relation de récurrence La séquence de Fibonacci doit son nom au mathématicien italien Léonard de Pise, connu sous le nom de Fibonacci. Son livre de 1202 Liber Abaci a introduit la séquence dans les mathématiques d'Europe occidentale, bien que la séquence ait été décrite plus tôt comme des nombres Virahanka dans les mathématiques indiennes. Par convention moderne, la séquence commence soit par F0 Les nombres de Fibonacci sont étroitement liés aux nombres de Lucas L_n dans la mesure où ils forment une paire complémentaire de séquences de Lucas U_n(1,-1)F_n et V_n(1,-1) Les nombres de Fibonacci apparaissent souvent de manière inattendue en mathématiques, à tel point qu'il existe une revue entière dédiée à leur étude, le Fibonacci Quarterly. Les applications des nombres de Fibonacci incluent des algorithmes informatiques tels que la technique de recherche de Fibonacci et la structure de données en tas de Fibonacci, ainsi que des graphiques appelés cubes de Fibonacci utilisés pour interconnecter des systèmes parallèles et distribués. Ils apparaissent également dans des contextes biologiques, tels que la ramification des arbres, la phyllotaxie (la disposition des feuilles sur une tige), les pousses de fruits d'un ananas, la floraison d'un artichaut, une fougère enroulée et la disposition des bractées d'une pomme de pin. La séquence de Fibonacci apparaît dans les mathématiques indiennes, en lien avec la prosodie sanskrite. Dans la tradition sanskrite de la prosodie, il y avait un intérêt à énumérer tous les modèles de syllabes longues (L) qui représentent 2 unités de durée et de syllabes courtes (S) qui représentent 1 unité de durée. Compter les différents modèles de L et S d'une durée donnée donne les nombres de Fibonacci : le nombre de modèles qui sont longs de m syllabes courtes est le nombre de Fibonacci Fm + 1. Susantha Goonatilake écrit que le développement de la séquence de Fibonacci « est attribué en partie à Pingala (200 avant JC), étant plus tard associé à Virahanka (vers 700 après JC), Gopāla (vers 1135) et Hemachandra (vers 1150) ». Parmanand Singh cite la formule énigmatique de Pingala misrau cha (« les deux sont mélangés ») et cite des chercheurs qui l'interprètent dans son contexte comme disant que les cas pour m battements (Fm+1) sont obtenus en ajoutant un [S] aux cas Fm et [ L] aux cas Fm−1. Il date de Pingala avant 450 avant JC. En dehors de l'Inde, la séquence de Fibonacci apparaît pour la première fois dans le livre Liber Abaci (1202) de Fibonacci. Fibonacci considère la croissance d'une population de lapins idéalisée (biologiquement irréaliste), en supposant que : un couple de lapins nouveau-nés, un mâle et une femelle, est mis dans un champ ; les lapins sont capables de s'accoupler à l'âge d'un mois afin qu'à la fin de son deuxième mois, une femelle puisse produire un autre couple de lapins ; les lapins ne meurent jamais et un couple accouplé produit toujours un nouveau couple (un mâle, une femelle) chaque mois à partir du deuxième mois. Le casse-tête posé par Fibonacci était le suivant : combien de paires y aura-t-il en un an ? À la fin du nième mois, le nombre de couples de lapins est égal au nombre de nouveaux couples (qui est le nombre de couples au mois n − 2) plus le nombre de couples vivants le mois dernier (n − 1). C'est le nième nombre de Fibonacci. Le nom « séquence de Fibonacci » a été utilisé pour la première fois par le théoricien des nombres du XIXe siècle, Édouard Lucas. Liste des numéros de Fibonacci Les 21 premiers nombres de Fibonacci Fn pour n = 0, 1, 2, …, 20 sont : les 300 premiers Fn sont-ils pris en compte en nombres premiers et en liens vers des tableaux plus complets. Les nombres de Fibonacci apparaissent dans les sommes des diagonales « peu profondes » du triangle de Pascal (voir Coefficient binomial). Les nombres de Fibonacci peuvent être trouvés de différentes manières parmi l’ensemble des chaînes binaires, ou de manière équivalente, parmi les sous-ensembles d’un ensemble donné. * Le nombre de chaînes binaires de longueur n sans 1 consécutifs est le nombre de Fibonacci Fn+2. Par exemple, sur les 16 chaînes binaires de longueur 4, il y a F6 8 sans 1 consécutifs – ce sont 0000, 0001, 0010, 0100, 0101, 1000, 1001 et 1010. Par symétrie, le nombre de chaînes de longueur n sans les 0 consécutifs sont également Fn+2. De manière équivalente, Fn+2 est le nombre de sous-ensembles S ⊂ {1,...,n} sans entiers consécutifs : {i, i+1} ⊄ S pour chaque i. L'énoncé symétrique est : Fn+2 est le nombre de sous-ensembles S ⊂ {1,...,n} sans deux entiers sautés consécutifs : c'est-à-dire S * Le nombre de chaînes binaires de longueur n sans nombre impair de 1 consécutifs est le nombre de Fibonacci Fn+1. Par exemple, sur les 16 chaînes binaires de longueur 4, il y a F5 = 5 sans nombre impair de 1 consécutifs – ils sont 0000, 0011, 0110, 1100, 1111. De manière équivalente, le nombre de sous-ensembles S ⊂ {1,. ..,n} sans un nombre impair d’entiers consécutifs est Fn+1. Comme toute séquence définie par une récurrence linéaire à coefficients constants, les nombres de Fibonacci ont une solution de forme fermée. On l'appelle désormais « formule de Binet », même si elle était déjà connue par Abraham de Moivre : donc les puissances de φ et ψ satisfont la récursion de Fibonacci. Autrement dit, 1 alors la séquence résultante Un doit être la séquence de Fibonacci. Cela revient à exiger que a et b satisfassent le système d’équations : De même, si l’on sait déjà que le nombre F > 1 est un nombre de Fibonacci, on peut déterminer son indice dans la séquence par Johannes Kepler a observé que le rapport des nombres de Fibonacci consécutifs converge. Il a écrit que "comme 5 est à 8, ainsi est 8 à 13, pratiquement, et comme 8 est à 13, ainsi est presque 13 à 21", et a conclu que la limite se rapproche du nombre d'or \varphi. Une autre conséquence est que la limite du rapport de deux nombres de Fibonacci compensés par un écart fini particulier d'indice correspond au nombre d'or élevé par cet écart. Ou, en d'autres termes : cette expression peut être utilisée pour décomposer les puissances supérieures \varphi^n en fonction linéaire des puissances inférieures, qui à leur tour peuvent être décomposées jusqu'à une combinaison linéaire de \varphi et 1. Les relations de récurrence qui en résultent donnent des nombres de Fibonacci comme coefficients linéaires : Cette expression est également vraie pour n n est étendu aux entiers négatifs en utilisant la règle de Fibonacci F_n = F_{n-1} + F_{n-2}. Un système bidimensionnel d'équations aux différences linéaires qui décrit la séquence de Fibonacci est d'où le ème élément de la série de Fibonacci L'expression fermée du ème élément de la série de Fibonacci est donc donnée par Les nombres de Fibonacci apparaissent comme le rapport des convergents successifs de la fraction continue pour , et la matrice formée à partir des convergents successifs de toute fraction continue a un déterminant de +1 ou −1. La représentation matricielle donne l'expression fermée suivante pour les nombres de Fibonacci : Ces deux dernières identités permettent de calculer les nombres de Fibonacci de manière récursive dans des opérations arithmétiques et en temps, où est le temps de multiplication de deux nombres de n chiffres. Cela correspond au temps de calcul du nième nombre de Fibonacci à partir de la formule matricielle fermée, mais avec moins d'étapes redondantes si l'on évite de recalculer un nombre de Fibonacci déjà calculé (récursion avec mémorisation). Reconnaître les nombres de Fibonacci La question peut se poser de savoir si un entier positif x est un nombre de Fibonacci. Cela est vrai si et seulement si l'un ou les deux de 5x^2+4 ou 5x^2-4 est un carré parfait. En effet, la formule de Binet ci-dessus peut être réorganisée pour donner ce qui permet de trouver la position dans la séquence d'un nombre de Fibonacci donné. La plupart des identités impliquant des nombres de Fibonacci peuvent être prouvées à l'aide d'arguments combinatoires en utilisant le fait que Fn peut être interprété comme le nombre de séquences de 1 et de 2 dont la somme est n − 1. Cela peut être considéré comme la définition de Fn, avec la convention selon laquelle F0 0, ce qui signifie qu'aucune somme ne vaut −1, et que F1 ou en mots, le nième nombre de Fibonacci est la somme des deux nombres de Fibonacci précédents, peut être affiché en divisant les sommes Fn de 1 et de 2 qui s'ajoutent à n − 1 en deux groupes qui ne se chevauchent pas. Un groupe contient les sommes dont le premier terme est 1 et l'autre les sommes dont le premier terme est 2. Dans le premier groupe, les termes restants s'ajoutent à n − 2, il a donc des sommes Fn-1, et dans le deuxième groupe les termes restants ajouter à n − 3, donc il y a des sommes Fn− 2. Il y a donc un total de sommes Fn−1 + Fn−2, ce qui montre que cela est égal à Fn. De même, on peut montrer que la somme des premiers nombres de Fibonacci jusqu'au nième est égale au (n + 2)-ième nombre de Fibonacci moins 1. En symboles : En mots, la somme des premiers nombres de Fibonacci d'indice impair jusqu'à F2n−1 est le (2n)ème nombre de Fibonacci, et la somme des premiers nombres de Fibonacci d'indice pair jusqu'à F2n est le (2n + 1)ème nombre de Fibonacci. nombre moins 1. ou en mots, la somme des carrés des premiers nombres de Fibonacci jusqu'à Fn est le produit du nième et du (n + 1)ième nombres de Fibonacci. Dans ce cas, notez que le rectangle de Fibonacci de taille Fn par F(n + 1) peut être décomposé en carrés de taille Fn, Fn−1, et ainsi de suite jusqu'à F1 = 1, d'où l'identité découle en comparant les aires. Ceux-ci peuvent être trouvés expérimentalement en utilisant la réduction de réseau et sont utiles pour mettre en place le tamis de champ numérique spécial pour factoriser un nombre de Fibonacci. La fonction génératrice de la séquence de Fibonacci est la série entière Cela peut être prouvé en utilisant la récurrence de Fibonacci pour développer chaque coefficient dans la somme infinie : Les sommes infinies sur les nombres de Fibonacci réciproques peuvent parfois être évaluées en termes de fonctions thêta. Par exemple, nous pouvons écrire la somme de chaque nombre de Fibonacci réciproque impair sous la forme et la somme des carrés des nombres de Fibonacci réciproques comme Si on ajoute 1 à chaque nombre de Fibonacci dans la première somme, on obtient aussi la forme fermée et il existe une somme imbriquée de carrés de nombres de Fibonacci donnant l'inverse du nombre d'or, Pas de formule fermée pour la constante de Fibonacci réciproque Chaque 3ème nombre de la séquence est pair et plus généralement, chaque kème nombre de la séquence est un multiple de Fk. Ainsi, la séquence de Fibonacci est un exemple de séquence de divisibilité. En fait, la suite de Fibonacci satisfait la propriété de divisibilité la plus forte Trois nombres de Fibonacci consécutifs sont premiers entre eux par paire, ce qui signifie que, pour chaque n, Tout nombre premier p divise un nombre de Fibonacci qui peut être déterminé par la valeur de p modulo 5. Si p est congru à 1 ou 4 (mod 5), alors p divise Fp − 1, et si p est congru à 2 ou 3 ( mod 5), alors, p divise Fp + 1. Le cas restant est que p = 5, et dans ce cas p divise Fp. Ces cas peuvent être regroupés en une seule formule, à l'aide du symbole Legendre :. Williams qualifie cette propriété de « bien connue ». n \mid F_{n-\left(\frac{5}{n}\right)}, où le symbole de Legendre a été remplacé par le symbole de Jacobi, alors c'est la preuve que n est premier, et s'il échoue tenez, alors n n'est certainement pas un nombre premier. Si n est composite et satisfait à la formule, alors n est un pseudopremier de Fibonacci. Fibonacci prime Un nombre premier de Fibonacci est un nombre de Fibonacci premier. Les premiers sont : Des nombres premiers de Fibonacci avec des milliers de chiffres ont été trouvés, mais on ne sait pas s'il y en a une infinité. Fkn est divisible par Fn, donc, mis à part F4 = 3, tout nombre premier de Fibonacci doit avoir un indice premier. Comme il existe des séries arbitrairement longues de nombres composés, il existe donc également des séries arbitrairement longues de nombres composites de Fibonacci. Aucun nombre de Fibonacci supérieur à F6 = 8 n’est supérieur ou inférieur d’un à un nombre premier. Le nombre carré de Fibonacci est 144. Attila Pethő a prouvé en 2001 qu'il n'existe qu'un nombre fini de nombres de Fibonacci puissance parfaite. En 2006, Y. Bugeaud, M. Mignotte et S. Siksek ont ​​prouvé que 8 et 144 sont les seules puissances parfaites non triviales. Diviseurs premiers des nombres de Fibonacci À l'exception de 1, 8 et 144 (F1 = F2, F6 et F12), chaque nombre de Fibonacci a un facteur premier qui n'est pas un facteur d'un nombre de Fibonacci plus petit (théorème de Carmichael). En conséquence, 8 et 144 (F6 et F12) sont les seuls nombres de Fibonacci qui sont le produit d'autres nombres de Fibonacci. La divisibilité des nombres de Fibonacci par un p premier est liée au symbole de Legendre \left(\tfrac{p}{5}\right) qui s'évalue comme suit : Tous les facteurs connus des nombres de Fibonacci F(i) pour tout i rassemble tous les facteurs connus de F(i) avec i rassemble tous les facteurs connus de F(i) avec 10000 Si les membres de la séquence de Fibonacci sont pris mod n, la séquence résultante est périodique avec un point au plus 6n. Les durées des périodes pour différents n forment ce que l'on appelle les périodes de Pisano. Déterminer une formule générale pour les périodes de Pisano est un problème ouvert, qui inclut comme sous-problème une instance particulière du problème de trouver l'ordre multiplicatif d'un entier modulaire ou d'un élément dans un corps fini. Cependant, pour tout n particulier, la période de Pisano peut être considérée comme un exemple de détection de cycle. En commençant par 5, un nombre de Fibonacci sur deux est la longueur de l'hypoténuse d'un triangle rectangle à côtés entiers, ou en d'autres termes, le plus grand nombre d'un triplet de Pythagore. La longueur de la branche la plus longue de ce triangle est égale à la somme des trois côtés du triangle précédent dans cette série de triangles, et la branche la plus courte est égale à la différence entre le nombre de Fibonacci contourné précédent et la branche la plus courte du nombre précédent. Triangle. Quatre nombres de Fibonacci consécutifs Fn, Fn+1, Fn+2 et Fn+3 peuvent également être utilisés pour générer un triplet de Pythagore d'une manière différente : Exemple 1 : soit les nombres de Fibonacci 1, 2, 3 et 5. Alors : Puisque Fn est asymptotique à \varphi^n/\sqrt5, le nombre de chiffres dans Fn est asymptotique à n\,\log_{10}\varphi\approx0.2090\,n. En conséquence, pour tout entier d > 1, il existe 4 ou 5 nombres de Fibonacci avec d chiffres décimaux. Les nombres de Fibonacci sont importants dans l'analyse informatique de l'algorithme d'Euclide pour déterminer le plus grand diviseur commun de deux entiers : l'entrée du pire cas pour cet algorithme est une paire de nombres de Fibonacci consécutifs. Brasch et coll. 2012 montrent comment une séquence de Fibonacci généralisée peut également être connectée au domaine de l'économie. En particulier, nous montrons comment une séquence de Fibonacci généralisée entre dans la fonction de contrôle de problèmes d'optimisation dynamique à horizon fini avec un état et une variable de contrôle. La procédure est illustrée dans un exemple souvent appelé modèle de croissance économique Brock-Mirman. Yuri Matiyasevich a pu montrer que les nombres de Fibonacci peuvent être définis par une équation diophantienne, ce qui a conduit à sa solution originale du dixième problème de Hilbert. Les nombres de Fibonacci sont également un exemple de séquence complète. Cela signifie que chaque entier positif peut être écrit comme une somme de nombres de Fibonacci, où un nombre est utilisé au maximum une fois. De plus, chaque entier positif peut être écrit de manière unique comme la somme d’un ou plusieurs nombres de Fibonacci distincts de telle sorte que la somme n’inclut pas deux nombres de Fibonacci consécutifs. C'est ce qu'on appelle le théorème de Zeckendorf, et une somme de nombres de Fibonacci qui satisfait à ces conditions est appelée une représentation de Zeckendorf. La représentation de Zeckendorf d'un nombre peut être utilisée pour dériver son codage de Fibonacci. Les nombres de Fibonacci sont utilisés par certains générateurs de nombres pseudo-aléatoires. Les nombres de Fibonacci sont utilisés dans une version polyphasée de l'algorithme de tri par fusion dans lequel une liste non triée est divisée en deux listes dont les longueurs correspondent aux nombres de Fibonacci séquentiels – en divisant la liste de sorte que les deux parties aient des longueurs dans la proportion approximative φ. Une implémentation sur lecteur de bande du tri par fusion polyphasé a été décrite dans The Art of Computer Programming. Les nombres de Fibonacci apparaissent lors de l'analyse de la structure de données du tas de Fibonacci. Le cube de Fibonacci est un graphe non orienté avec un nombre de nœuds de Fibonacci qui a été proposé comme topologie de réseau pour le calcul parallèle.
En mathématiques, les nombres de Fibonacci sont les nombres de la séquence entière suivante, appelée séquence de Fibonacci :
1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;
Souvent, surtout dans l'usage moderne, la séquence est étendue par un terme initial supplémentaire :
0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144, \; \ldots\;.
Par définition, les deux premiers nombres de la séquence de Fibonacci sont soit 1 et 1, soit 0 et 1, selon le point de départ choisi de la séquence, et chaque nombre suivant est la somme des deux précédents.
En termes mathématiques, la séquence Fn de nombres de Fibonacci est définie par la relation de récurrence
F_n = F_{n-1} + F_{n-2},\!\,
avec des valeurs de départ
F_1 1,\; F_2
1
ou
F_0 0,\; F_1
1.
La séquence de Fibonacci doit son nom au mathématicien italien Léonard de Pise, connu sous le nom de Fibonacci. Son livre de 1202 Liber Abaci a introduit la séquence dans les mathématiques d'Europe occidentale, bien que la séquence ait été décrite plus tôt comme des nombres Virahanka dans les mathématiques indiennes. Par convention moderne, la séquence commence soit par F0
0 ou avec F1  1. La séquence décrite dans Liber Abaci commençait par F1
1.
Les nombres de Fibonacci sont étroitement liés aux nombres de Lucas L_n dans la mesure où ils forment une paire complémentaire de séquences de Lucas U_n(1,-1)F_n et V_n(1,-1)
L_n. Ils sont intimement liés au nombre d’or ; par exemple, les approximations rationnelles les plus proches du rapport sont 2/1, 3/2, 5/3, 8/5, ... .
Les nombres de Fibonacci apparaissent souvent de manière inattendue en mathématiques, à tel point qu'il existe une revue entière dédiée à leur étude, le Fibonacci Quarterly. Les applications des nombres de Fibonacci incluent des algorithmes informatiques tels que la technique de recherche de Fibonacci et la structure de données en tas de Fibonacci, ainsi que des graphiques appelés cubes de Fibonacci utilisés pour interconnecter des systèmes parallèles et distribués. Ils apparaissent également dans des contextes biologiques, tels que la ramification des arbres, la phyllotaxie (la disposition des feuilles sur une tige), les pousses de fruits d'un ananas, la floraison d'un artichaut, une fougère enroulée et la disposition des bractées d'une pomme de pin.
Origines
La séquence de Fibonacci apparaît dans les mathématiques indiennes, en lien avec la prosodie sanskrite. Dans la tradition sanskrite de la prosodie, il y avait un intérêt à énumérer tous les modèles de syllabes longues (L) qui représentent 2 unités de durée et de syllabes courtes (S) qui représentent 1 unité de durée. Compter les différents modèles de L et S d'une durée donnée donne les nombres de Fibonacci : le nombre de modèles qui sont longs de m syllabes courtes est le nombre de Fibonacci Fm + 1.
Susantha Goonatilake écrit que le développement de la séquence de Fibonacci « est attribué en partie à Pingala (200 avant JC), étant plus tard associé à Virahanka (vers 700 après JC), Gopāla (vers 1135) et Hemachandra (vers 1150) ». Parmanand Singh cite la formule énigmatique de Pingala misrau cha (« les deux sont mélangés ») et cite des chercheurs qui l'interprètent dans son contexte comme disant que les cas pour m battements (Fm+1) sont obtenus en ajoutant un [S] aux cas Fm et [ L] aux cas Fm−1. Il date de Pingala avant 450 avant JC.
Cependant, l'exposé le plus clair de la séquence apparaît dans l'œuvre de Virahanka (vers 700 après JC), dont le propre travail est perdu, mais est disponible dans une citation de Gopala (vers 1135) :
Variations de deux mètres antérieurs [est la variation]... Par exemple, pour [un mètre de longueur] quatre, les variations de mètres de deux [et] trois étant mélangées, cinq se produisent. [établit les exemples 8, 13, 21]... De cette façon, le processus doit être suivi dans tous les mātrā-vṛttas [combinaisons prosodiques].
La séquence est également discutée par Gopala (avant 1135 après JC) et par l'érudit jaïn Hemachandra (vers 1150).
En dehors de l'Inde, la séquence de Fibonacci apparaît pour la première fois dans le livre Liber Abaci (1202) de Fibonacci. Fibonacci considère la croissance d'une population de lapins idéalisée (biologiquement irréaliste), en supposant que : un couple de lapins nouveau-nés, un mâle et une femelle, est mis dans un champ ; les lapins sont capables de s'accoupler à l'âge d'un mois afin qu'à la fin de son deuxième mois, une femelle puisse produire un autre couple de lapins ; les lapins ne meurent jamais et un couple accouplé produit toujours un nouveau couple (un mâle, une femelle) chaque mois à partir du deuxième mois. Le casse-tête posé par Fibonacci était le suivant : combien de paires y aura-t-il en un an ?
* A la fin du premier mois, ils s'accouplent, mais il n'y a toujours qu'un seul couple.
* A la fin du deuxième mois la femelle produit un nouveau couple, il y a donc maintenant 2 couples de lapins dans le champ.
* A la fin du troisième mois, la femelle originelle produit un deuxième couple, soit 3 couples en tout sur le terrain.
* A la fin du quatrième mois, la femelle d'origine a produit encore un nouveau couple, la femelle née il y a deux mois produit également son premier couple, soit 5 couples.
À la fin du nième mois, le nombre de couples de lapins est égal au nombre de nouveaux couples (qui est le nombre de couples au mois n − 2) plus le nombre de couples vivants le mois dernier (n − 1). C'est le nième nombre de Fibonacci.
Le nom « séquence de Fibonacci » a été utilisé pour la première fois par le théoricien des nombres du XIXe siècle, Édouard Lucas.
Liste des numéros de Fibonacci
Les 21 premiers nombres de Fibonacci Fn pour n = 0, 1, 2, …, 20 sont : les 300 premiers Fn sont-ils pris en compte en nombres premiers et en liens vers des tableaux plus complets.
La séquence peut également être étendue à un indice n négatif en utilisant la relation de récurrence réorganisée
F_{n-2} = F_n - F_{n-1},
ce qui donne la séquence de nombres "negafibonacci" satisfaisant
F_{-n} = (-1)^{n+1} F_n.
Ainsi la séquence bidirectionnelle est
Utilisation en mathématiques
Les nombres de Fibonacci apparaissent dans les sommes des diagonales « peu profondes » du triangle de Pascal (voir Coefficient binomial).
F_{n}\sum_{k
0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \tbinom {n-k-1} k
Ces chiffres donnent également la solution à certains problèmes énumératifs. Le problème le plus courant est celui de compter le nombre de compositions de 1 et de 2 qui totalisent un total n donné : il existe des façons Fn+1 de le faire.
Par exemple, si n 5, alors Fn+1
F6 = 8 compte les huit compositions :
1+1+1+1+1 1+1+1+2
 1+1+2+1 1+2+1+1
2+1+1+1 2+2+1
 2+1+2 = 1+2+2,
qui totalisent n 5
6−1.
Les nombres de Fibonacci peuvent être trouvés de différentes manières parmi l’ensemble des chaînes binaires, ou de manière équivalente, parmi les sous-ensembles d’un ensemble donné.
* Le nombre de chaînes binaires de longueur n sans 1 consécutifs est le nombre de Fibonacci Fn+2. Par exemple, sur les 16 chaînes binaires de longueur 4, il y a F6 8 sans 1 consécutifs – ce sont 0000, 0001, 0010, 0100, 0101, 1000, 1001 et 1010. Par symétrie, le nombre de chaînes de longueur n sans les 0 consécutifs sont également Fn+2. De manière équivalente, Fn+2 est le nombre de sous-ensembles S ⊂ {1,...,n} sans entiers consécutifs : {i, i+1} ⊄ S pour chaque i. L'énoncé symétrique est : Fn+2 est le nombre de sous-ensembles S ⊂ {1,...,n} sans deux entiers sautés consécutifs : c'est-à-dire S
{a1 k} avec ai+1 ≤ ai + 2.
* Le nombre de chaînes binaires de longueur n sans nombre impair de 1 consécutifs est le nombre de Fibonacci Fn+1. Par exemple, sur les 16 chaînes binaires de longueur 4, il y a F5 = 5 sans nombre impair de 1 consécutifs – ils sont 0000, 0011, 0110, 1100, 1111. De manière équivalente, le nombre de sous-ensembles S ⊂ {1,. ..,n} sans un nombre impair d’entiers consécutifs est Fn+1.
* Le nombre de chaînes binaires de longueur n sans nombre pair de 0 ou de 1 consécutifs est 2Fn. Par exemple, sur les 16 chaînes binaires de longueur 4, il y a 2F4 = 6 sans un nombre pair de 0 ou de 1 consécutifs – il s'agit de 0001, 0111, 0101, 1000, 1010, 1110. Il existe une déclaration équivalente concernant les sous-ensembles.
Relation avec le nombre d'or
Expression de forme fermée
Comme toute séquence définie par une récurrence linéaire à coefficients constants, les nombres de Fibonacci ont une solution de forme fermée. On l'appelle désormais « formule de Binet », même si elle était déjà connue par Abraham de Moivre :
F_n \frac{\varphi^n-\psi^n}{\varphi-\psi}
 \frac{\varphi^n-\psi^n}{\sqrt 5}
où
\varphi = \frac{1 + \sqrt{5}}{2} \environ 1,61803\,39887\cdots\,
est le nombre d'or (), et
\psi \frac{1 - \sqrt{5}}{2}
1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\cdots
Puisque \psi = -\frac{1}{\varphi}, cette formule peut aussi s'écrire
F_n \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}
\frac{\varphi^n-(-\varphi)^{-n}}{2 \varphi - 1}
Pour voir cela, notons que φ et ψ sont tous deux des solutions des équations
x^2 x + 1,\, x^n
x^{n-1} + x^{n-2},\,
donc les puissances de φ et ψ satisfont la récursion de Fibonacci. Autrement dit,
\varphi^n = \varphi^{n-1} + \varphi^{n-2}\,
et
\psi^n = \psi^{n-1} + \psi^{n-2}\, .
Il s'ensuit que pour toutes valeurs a et b, la séquence définie par
U_n=a \varphi^n + b \psi^n\,
satisfait la même récurrence
U_na \varphi^{n-1} + b \psi^{n-1} + a \varphi^{n-2} + b \psi^{n-2}
U_{n-1} + U_{n-2}.\,
Si a et b sont choisis pour que U0  0 et U1
1 alors la séquence résultante Un doit être la séquence de Fibonacci. Cela revient à exiger que a et b satisfassent le système d’équations :
\left\{\begin{array}{l} a + b 0\\ \varphi a + \psi b
 1\end{array}\right.
qui a une solution
une \frac{1}{\varphi-\psi}
 \frac{1}{\sqrt 5},\, b = -a
produire la formule requise.
En prenant U0 et U1 comme variables, une solution plus générale peut être trouvée pour toutes les valeurs de départ :
 U_n=a\varphi^n+b\psi^n
où
a=\frac{U_1-U_0\psi}{\sqrt 5}
 b=\frac{U_0\varphi-U_1}{\sqrt 5}.
Calcul par arrondi
Depuis
\left|\frac{\psi^{n}}{\sqrt 5}\right|
pour tout n ≥ 0, le nombre Fn est l'entier le plus proche de \frac{\varphi^n}{\sqrt 5}. Par conséquent, il peut être trouvé par arrondi, c’est-à-dire en utilisant la fonction entière la plus proche :
F_n=\left[\frac{\varphi^n}{\sqrt 5}\right],\ n \geq 0,
ou en termes de fonction du sol :
F_n=\left\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\right\rfloor,\ n \geq 0.
De même, si l’on sait déjà que le nombre F > 1 est un nombre de Fibonacci, on peut déterminer son indice dans la séquence par
n(F) = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2}\right) \bigg\rfloor
Limite des quotients consécutifs
Johannes Kepler a observé que le rapport des nombres de Fibonacci consécutifs converge. Il a écrit que "comme 5 est à 8, ainsi est 8 à 13, pratiquement, et comme 8 est à 13, ainsi est presque 13 à 21", et a conclu que la limite se rapproche du nombre d'or \varphi.
\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi
Cette convergence est valable quelles que soient les valeurs de départ, à l'exclusion de 0, 0. Cela peut être dérivé de la formule de Binet.
Par exemple, les valeurs initiales 3 et 2 génèrent la séquence 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, …, etc. Le rapport des termes consécutifs dans cette séquence montre la même convergence vers le nombre d’or.
Une autre conséquence est que la limite du rapport de deux nombres de Fibonacci compensés par un écart fini particulier d'indice correspond au nombre d'or élevé par cet écart. Ou, en d'autres termes :
\lim_{n\to\infty}\frac{F_{n+\alpha}}{F_n}=\varphi^\alpha
Décomposition des puissances du nombre d'or
Puisque le nombre d'or satisfait l'équation
\varphi^2 = \varphi + 1,\,
cette expression peut être utilisée pour décomposer les puissances supérieures \varphi^n en fonction linéaire des puissances inférieures, qui à leur tour peuvent être décomposées jusqu'à une combinaison linéaire de \varphi et 1. Les relations de récurrence qui en résultent donnent des nombres de Fibonacci comme coefficients linéaires :
\varphi^n = F_n\varphi + F_{n-1}.
Cette équation peut être prouvée par récurrence sur n.
Cette expression est également vraie pour n n est étendu aux entiers négatifs en utilisant la règle de Fibonacci F_n = F_{n-1} + F_{n-2}.
Forme matricielle
Un système bidimensionnel d'équations aux différences linéaires qui décrit la séquence de Fibonacci est
\begin{aligner}
 {F_{k+2} \choisir F_{k+1}} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} {F_{k+1} \choisir F_{k}} \\
 \vec F_{k+1} &= \mathbf{A} \vec F_{k} ~,
\fin{aligner}
ce qui donne \vec F_{n} \mathbf{A}^n \vec F_{0}. Comme les valeurs propres de la matrice A sont \varphi
~\scriptstyle\frac12(1+\sqrt5)\,\! et -\varphi^{-1}~\scriptstyle\frac12(1-\sqrt5), pour les vecteurs propres respectifs \vec \mu
\scriptstyle{\varphi \choose 1} et \vec\nu=\scriptstyle{-\varphi^{-1} \choose 1},
et la valeur initiale \scriptstyle\vec F_0{1 \choose 0}
\frac{1}{\sqrt{5}}\vec{\mu}-\frac{1}{\sqrt{5}}\vec{\nu}, le ème terme est
\begin{align}\vec F_{n} &= \frac{1}{\sqrt{5}}A^n\vec\mu-\frac{1}{\sqrt{5}}A^n\vec \nu \\
&= \frac{1}{\sqrt{5}}\varphi^n\vec\mu-\frac{1}{\sqrt{5}}(-\varphi)^{-n}\vec\nu~ \\
& =\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n{\varphi \choose 1}-\cfrac{1 }{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n{-\varphi^{-1}\choose 1}~,
\fin{aligner}
d'où le ème élément de la série de Fibonacci
comme fonction analytique de se lit maintenant directement :
F_{n} = \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt {5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n~.
De manière équivalente, le même calcul est effectué par diagonalisation de A grâce à l'utilisation de sa décomposition propre :
\begin{align} A & = S\Lambda S^{-1} ,\\
A^n & = S\Lambda^n S^{-1},
\fin{aligner}
où \Lambda\begin{pmatrix} \varphi & 0 \\ 0 & -\varphi^{-1} \end{pmatrix} et S
\begin{pmatrix} \varphi & -\varphi^{-1} \\ 1 & 1 \end{pmatrix} .
L'expression fermée du ème élément de la série de Fibonacci est donc donnée par
\begin{align} {F_{n+1} \choisissez F_{n}} & = A^{n} {F_1 \choisissez F_0} \\
& = S \Lambda^n S^{-1} {F_1 \choose F_0} \\
 & = S \begin{pmatrix} \varphi^n & 0 \\ 0 & (-\varphi)^{-n} \end{pmatrix} S^{-1} {F_1 \choose F_0} \\
 & = \begin{pmatrix} \varphi & -\varphi^{-1} \\ 1 & 1 \end{pmatrix}
\begin{pmatrix} \varphi^n & 0 \\ 0 & (-\varphi)^{-n} \end{pmatrix}
     \frac{1}{\sqrt{5}}\begin{pmatrix} 1 & \varphi^{-1} \\ -1 & \varphi \end{pmatrix} {1 \choose 0},
\fin{aligner}
ce qui donne encore une fois
F_{n} = \cfrac{\varphi^n-(-\varphi)^{-n}}{\sqrt{5}}.
La matrice A a un déterminant de −1, et c'est donc une matrice unimodulaire 2 × 2.
Cette propriété peut être comprise en termes de représentation de fraction continue pour le nombre d'or :
\varphi = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \;\;\ddots\,}}}
Les nombres de Fibonacci apparaissent comme le rapport des convergents successifs de la fraction continue pour , et la matrice formée à partir des convergents successifs de toute fraction continue a un déterminant de +1 ou −1. La représentation matricielle donne l'expression fermée suivante pour les nombres de Fibonacci :
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.
Prendre le déterminant des deux côtés de cette équation donne l'identité de Cassini,
(-1)^n = F_{n+1}F_{n-1} - F_n^2\,.
De plus, puisque pour toute matrice carrée A, les identités suivantes peuvent être dérivées (elles sont obtenues à partir de deux coefficients différents du produit matriciel, et on peut facilement déduire le second du premier en passant par ),
\begin{aligner}
 {F_m}{F_n} + {F_{m-1}}{F_{n-1}} &= F_{m+n-1},\\
F_{m} F_{n+1} + F_{m-1} F_n &= F_{m+n} .
\fin{aligner}
En particulier, avec m = n,
\begin{aligner}
 F_{2n-1} &= F_n^2 + F_{n-1}^2\\
 F_{2n} &= (F_{n-1}+F_{n+1})F_n\\
&= (2F_{n-1}+F_n)F_n .
\fin{aligner}
Ces deux dernières identités permettent de calculer les nombres de Fibonacci de manière récursive dans des opérations arithmétiques et en temps, où est le temps de multiplication de deux nombres de n chiffres. Cela correspond au temps de calcul du nième nombre de Fibonacci à partir de la formule matricielle fermée, mais avec moins d'étapes redondantes si l'on évite de recalculer un nombre de Fibonacci déjà calculé (récursion avec mémorisation).
Reconnaître les nombres de Fibonacci
La question peut se poser de savoir si un entier positif x est un nombre de Fibonacci. Cela est vrai si et seulement si l'un ou les deux de 5x^2+4 ou 5x^2-4 est un carré parfait. En effet, la formule de Binet ci-dessus peut être réorganisée pour donner
n = \log_{\varphi}\left(\frac{F_n\sqrt{5} + \sqrt{5F_n^2 \pm 4}}{2}\right),
ce qui permet de trouver la position dans la séquence d'un nombre de Fibonacci donné.
Cette formule doit renvoyer un entier pour tout n, donc l'expression radicale doit être un entier (sinon le logarithme ne renvoie même pas de nombre rationnel).
Identités combinatoires
La plupart des identités impliquant des nombres de Fibonacci peuvent être prouvées à l'aide d'arguments combinatoires en utilisant le fait que Fn peut être interprété comme le nombre de séquences de 1 et de 2 dont la somme est n − 1. Cela peut être considéré comme la définition de Fn, avec la convention selon laquelle F0 0, ce qui signifie qu'aucune somme ne vaut −1, et que F1
1, ce qui signifie que la somme vide "s'additionne" à 0. Ici, l'ordre de la somme compte. Par exemple, 1 + 2 et 2 + 1 sont considérés comme deux sommes différentes.
Par exemple, la relation de récurrence
F_{n} = F_{n-1} + F_{n-2},\,
ou en mots, le nième nombre de Fibonacci est la somme des deux nombres de Fibonacci précédents, peut être affiché en divisant les sommes Fn de 1 et de 2 qui s'ajoutent à n − 1 en deux groupes qui ne se chevauchent pas. Un groupe contient les sommes dont le premier terme est 1 et l'autre les sommes dont le premier terme est 2. Dans le premier groupe, les termes restants s'ajoutent à n − 2, il a donc des sommes Fn-1, et dans le deuxième groupe les termes restants ajouter à n − 3, donc il y a des sommes Fn− 2. Il y a donc un total de sommes Fn−1 + Fn−2, ce qui montre que cela est égal à Fn.
De même, on peut montrer que la somme des premiers nombres de Fibonacci jusqu'au nième est égale au (n + 2)-ième nombre de Fibonacci moins 1. En symboles :
\sum_{i1}^n F_i
 F_{n+2} - 1
Cela se fait en divisant les sommes s'ajoutant à n + 1 d'une manière différente, cette fois par l'emplacement des 2 premiers. Plus précisément, le premier groupe est constitué des sommes qui commencent par 2, le deuxième groupe celles qui commencent par 1 + 2 , le troisième 1 + 1 + 2, et ainsi de suite, jusqu'au dernier groupe, qui consiste en la somme unique où seuls les 1 sont utilisés. Le nombre de sommes dans le premier groupe est F(n), F(n − 1) dans le deuxième groupe, et ainsi de suite, avec 1 somme dans le dernier groupe. Le nombre total de sommes est donc F(n) + F(n − 1) + ... + F(1) + 1 et donc cette quantité est égale à F(n + 2).
Un argument similaire, regroupant les sommes selon la position du premier 1 plutôt que du premier 2, donne deux autres identités :
\sum_{i0}^{n-1} F_{2i+1}
 F_{2n}
et
\sum_{i1}^{n} F_{2i}
 F_{2n+1}-1.
En mots, la somme des premiers nombres de Fibonacci d'indice impair jusqu'à F2n−1 est le (2n)ème nombre de Fibonacci, et la somme des premiers nombres de Fibonacci d'indice pair jusqu'à F2n est le (2n + 1)ème nombre de Fibonacci. nombre moins 1.
Une autre astuce peut être utilisée pour prouver
\sum_{i1}^n {F_i}^2
F_{n} F_{n+1},
ou en mots, la somme des carrés des premiers nombres de Fibonacci jusqu'à Fn est le produit du nième et du (n + 1)ième nombres de Fibonacci. Dans ce cas, notez que le rectangle de Fibonacci de taille Fn par F(n + 1) peut être décomposé en carrés de taille Fn, Fn−1, et ainsi de suite jusqu'à F1 = 1, d'où l'identité découle en comparant les aires.
Autres identités
De nombreuses autres identités peuvent être dérivées en utilisant diverses méthodes. Certains des plus remarquables sont :
Cassini et les identités catalanes
L'identité de Cassini indique que
F_n^2 - F_{n+1}F_{n-1} = (-1)^{n-1}
L'identité catalane est une généralisation :
F_n^2 - F_{n+r}F_{n-r} = (-1)^{n-r}F_r^2
L'identité de d'Ocagne
F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}
F_{2n} F_{n+1}^2 - F_{n-1}^2
F_n \left (F_{n+1}+F_{n-1} \right ) = F_nL_n
où Ln est le nième nombre de Lucas. La dernière est une identité pour doubler n ; d'autres identités de ce type sont
F_{3n} 2F_n^3 + 3F_n F_{n+1} F_{n-1}
5F_n^3 + 3 (-1)^n F_n
par l'identité de Cassini.
F_{3n+1} = F_{n+1}^3 + 3 F_{n+1}F_n^2 - F_n^3
F_{3n+2} = F_{n+1}^3 + 3 F_{n+1}^2F_n + F_n^3
F_{4n} = 4F_nF_{n+1} \left (F_{n+1}^2 + 2F_n^2 \right ) - 3F_n^2 \left (F_n^2 + 2F_{n+1}^2 \right )
Ceux-ci peuvent être trouvés expérimentalement en utilisant la réduction de réseau et sont utiles pour mettre en place le tamis de champ numérique spécial pour factoriser un nombre de Fibonacci.
Plus généralement,
F_{kn+c} \sum_{i
0}^k {k\choisir i} F_{c-i} F_n^i F_{n+1}^{k-i}.
En mettant cette formule, on obtient à nouveau les formules de la fin de la section ci-dessus Formulaire matriciel.
Série de puissance
La fonction génératrice de la séquence de Fibonacci est la série entière
s(x)\somme_{k
0}^{\infty} F_k x^k.
Cette série est convergente pour |x| et sa somme a une forme fermée simple :
s(x)=\frac{x}{1-x-x^2}
Cela peut être prouvé en utilisant la récurrence de Fibonacci pour développer chaque coefficient dans la somme infinie :
\begin{aligner}
s(x) &\somme_{k
0}^{\infty} F_k x^k \\
       &F_0 + F_1x + \sum_{k
2}^{\infty} \left( F_{k-1} + F_{k-2} \right) x^k \\
       &x + \somme_{k
2}^{\infty} F_{k-1} x^k + \sum_{k=2}^{\infty} F_{k-2} x^k \\
&x + x\somme_{k
0}^{\infty} F_k x^k + x^2\sum_{k=0}^{\infty} F_k x^k \\
       &= x + x s(x) + x^2 s(x).
\fin{aligner}
Résoudre l'équation
s(x)=x+xs(x)+x^2s(x)
pour s(x) donne la forme fermée ci-dessus.
Si est l’inverse d’un entier k supérieur à 1, la forme fermée de la série devient
\sum_{n0}^\infty\,\frac{F_n}{k^{n}}\,
\,\frac{k}{k^{2}-k-1}.
En particulier,
\sum_{n 1}^{\infty}{\frac {F_n}{10^{m(n + 1)}}}
\frac {1}{10^{2m} - 10^{m} - 1}
pour tous les entiers positifs m.
Certains livres d'énigmes mathématiques présentent comme curieuse la valeur particulière qui vient de m1, qui est \frac{s(\frac{1}{10})}{10}
\frac{1}{89} .011235\ldots. De même, m
2 donne \frac{s(\frac{1}{100})}{100}\frac{1}{9899}
 .00010102030508132134\ldots.
Sommes réciproques
Les sommes infinies sur les nombres de Fibonacci réciproques peuvent parfois être évaluées en termes de fonctions thêta. Par exemple, nous pouvons écrire la somme de chaque nombre de Fibonacci réciproque impair sous la forme
\sum_{k0}^\infty \frac{1}{F_{2k+1}}
\frac{\sqrt{5}}{4}\vartheta_2^2 \left(0, \frac{3-\sqrt 5}{2}\right) ,
et la somme des carrés des nombres de Fibonacci réciproques comme
\sum_{k1}^\infty \frac{1}{F_k^2}
\frac{5}{24} \left(\vartheta_2^4\left(0, \frac{3-\sqrt 5}{2}\right) - \vartheta_4^4\left(0, \frac{3- \sqrt 5}{2}\right) + 1 \right).
Si on ajoute 1 à chaque nombre de Fibonacci dans la première somme, on obtient aussi la forme fermée
\sum_{k0}^\infty \frac{1}{1+F_{2k+1}}
\frac{\sqrt{5}}{2},
et il existe une somme imbriquée de carrés de nombres de Fibonacci donnant l'inverse du nombre d'or,
\sum_{k1}^\infty \frac{(-1)^{k+1}}{\sum_{j
1}^k {F_{j}}^2} = \frac{\sqrt{5}-1}{2}.
Pas de formule fermée pour la constante de Fibonacci réciproque
\psi \sum_{k
1}^{\infty} \frac{1}{F_k} = 3.359885666243 \dots
est connu, mais ce chiffre a été prouvé irrationnel par Richard André-Jeannin.
La série Millin donne l'identité
\sum_{n 0}^{\infty} \frac{1}{F_{2n}} \frac{7 - \sqrt{5}}{2}\,,
qui découle de la forme fermée pour ses sommes partielles lorsque N tend vers l'infini :
\sum_{n0}^N \frac{1}{F_{2^n}}
 3 - \frac{F_{2^N-1}}{F_{2^N}}.
Nombres premiers et divisibilité
Propriétés de divisibilité
Chaque 3ème nombre de la séquence est pair et plus généralement, chaque kème nombre de la séquence est un multiple de Fk. Ainsi, la séquence de Fibonacci est un exemple de séquence de divisibilité. En fait, la suite de Fibonacci satisfait la propriété de divisibilité la plus forte
\gcd(F_m,F_n) = F_{\gcd(m,n)}.
Trois nombres de Fibonacci consécutifs sont premiers entre eux par paire, ce qui signifie que, pour chaque n,
pgcd(Fn, Fn+1) pgcd(Fn, Fn+2)
 pgcd(Fn+1, Fn+2) = 1.
Tout nombre premier p divise un nombre de Fibonacci qui peut être déterminé par la valeur de p modulo 5. Si p est congru à 1 ou 4 (mod 5), alors p divise Fp − 1, et si p est congru à 2 ou 3 ( mod 5), alors, p divise Fp + 1. Le cas restant est que p = 5, et dans ce cas p divise Fp. Ces cas peuvent être regroupés en une seule formule, à l'aide du symbole Legendre :. Williams qualifie cette propriété de « bien connue ».
p \mid F_{p-\left(\frac{5}{p}\right)}.
Test de primalité
La formule ci-dessus peut être utilisée comme test de primalité dans le sens où si
n \mid F_{n-\left(\frac{5}{n}\right)}, où le symbole de Legendre a été remplacé par le symbole de Jacobi, alors c'est la preuve que n est premier, et s'il échoue tenez, alors n n'est certainement pas un nombre premier. Si n est composite et satisfait à la formule, alors n est un pseudopremier de Fibonacci.
Lorsque m est grand (disons un nombre de 500 bits), nous pouvons alors calculer efficacement Fm (mod n) en utilisant la forme matricielle. Ainsi
\begin{pmatrix} F_{m+1} & F_m \\ F_m & F_{m-1} \end{pmatrix} ≡ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m ( mod n).
Ici, la puissance matricielle Am est calculée à l'aide de l'exponentiation modulaire, qui peut être adaptée aux matrices - exponentiation modulaire pour les matrices
Fibonacci prime
Un nombre premier de Fibonacci est un nombre de Fibonacci premier. Les premiers sont :
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, … .
Des nombres premiers de Fibonacci avec des milliers de chiffres ont été trouvés, mais on ne sait pas s'il y en a une infinité.
Fkn est divisible par Fn, donc, mis à part F4 = 3, tout nombre premier de Fibonacci doit avoir un indice premier. Comme il existe des séries arbitrairement longues de nombres composés, il existe donc également des séries arbitrairement longues de nombres composites de Fibonacci.
Aucun nombre de Fibonacci supérieur à F6 = 8 n’est supérieur ou inférieur d’un à un nombre premier.
Le seul non trivial
Le nombre carré de Fibonacci est 144. Attila Pethő a prouvé en 2001 qu'il n'existe qu'un nombre fini de nombres de Fibonacci puissance parfaite. En 2006, Y. Bugeaud, M. Mignotte et S. Siksek ont ​​prouvé que 8 et 144 sont les seules puissances parfaites non triviales.
Diviseurs premiers des nombres de Fibonacci
À l'exception de 1, 8 et 144 (F1 = F2, F6 et F12), chaque nombre de Fibonacci a un facteur premier qui n'est pas un facteur d'un nombre de Fibonacci plus petit (théorème de Carmichael). En conséquence, 8 et 144 (F6 et F12) sont les seuls nombres de Fibonacci qui sont le produit d'autres nombres de Fibonacci.
La divisibilité des nombres de Fibonacci par un p premier est liée au symbole de Legendre \left(\tfrac{p}{5}\right) qui s'évalue comme suit :
\left(\frac{p}{5}\right) \begin{cases} 0 & \textrm{if}\;p
5\\ 1 &\textrm{if}\;p \equiv \pm1 \pmod 5\\ -1 &\textrm{if}\;p \equiv \pm2 \pmod 5.\end{cases}
Si p est un nombre premier alors
 F_p \equiv \left(\frac{p}{5}\right) \pmod p \quad \text{and}\quad F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmodp.
Par exemple,
\begin{aligner}
(\tfrac{2}{5}) &-1, &F_3 &
 2, &F_2&=1, \\
(\tfrac{3}{5}) &-1, &F_4 &
 3,&F_3&=2, \\
(\tfrac{5}{5}) &0, &F_5 &
5, \\
(\tfrac{7}{5}) &-1, &F_8 &
 21,&F_7&=13, \\
(\tfrac{11}{5})& +1, &F_{10}&
 55, &F_{11}&=89.
\fin{aligner}
On ne sait pas s’il existe un premier p tel que
F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod{p^2}.
De tels nombres premiers (s'il y en a) seraient appelés nombres premiers Mur – Soleil – Soleil.
De plus, si p ≠ 5 est un nombre premier impair alors :
5F^2_{\frac{p \pm 1}{2}} \equiv \begin{cases}
\tfrac{1}{2} \left (5\left(\frac{p}{5}\right)\pm 5 \right ) \pmod p & \textrm{if}\;p \equiv 1 \pmod 4 \\
\tfrac{1}{2} \left (5\left(\frac{p}{5}\right)\mp 3 \right ) \pmod p & \textrm{if}\;p \equiv 3 \pmod 4 .
\fin{cas}
Exemple 1. p = 7, dans ce cas p ≡ 3 (mod 4) et on a :
(\tfrac{7}{5}) -1 : \qquad \tfrac{1}{2}\left (5(\tfrac{7}{5})+3 \right )
-1, \quad \tfrac{1}{2} \left (5(\tfrac{7}{5})-3 \right )=-4.
F_32 \text{ et } F_4
3.
5F_3^220\equiv -1 \pmod {7}\;\;\text{ et }\;\;5F_4^2
45\équiv -4 \pmod {7}
Exemple 2. p = 11, dans ce cas p ≡ 3 (mod 4) et on a :
(\tfrac{11}{5}) +1 : \qquad \tfrac{1}{2}\left (5(\tfrac{11}{5})+3 \right )
4, \quad \tfrac{1}{2} \left (5(\tfrac{11}{5})- 3 \right )=1.
F_55 \text{ et } F_6
8.
5F_5^2125\equiv 4 \pmod {11} \;\;\text{ et }\;\;5F_6^2
320\équiv 1 \pmod {11}
Exemple 3. p = 13, dans ce cas p ≡ 1 (mod 4) et on a :
(\tfrac{13}{5}) -1 : \qquad \tfrac{1}{2}\left (5(\tfrac{13}{5})-5 \right )
-5, \quad \tfrac{1}{2}\left (5(\tfrac{13}{5})+ 5 \right )=0.
F_68 \text{ et } F_7
13.
5F_6^2320\equiv -5 \pmod {13} \;\;\text{ et }\;\;5F_7^2
845\équiv 0 \pmod {13}
Exemple 4. p = 29, dans ce cas p ≡ 1 (mod 4) et on a :
(\tfrac{29}{5}) +1 : \qquad \tfrac{1}{2}\left (5(\tfrac{29}{5})-5 \right )
0, \quad \tfrac{1}{2}\left (5(\tfrac{29}{5})+5 \right )=5.
F_{14}377 \text{ et } F_{15}
610.
5F_{14}^2710645\equiv 0 \pmod {29} \;\;\text{ et }\;\;5F_{15}^2
1860500\équiv 5 \pmod {29}
Pour n impair, tous les diviseurs premiers impairs de Fn sont congrus à 1 modulo 4, ce qui implique que tous les diviseurs impairs de Fn (en tant que produits de diviseurs premiers impairs) sont congrus à 1 modulo 4.
Par exemple,
F_1 1, F_3
2, F_5 5, F_7
 13, F_9 34
 2 \cdot 17, F_{11} 89, F_{13}
233, F_{15} 610
 2 \cdot 5 \cdot 61.
Tous les facteurs connus des nombres de Fibonacci F(i) pour tout i rassemble tous les facteurs connus de F(i) avec i rassemble tous les facteurs connus de F(i) avec 10000
Périodicité modulo n
Si les membres de la séquence de Fibonacci sont pris mod n, la séquence résultante est périodique avec un point au plus 6n. Les durées des périodes pour différents n forment ce que l'on appelle les périodes de Pisano. Déterminer une formule générale pour les périodes de Pisano est un problème ouvert, qui inclut comme sous-problème une instance particulière du problème de trouver l'ordre multiplicatif d'un entier modulaire ou d'un élément dans un corps fini. Cependant, pour tout n particulier, la période de Pisano peut être considérée comme un exemple de détection de cycle.
Triangles rectangles
En commençant par 5, un nombre de Fibonacci sur deux est la longueur de l'hypoténuse d'un triangle rectangle à côtés entiers, ou en d'autres termes, le plus grand nombre d'un triplet de Pythagore. La longueur de la branche la plus longue de ce triangle est égale à la somme des trois côtés du triangle précédent dans cette série de triangles, et la branche la plus courte est égale à la différence entre le nombre de Fibonacci contourné précédent et la branche la plus courte du nombre précédent. Triangle.
Le premier triangle de cette série a des côtés de longueur 5, 4 et 3. En sautant 8, le triangle suivant a des côtés de longueur 13, 12 (5 + 4 + 3) et 5 (8 − 3). En sautant 21, le triangle suivant a des côtés de longueur 34, 30 (13 + 12 + 5) et 16 (21 − 5). Cette série se poursuit indéfiniment. Les côtés du triangle a, b, c peuvent être calculés directement :
\begin{aligner}
a_n & = F_{2n-1} \\[4pt]
b_n & = 2 F_n F_{n-1} \\[4pt]
c_n & = F_n^2 - F_{n-1}^2.
\fin{aligner}
Ces formules satisfont a_n ^2 = b_n ^2 + c_n ^2 pour tout n, mais elles ne représentent les côtés du triangle que lorsque n > 2.
Quatre nombres de Fibonacci consécutifs Fn, Fn+1, Fn+2 et Fn+3 peuvent également être utilisés pour générer un triplet de Pythagore d'une manière différente :
une F_n F_{n+3} \, ; \,b
 2 F_{n+1} F_{n+2} \, ; \, c F_{n+1}^2 + F_{n+2}^2 \, ; \, a^2 + b^2
 c^2 \,.
Exemple 1 : soit les nombres de Fibonacci 1, 2, 3 et 5. Alors :
\begin{aligner}
une 1 \fois 5 &
5 \\
b 2 \ fois 2 \ fois 3 &
 12 \\
c 2^2 + 3^2 & 
 13 \\
5^2 + 12^2 & = 13^2
\fin{aligner}
Ordre de grandeur
Puisque Fn est asymptotique à \varphi^n/\sqrt5, le nombre de chiffres dans Fn est asymptotique à n\,\log_{10}\varphi\approx0.2090\,n. En conséquence, pour tout entier d > 1, il existe 4 ou 5 nombres de Fibonacci avec d chiffres décimaux.
Plus généralement, dans la représentation en base b, le nombre de chiffres dans Fn est asymptotique à n\,\log_b\varphi.
Applications
Les nombres de Fibonacci sont importants dans l'analyse informatique de l'algorithme d'Euclide pour déterminer le plus grand diviseur commun de deux entiers : l'entrée du pire cas pour cet algorithme est une paire de nombres de Fibonacci consécutifs.
Brasch et coll. 2012 montrent comment une séquence de Fibonacci généralisée peut également être connectée au domaine de l'économie. En particulier, nous montrons comment une séquence de Fibonacci généralisée entre dans la fonction de contrôle de problèmes d'optimisation dynamique à horizon fini avec un état et une variable de contrôle. La procédure est illustrée dans un exemple souvent appelé modèle de croissance économique Brock-Mirman.
Yuri Matiyasevich a pu montrer que les nombres de Fibonacci peuvent être définis par une équation diophantienne, ce qui a conduit à sa solution originale du dixième problème de Hilbert.
Les nombres de Fibonacci sont également un exemple de séquence complète. Cela signifie que chaque entier positif peut être écrit comme une somme de nombres de Fibonacci, où un nombre est utilisé au maximum une fois.
De plus, chaque entier positif peut être écrit de manière unique comme la somme d’un ou plusieurs nombres de Fibonacci distincts de telle sorte que la somme n’inclut pas deux nombres de Fibonacci consécutifs. C'est ce qu'on appelle le théorème de Zeckendorf, et une somme de nombres de Fibonacci qui satisfait à ces conditions est appelée une représentation de Zeckendorf. La représentation de Zeckendorf d'un nombre peut être utilisée pour dériver son codage de Fibonacci.
Les nombres de Fibonacci sont utilisés par certains générateurs de nombres pseudo-aléatoires.
Ils sont également utilisés dans la planification du poker, qui est une étape d'estimation dans les projets de développement de logiciels utilisant la méthodologie Scrum (développement de logiciels).
Les nombres de Fibonacci sont utilisés dans une version polyphasée de l'algorithme de tri par fusion dans lequel une liste non triée est divisée en deux listes dont les longueurs correspondent aux nombres de Fibonacci séquentiels – en divisant la liste de sorte que les deux parties aient des longueurs dans la proportion approximative φ. Une implémentation sur lecteur de bande du tri par fusion polyphasé a été décrite dans The Art of Computer Programming.
Les nombres de Fibonacci apparaissent lors de l'analyse de la structure de données du tas de Fibonacci.
Le cube de Fibonacci est un graphe non orienté avec un nombre de nœuds de Fibonacci qui a été proposé comme topologie de réseau pour le calcul parallèle.