Super Fibo

Vous connaissez probablement la suite de Fibonacci (j’ai écrit au moins deux articles qui en parlent… voir ici). Petit rappel pour ceux qui n’en auraient jamais entendu parlé: il s’agit de la suite (F_n) définie par:

\begin{cases}  F_0 = 0\\  F_1=1\\  F_{n+2}=F_{n+1}+F_n  \end{cases}

Les premiers termes de la suite sont donc  0,1,1,2,3,5,8,13,21… L’idée de cette suite est que chaque terme est la somme des deux termes précédents. On peut donc penser à généraliser cette idée en imaginant une suite dont chaque terme serait, non pas la somme, mais plus généralement une combinaison linéaire des deux termes précédents. La nouvelle suite de Fibonacci obtenue serait définie ainsi:

\begin{cases}  F_0 = 0\\  F_1=1\\  F_{n+2}=a F_{n+1}+ b F_n  \end{cases}

a et b sont deux entiers donnés. Examinons ce que donnerait cette suite pour quelques valeurs de a et b

Ceci est une image gratuitement racoleuse pour illustrer la suite de  Fibonacci.

Ceci est une image gratuitement racoleuse pour illustrer la suite de Fibonacci.

Cas où a = 1 et b = -1

Dans ce cas, on a la relation de récurrence: F_{n+2}=F_{n+1} - F_n. Autrement dit, c’est la suite obtenue en faisant la différence des termes successifs. Les premiers termes de la suite sont donc:

0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1,….

Nous voyons donc que la suite obtenue est périodique. Montrons qu’effectivement, pour tout entier naturel n, F_{n+6}=F_n.

Tout d’abord, nous voyons que F_{n+3} = - F_n car:

F_{n+3} = F_{n+2} - F_{n+1} = (F_{n+1} - F_{n}) - F_{n+1} = - F_{n}

Ainsi,

F_{n+6} = - F_{n+3} = -(-F_n) = F_n

Voilà pour la mise en bouche, passons à d’autres exemples plus croustillants !

Cas où a = 2 et b = -1

La relation de récurrence est alors F_{n+2} = 2F_{n+1} - F_n et donc a priori, rien de bien folichon. Essayons de voir ce que donnent les premières valeurs de la suite:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ……

Ne serait-ce pas la suite de tous les entiers naturels ? Mais oui ! Aller, démontrons-le, c’est-à-dire montrons que F_n = n pour tout n.

■ C’est vrai si n=0 ou n=1 car F_0=0 et F_1=1.
■ On suppose le résultat vrai pour tous les entiers naturels inférieurs ou égaux à n. Il s’agit alors de montrer que F_{n+1 } = n+1. Mais cela est facile car:

F_{n+1} = 2 F_n - F_{n-1} = 2 n - (n-1) = n+1

C’est quand même un résultat assez amusant que de voir qu’on retrouve la suite des entiers naturels à partir d’une généralisation de la suite de Fibonacci. Mais vous en voulez encore plus ? Vous allez en avoir pour votre argent ! (sachant que ce blog est gratuit, je suis pas sûr si cela doit vous rassurer avant de lire la suite).

Cas où a = 3 et b = -2

Dans ce cas, la suite est définie par F_{n+2}= 3F_{n+1} - 2 F_n. Que nous réserve cette suite cette fois ? Eh bien sans plus attendre, voici les premiers termes:

0, 1, 3, 7, 15, 31, 63……

Vous avez deviné ? Eh oui, ce sont les puissances de 2 diminuées de 1 ! Plus précisément, F_n = 2^n - 1, et ces nombres sont parfois appelés nombres de Mersenne. Là encore, on peut faire une démonstration par récurrence:

■ Si n=0, alors F_0 = 0 = 2^0 - 1
■ Soit n un entier naturel. On suppose que pour tout k\leq n, F_k = 2^k - 1. Alors,

F_{n+1} = 3 F_{n} - 2 F_{n-1} = 3 \times (2^{n}-1) - 2\times (2^{n-1}-1)

Donc,

F_{n+1}= 3\times 2^{n } - 3 - 2^n +2 = 2\times 2^{n} - 1 = 2^{n+1} - 1

CQFD ! Quand même, trouver les nombres de Mersenne dans la suite de Fibonacci (généralisée), c’est fort. Mais, nous allons voir qu’il y a encore plus fort

Cas où a = 11 et b = -10

Si je ne vous ai pas achevé avec les exemples précédents, celui-ci risque bien de finir de vous en mettre plein la vue. La relation de récurrence est ici F_{n+2} = 11 F_{n+1} - 10 F_n et les premiers termes de la suite sont:

