Application au problème de Fibonacci

 

 

 

 

Introduction En 1202, un mathématicien italien connu sous le nom de Fibonacci a posé la question suivante: supposons qu'un couple (mâle-femelle) de lapins sont nés au début de l’année. Nous assumons les conditions suivantes:

1.      La maturité sexuelle du lapin est atteinte après un mois qui est aussi la durée de gestation.

2.       Chaque portée comporte toujours un mâle et une femelle.

3.      Les lapins ne meurent pas.

 

Combien y aura-t-il de lapins après un an?

 

Soit fn le nombre de lapins au début du nième mois. Alors on a

 

                                            f0=1, f1=1, f2=2, f3=3, f4=5,... (voir le diagramme ci-dessous) et en générale,

 

                                                     fn=fn-1+fn-2.

 

 

 

En d'autres termes, chaque terme dans cette suite (commençant par n=2) est égal à la somme des deux termes précédents. La suite {1,1,2,3,5,8,13,21,34…}  produite selon cet arrangement a été appelé en l'honneur de Fibonacci. Cette suite se produit dans beaucoup d'endroits en mathématiques, la science générale, en nature et même dans l'art.

La table suivante donne les 55 premiers nombres de Fibonacci:

 

 

n, fn

n, fn

n, fn

n, fn

n, fn

1, 1

12, 144

23, 28657

34, 5702887

45, 1134903170

2, 1

13, 233

24, 46368

35, 9227465

46, 1836311903

3, 2

14, 377

25, 75025

36, 14930352

47, 2971215073

4, 3

15, 610

26, 121393

37, 24157817

48, 4807526976

5, 5

16, 987

27, 196418

38, 39088169

49, 7778742049

6, 8

17, 1597

28, 317811

39, 63245986

50, 12586260925

7, 13

18, 2584

29, 514229

40, 102334155

51, 20365011074

8, 21

19, 4181

30, 832040

41, 165580141

52, 32951280099

9, 34

20, 6765

31, 1346269

42, 267914296

53, 53316291173

10, 55

21, 10946

32, 2178309

43, 433494437

54, 86267571272

11, 89

22, 17711

33, 3524578

44, 701408733

55, 139583862445

 

En particulier, à la fin de la première année (n=12), le nombre de  lapins est 144.

 

Comme on peut le voir la suite de Fibonacci est croissante. Pour avoir une idée de ses termes après n=55, cliquez ici.

 

Une question normale serait: peut-on trouver une expression qui donne fn  pour n'importe quel ? La réponse est oui si on a une idée commet diagonaliser une matrice. Rappelons alors quelques faits de base sur la diagonalization des matrices.

 

 

Définition Soit A une matrice carrée de format nxn.  On dit qu’un nombre  λ est une  valeur propre  de A s’il existe un vecteur non-nul X de Rn tel que AX= λX. Dans ce cas, on dit que X est un vecteur propre de A correspondant à la valeur propre λ.

 

Exemple Soit

 

 

alors

 

.

 

D’où, le  vecteur

 

 

est un vecteur propre de la matrice A correspondant à la valeur propre  (1+√5)/2.

 

Étant donnée une matrice carrée A de format nxn, les valeurs propres de A sont les solutions de l’équation

 

 

 

où |A- λ I| représente le déterminant de la matrice A- λ I et  I est la matrice identité de même format que A.

 

Exemple Pour la matrice  A de l’exemple précédent,

 

 

En résolvant cette équation, on  trouve les deux valeurs propres :

 

 

Comment trouver les vecteurs propres de A?

 

Si  X est un vecteur propre de  of A correspondant à la valeur propre λ, alors AX= λX. En d’autres termes, (A- λI)X=0. Ceci implique que chaque vecteur propre de A est une solution du système homogène  (A- λI)X=0.

 

 

On définit l’espace propre E λ correspondant  à la valeur propre λ de A comme étant l’ensemble de tous les vecteurs propres correspondant à λ avec le vecteur nul. En d’autres termes, E λ représente l’ensemble de solutions du système (A- λI)X=0.

 

Pour voir comment ceci fonctionne, considérons encore la matrice A de nos exemples précédents. Pour trouver les vecteurs propres de A correspondants à la valeur propre λ1=(1+√5)/2, on résout le système

 

 

 

 

