Suite de Fibonacci
Biographie - Croissance d'une colonie de lapins - Mots

Fibonacci est né à Pise vers 1170. Son père, commerçant, s'est installé ensuite dans la ville de Bougie (*) où Leonardo le rejoint.
Fibonacci étudie le commerce et les mathématiques en effectuant de nombreux voyages en Afrique du nord et sur le pourtour de la Méditerranée. Fibonacci prend connaissance des travaux des mathématiciens arabes comme Al Khwarizmi, apprend la numération de position indienne. À l'époque, en Italie, les chiffres romains sont encore utilisés.

L'empereur Frédéric II, accompagné de ses mathématiciens Théodore et Jean de Palerme, s'était arrêté à Pise en 1225 pour rencontrer Fibonacci dont la renommée était grande et organiser un tournoi mathématique. L'une de ces questions était de trouver un rationnel dont le carré augmenté ou diminué de 5 soit encore un carré. Fibonacci donna la solution 41/12. Ceci revient à montrer que 5 est un nombre congruent et à trouver le triangle rectangle rationnel de côtés c=9/6, b=40/6 et a=41/6 d'aire 5.
La suite des nombres congruents est la suite A003273 de N. J. A. Sloane.
Mais évidemment cela n'a rien à voir avec le nombre F(5) = 5 de la suite de Fibonacci.

La publication au 13ème siècle par Léonard de Pise (Fibonacci) d'observations sur la croissance d'une population de lapins a donné comme modèle la suite dite de Fibonacci.

Au début (t=0) on a un couple A de jeunes lapins.
Le mois suivant (t=1) les deux lapins sont adultes, le couple est appelé B.
Évidemment après un second mois (t=2), deux jeunes lapins naissent et on a deux couples B et A.

Résumons : d'un mois au suivant

• chaque A devient B,
• chaque B devient BA.

Les couples sont, successivement, A, B, BA, BAB, BABBA, BABBABAB ... (ce sont les mots de Fibonacci sur l'alphabet {A, B}).
Les nombres de couples de lapins sont 1, 1, 2, 3, 5, 8 ... (nombres de Fibonacci).

La suite (F_n) est définie par la donnée de F₀=0, F₁=1 et par la relation de récurrence F_n=F_n-1+F_n-2 pour n>1.

Les termes successifs de la suite de Fibonacci sont :
F₀=0, F₁=1, F₂=1, F₃=2, F₄=3, F₅=5, F₆=8, F₇=13, F₈=21, F₉=34, F₁₀=55, F₁₁=89, ...

Pour obtenir F_n+1 on ajoute les deux précédents F_n et F_n-1, par exemple F₇=F₆+F₅=13+8=21.

On définit aussi de manière analogue, les mots de Fibonacci sur l'alphabet {0, 1}. (Peu importe l'alphabet, mais celui-ci est souvent utilisé).
Les mots successifs sont donnés dans le tableau ci-dessous, le procédé de construction est indiqué après.

Première méthode :
Pour obtenir M_n+1 on concatène (on accole) M_n et M_n-1, dans cet ordre.
Par exemple M₆ = M₅ M₄ ={10110101} {10110} = {1011010110110 }

On utilise la première méthode, décrite ci-dessus.

Mots et nombres de Fibonacci

Rang n :
Mot Mn :
Nombre Fn :	(c'est le nombre de chiffres 1 dans le mot Mn ci-dessus)

Deuxième méthode :
On peut voir en effet que ce procédé est équivalent, tout en étant plus simple, au morphisme 0 -> 1, 1 -> 10 suivant :
pour obtenir M_n+1 on remplace dans M_n

• tous les 0 par des 1, (les jeunes couples deviennent vieux)
• tous les 1 par des 10, (les vieux couples donnent naissance à autant de couples de jeunes).

Morphisme

Lettres    Images      

Voir aussi la page sur les morphismes, ou on retrouve l'exemple.

Écoutez l'air de musique [Mus.] obtenu en prenant à partir de chaque chiffre du mot de Fibonacci : (1)(0)(1)101011011010110101101101011011010110101... vers la droite, les 7 éléments binaires successifs (1)(0)(1)1010 (0)(1)10101 (1)101011 ... et en convertissant les nombres obtenus 90 53 107(base 10) en notes

Le script fib2midi utilise Awk pour produire le fichier fibonacci.abc au format 'abc' qui a été ensuite transformé en fibonacci.mid au format 'midi' par le programme abc2midi (a package of programs developed by James Allwright for processing ABC music notation files).

L'ensemble S de Clark Kimberling est défini de la manière suivante :

• 1 appartient à S
• Pour chaque élément x de S, les nombres 2x et 4x-1 appartiennent aussi à S
• Aucun autre élément que ceux obtenus ci-dessus n'appartient à S

Cet ensemble S est dit 'auto-générateur' et peut donc se construire par récurrence de la manière suivante.
1 -> 2 et 3 -> 4, 7, 6 et 11 -> 8, 15, 14, 27, 22, 43 -> ...

En rangeant ces éléments dans l'ordre croissant on obtient la suite A052499 de Sloane,

1 2 3 4 6 7 8 11 12 14 15 16 22 23 24 27 28 30 31 32 43 44 46 47 48 ...

Henry Bottomley a remarqué et montré que les rangs des puissances de 2, c'est-à-dire les positions de 1 2 4 8 16 ...2n dans cette suite s'expriment en fonction des nombres de Fibonacci, 2ⁿ a pour rang F(n+3)-2.
Une page du site est consacrée à cet ensemble auto-générateur et on y retrouve la suite de Fibonacci en divers endroits, une démo de la propriété ci-dessus, le nombre d'or, le jeu de Wythoff, les mots infinis, déterminations de morphismes.

En observant attentivement les mots Mn de Fibonacci :
M2 = 10, M3 = 101, M4 = 10110, M5 = 10110101, M6 = 1011010110110, ...
vous pouvez voir qu'en effaçant les deux derniers chiffres on obtient des palindromes (le premier est vide)
P0 = "", P1 = 1, P2 = 101, P3 = 101101, P4 = 10110101101
(Un palindrome 10110101101 est identique au mot retourné. Il peut se lire indifféremment de gauche à droite ou de droite à gauche).
Ces palindromes ont pour longueurs an = Fn+2 - 2.
Cette suite 0, 1, 3, 6, 11, 19, 32, 53, 87, 142, 231 ... est répertoriée par N.J.A. Sloane sous le numéro A001911.
La relation de récurrence définie par a(0)=0, a(1)=1, a(n) = a(n-1) + a(n-2) + 2, permet de retrouver la suite.

Voir la page sur les algorithmes génétiques (La génétique y est utilisée pour retrouver le morphisme 1->10, 0->1, en élevant une population de mots et n'a ici strictement aucun rapport avec l'évolution d'une colonie de lapins).

Quadrillage

Intersections des lignes 1 horizontale et 0 verticale du quadrillage par
la droite D: y = ax de pente irrationnelle a = 

longueur du mot         



    longueur maxi  des chaînes des morphismes (ajuster)