0, 1, 11, 111, 1111, 11111, 111111, ……

Non mais vraiment, il est fou Fibonacci, il est fou ! Pour tout n, F_n est le nombre 111…11 où il y a n chiffres 1 (cette suite s’appelle aussi la suite des répunits). Voyons voir comment démontrer cela.

Un nombre qui s’écrit 111…..11 avec n fois le nombre 1 n’est rien d’autre qu’un nombre de la forme \dfrac{10^n -1}{9}. Montrons que F_n est bien de cette forme:

■ Si n=0, alors F_0 = 0 = \dfrac{10^0 -1}{9} et donc le résultat est acquis.
■ Si n un entier naturel, on suppose que pour tout k\leq n, F_k = \dfrac{10^k - 1}{9}. Alors:

F_n = 11F_{n-1} - 10 F_{n-2} = 11\times \dfrac{10^{n-1} - 1 }{9} - 10 \times \dfrac{10^{n-2} - 1}{9}

d’où:

F_n = \dfrac{11\times 10^{n-1} - 11 - 10^{n-1} + 10}{9} = \dfrac{(11 -1) \times 10^{n-1} - 1}{9}

ce qui donne bien

F_n = \dfrac{10^n - 1}{9}

D’autres exemples

On peut s’amuser à tester plein de a et b différents (et je vous invite à le faire), citons encore quelques cas intéressants:

1) Si a=3 et b=-1, on obtient la suite:

0, 1, 3, 8, 21, 55 …

Ce sont les nombres de Fibonacci de rang pair (de la suite de Fibonacci f_n classique, celle dont vous aviez l’habitude avant de lire cet article):

f_0, f_2, f_4, f_6, ...

2) Dans le cas où a=2 et b=1, on obtient la suite de nombres suivante:

0, 1, 2, 5, 12, 29, 70…

C’est un exemple de suite moins connu, mais qui porte un nom quand même: ce sont les nombres de Pell.

Cas général

Nous allons exprimer de manière générale (c’est-à-dire pour a et b quelconques) le terme F_n en fonction de n. Pour cela, il faut se souvenir de la résolution des suites récurrentes linéaires (voir la page Wikipédia associée pour plus de précisions).

La relation de récurrence F_{n+2} = a F_{n+1} + b F_n est, bien entendu, équivalente à F_{n+2} -aF_{n+1} - b F_n=0 donc le polynôme caractéristique associé à cette relation de récurrence est P = X^2 -aX - b. Le discriminant de ce polynôme est \Delta = (-a)^2 -4\times 1 \times (-b) = a^2 + 4b. On note \alpha et \beta les racines complexes de ce polynôme (racines qui peuvent être réelles si \Delta>0 et égales si \Delta =0). On distingue deux cas:

1er cas: si \Delta =0 alors \alpha=\beta et dans ce cas (en supposant \alpha non nul car ce cas est peu passionnant), la théorie dit alors qu’il existe deux constantes réelles \lambda et \mu tels que:

\forall n, F_n = (\lambda n + \mu) \alpha^n

Pour déterminer ces deux constantes, on utilise les « conditions initiales »:

F_0 = 0 \Longrightarrow 0 = (\lambda \times 0 + \mu) \alpha^0 \Longrightarrow \mu =0

De plus,

F_1 = 1 \Longrightarrow 1 = (\lambda \times 1 + 0 ) \alpha^1 \Longrightarrow \lambda = \dfrac{1}{\alpha}

Ainsi,

\boxed{F_n = \frac{n}{\alpha} \alpha^n = n \alpha^{n-1}}

Remarque: On peut même affiner cette expression car si \Delta =0, on sait que la racine (double) du trinôme X^2 -aX -b est \alpha = \frac{-(-a)}{2\times 1} = \frac{a}{2} et donc F_n= n \left(\dfrac{a}{2} \right)^{n-1} !

2ème cas: Si \Delta \neq 0 alors les racines \alpha et \beta sont distinctes, et la théorie nous dit qu’il existe deux constantes \lambda et \mu telles que:

\forall n, F_n = \lambda \alpha^n + \mu \beta ^n

Comme précédemment, on détermine ces constantes à l’aide des conditions initiales:

F_0 = 0 \Longrightarrow 0 = \lambda \alpha^0 + \mu \beta^n \Longrightarrow \lambda + \mu =0 \Longrightarrow \mu = - \lambda
F_1 = 1 \Longrightarrow 1 = \lambda \alpha^1 - \lambda \beta^1 \Longrightarrow \lambda (\alpha - \beta) = 1