qui est équivalent au système suivant :

 

 

 

La solution générale est:

 

 

Ceci montre en particulier que le vecteur

 

est une base de Eλ1. Similairement, on peut montrer que le vecteur

 

 

est une base de l’espace propre Eλ2. En particulier, dim (Eλ1) + dim (Eλ2)=2.

 

Définition Une matrice carrée A est dite diagonale si toutes ses entrées sont nulls sauf, peut-être, celles qui sont sur la diagonale principale. Une matrice carrée est dite diagonalisable s’il existe une matrice inversible P de même format que A qui satisfait la condition :

 

 

pour une certaine matrice D (on dit que A est semblable à une matrice diagonale).

 

Pourquoi sommes-nous intéressés aux matrices diagonalisables? Une des propriétés intéressantes des matrices diagonalisables est la facilité de calculer leurs puissances. Voici comment cela fonctionne:

 

Si A est diagonalisable, alors A=PDP-1  pour une certaine matrice inversible P et une matrice diagonale D. Essayons de calculer quelques puissances de A:

 

 

 

 

En général, on peut voir que Ak=PDkP-1  pour n'importe quelle puissance k. que diriez-vous de Dk? Rappelez-vous que D a la forme

 

 

 

 

ainsi il n'est pas difficile de voir que Dk aura la forme

 

 

 

 

 

 

 

Par conséquent, le calcul des puissances d'une matrice diagonalisable devient une tâche facile une fois qu’on  connaît les matrices P et D dans la formule

 

.

 

 

Le théorème suivant donne  algorithme pour diagonaliser une matrice.

Théorème  Soit  A une matrice de format  nxn, et soient  λ1,…, λk les valeurs propres (réelles) distinctes de A.  Alors:

1.      A est diagonalisable si et seulement si dim (Eλ1) +…+ dim (Eλk)=n.

2.      Si A est diagonalisable avec P-1AP=D, alors les colonnes de P sont tous les vecteurs de base pour les espaces propres de A et les entrées sur la diagonale principale de D sont les valeurs propres correspondantes.

 

Considérons de nouveau la matrice

 

 

et appliquons l’ algorithme du théorème précédent. Comme on a déjà montré que dim (Eλ1) + dim (Eλ2)=2, on sait maintenant A est diagonalisable. Soit

 

 

 

 

 

la matrice dont les colonnes sont les vecteurs de base des espaces propres trouvés ci-haut. Alors

 

 

 

Par le théorème précédent,  on a la décomposition suivante de A:

 

 

 

Maintenant voyons comment tout ceci peut être appliqué pour répondre à notre problème au sujet des lapins de Fibonacci. Le modèle général pour la suite de Fibonacci était:

 

fn=fn-1+fn-2.

 

 

Une expression générale pour fn n'est pas évidente, mais une torsion intelligente transforme le problème en un autre plus simple en employant matrices. L'idée est de calculer le vecteur

 

 

 

pour tout n ≥ 0 au lieu de calculer  fn . La relation fn=fn-1+fn-2 donne

 

 

 

 

 

 

est la même matrice qu’on a utilisé ci-haut. En utilisant la relation

 

 

on obtient

 

Mais  An=PDnP-1 

 

 

 

 

sont comme avant. Alors, 

 

 

pour tout n ≥ 0. Dans cette formule, le dernier vecteur est

 

 

 

 

Si vous multipliez soigneusement ceci et prenez la première composante du vecteur résultant, vous obtenez la nième terme de Fibonacci:

 

 

 

 

Est-il maintenant facile de calculer le 100ième terme de la suite de Fibonacci :

 

 

 

Une calculatrice assez puissante donne la valeur 573147844013817084101 pour f100.

 

Remarquez que le nombre

 

 

est un des nombres les plus mystérieux, il est largement connu sous le nom du nombre d’or. Ce nom vient du fait suivant : un rectangle de dimensions s et Φs  a une forme agréable, probablement parce que si on plie le côté plus petit (de longueur s) dans le rectangle, on obtient un carré de côté s et un plus petit rectangle ayant comme côtés s et s(1- Φ). Ce plus petit rectangle est semblable au rectangle original !