D’où:

\lambda = \dfrac{1}{\alpha - \beta} ; \mu = - \dfrac{1}{\alpha - \beta}

Ainsi,

F_n = \dfrac{1}{\alpha - \beta} \alpha^n - \dfrac{1}{\alpha - \beta} \beta^n

et on en déduit la jolie formule (dite de Binet):

\boxed{ F_n = \dfrac{\alpha^n - \beta^n}{\alpha - \beta} }

Application des formules

Si a=2 et b=-1, nous avions obtenu la suite de tous les entiers naturels. Voyons voir pourquoi grâce aux formules précédentes: dans ce cas, le polynôme caractéristique est P =X^2 - 2X +1 dont le discriminant vaut 0. La racine double de ce polynôme est donc \alpha = \frac{-(-2)}{2\times1} = 1, et donc, d’après la formule précédente, F_n = n \times 1^{n-1} = n.

Si a=3 et b=-2, nous avions obtenu la suite des nombres de Mersenne. En effet, le polynôme caractéristique est P = X^2 -3X +2, qui a pour discriminant \Delta = 1 et donc pour racines: \alpha = 2 et \beta = 1. D’après la formule précédente, on en déduit que F_n = \frac{2^n - 1^n}{2-1} = 2^n - 1 !

Enfin, si a=1 et b=1, c’est-à-dire dans le cas de la suite de Fibonacci classique, on a P=X^2 - X -1 et il y a deux racines \alpha = \frac{1+\sqrt{5}}{2} (le nombre d’or !) et \beta = \frac{1-\sqrt{5}}{2}. Comme \alpha - \beta = \sqrt{5}, cela nous donne la formule:

F_n = \dfrac{ (\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} = \dfrac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5} }.

Comment construire la suite des répunits en base m quelconque ?

En autre application des formules, nous allons voir qu’il est toujours possible de choisir a et b de façon à ce que la suite de Fibonacci obtenue soit la suite des répunits en base m quelconque, c’est-à-dire la suite des nombres qui s’écrivent uniquement avec des 1 quand on les écrit en base m (1, 11, 111, ….). Par exemple, nous avions vu que pour avoir la suite des répunits en base 10, il fallait prendre a=11 et b=-10 et que pour avoir les suite des répunits en base 2 (c’est-à-dire les nombres de Mersenne !), il fallait prendre a=3 et b=-2.

Tout d’abord, la suite des répunits en base m est la suite des nombres \frac{m^n - 1}{m-1} (n \in \mathbb{N}). D’après la formule F_n = \frac{\alpha^n- \beta^n}{\alpha - \beta}, on voit que pour obtenir la suite des répunits en base m, il suffit de prendre a et b de façon à ce que les racines du polynôme X^2 - aX - b soit \alpha = m et \beta =1. C’est à ce moment-là qu’on ressort les vieilles recettes du lycée. On sait que le produit des racines est égal au coefficient de terme constant et que la somme des racines est égale à l’opposée du coefficient du terme en X, ce qui donne le système:

\begin{cases} m\times 1 = -b \\ m+1 = -(-a) \end{cases}

Ca doit sans doute être le système le plus con de toute votre carrière mathématique, mais quoiqu’il en soit, on voit que pour obtenir la suite des répunits en base m, il suffit de prendre a=m+1 et b=-m. Pour la base 10, nous avions bien pris a=10+1=11 et b=-10.

Par exemple, quelle base vous ferait plaisir ? Vous avez l’âme d’un babylonien et vous aimez la base 60 ? Prenez a=61 et b=-60 et vous obtenez (en écriture décimale) la suite:

0, 1, 61, 3661, 219661, 13179661, …

ce qui, écrit en base 60, donne: 0, 1, 11, 111, 1111, 11111, …

Un dernier exemple, pour la route

Si on prend a=9 et b=10, on obtient:

0, 1, 9, 91, 909, 9091, 90909, 909091, 9090909, 90909091, 909090909, …

Autrement dit, s’il y a un 1, on le remplace par 09, et s’il n’y a pas de 1, on en accole un ! Et je vous laisse méditer là-dessus sans plus d’explications !

Advertisements
Cet article, publié dans Nombres, est tagué , , , , . Ajoutez ce permalien à vos favoris.

2 commentaires pour Super Fibo

  1. Ping : Les propriétés étonnantes de la Super Fibo | L'Endormitoire

  2. Kikoo Lol dit :

    Merci pour la photographie, qui est la parfaite illustration du foutage de gueule intégral que représente la volonté de voir cette suite partout dans l’art !

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s