Xavier Hubaut - Professeur émérite de l'Université Libre de Bruxelles
Suites récurrentes
Généralisons quelque peu la célèbre suite de Fibonacci, et supposons que chaque terme est, non pas la somme des deux précédents mais plus généralement, une combinaison linéaire des deux précédents.
Quelle est la limite du quotient de 2 termes consécutifs de cette suite? Si cette limite existe, soit φ sa valeur; pour n suffisamment grand on a approximativement xn = φxn-1 et xn-1 = φxn-2; donc la relation de récurrence devient φ²xn-2 = φaxn-2 + bxn-2; en simplifiant par xn-2 on a: φ² = φa + b et φ doit être solution de l'équation:
Il est clair que si cette équation n'a pas de solution réelle, la limite n'existe pas. On peut néanmoins s'interroger sur l'évolution du rapport xn/xn-1 en fonction de n.
En choisissant des exemples numériques on constate des comportements assez curieux suivant les valeurs choisies pour a et b (Remarquons que seul le rapport a²/b importe!). Parfois même cette suite de rapports est périodique et, avec un peu de chance, on tombe facilement sur des valeurs donnant une périodicité d'ordre 3, 4, 6. Plusieurs questions se posent: peut-on obtenir n'importe quelle période? Comment choisir a et b? Quelle est la nature de la relation entre a et b ? Essayons d'éclaircir ce problème.
Par exemple si a = 1 et b = - 0.32
Quelques essais nous auront rapidement convaincus que les valeurs de départ x0 et x1 n'ont guère d'influence sur l'évolution à long terme du rapport xn/xn-1. Exprimons les xn en fonction de x0 et x1.
x2 = ax1 + bx0
x3 = ax2 + bx1 = a(ax1 + bx0) + bx1
= (a² + b)x1 + abx0
x4 = ax3 + bx2 = a[(a² + b)x1 + abx0] + b[ax1 + bx0]
=(a³ + 2ab)x1 + (a²b + b²)x0
etc.
On voit ainsi que xn = Pn(a,b)x1 + Qn(a,b)x0, où Pn et Qn sont 2 polynômes (de degré n-1) en a et b. Que peut-on dire de ces polynômes? Evidemment ils satisfont à une condition qui découle de la définition même de la suite.
c'est-à-dire:
et de même pour les polynômes Qn. Ces derniers ne sont guère intéressants car si nous posons P0 = 0 et P1 = 1, nous voyons que Qn = bPn-1. Nous pouvons donc oublier les polynômes Qn et ne nous intéresser qu'aux Pn.
On a donc:
Voici l'expression des premiers polynômes Pn:
P0 = 0
P1 = 1
P2 = a
P3 = a² + b
P4 = a³ + 2ab
P5 = a4 + 3a²b + b²
etc.
On voit apparaître une analogie avec le triangle de Pascal et on vérifie sans peine que les polynômes Pn s'obtiennent à partir du développement de (a + b)n en lisant le tableau "en oblique".
On a:
(il suffit de vérifier que P1 = 1 et P2 = a et que la relation de récurrence est satisfaite).
Revenons à la périodicité de la suite des rapports xn/xn-1.
Le rapport
Il y aura périodicité (de période n - 1) si xn/xn-1 = x1/x0 = λ
c'est à dire:
où λPn + bPn-1 - λ²Pn-1 - bλPn-2 = 0 ; mais Pn = aPn-1 + bPn-2, d'où
aλPn-1 + bλPn-2 + bPn-1 - λ²Pn-1 - bλPn-2 = 0 , c'est-à-dire
(aλ + b - λ²)Pn-1 = 0
Nous sommes précisément dans le cas où cette équation n'a pas de solution réelle (à comparer avec l'équation en φ plus haut). Le polynome en λ ne peut être nul et donc Pn-1 = 0. Le résultat est donc que la suite des rapports est périodique d'ordre n si Pn = 0. Inversement si Pn = 0 la suite des rapports est périodique, de période n, et par conséquent P2n = P3n =....= 0. Comme ces polynômes n'ont pas de racine multiple, l'ensemble Pn(a,b) possède donc la propriété remarquable que si m | n Pm(a,b) | Pn(a,b).
Une étude plus approfondie de ceux-ci montrerait qu'ils possèdent tous (au moins) une racine réelle négative dont la valeur absolue est fonction décroissante de n; les premières valeurs sont (pour a = 1)
Lorsque la période n tend vers l'infini, la plus petite racine négative, en valeur absolue, tend vers -0,25.
xn = axn-1 + bxn-2
Quelle est la limite du quotient de 2 termes consécutifs de cette suite? Si cette limite existe, soit φ sa valeur; pour n suffisamment grand on a approximativement xn = φxn-1 et xn-1 = φxn-2; donc la relation de récurrence devient φ²xn-2 = φaxn-2 + bxn-2; en simplifiant par xn-2 on a: φ² = φa + b et φ doit être solution de l'équation:
φ² - aφ - b = 0.
Il est clair que si cette équation n'a pas de solution réelle, la limite n'existe pas. On peut néanmoins s'interroger sur l'évolution du rapport xn/xn-1 en fonction de n.
En choisissant des exemples numériques on constate des comportements assez curieux suivant les valeurs choisies pour a et b (Remarquons que seul le rapport a²/b importe!). Parfois même cette suite de rapports est périodique et, avec un peu de chance, on tombe facilement sur des valeurs donnant une périodicité d'ordre 3, 4, 6. Plusieurs questions se posent: peut-on obtenir n'importe quelle période? Comment choisir a et b? Quelle est la nature de la relation entre a et b ? Essayons d'éclaircir ce problème.
Par exemple si a = 1 et b = - 0.32
Quelques essais nous auront rapidement convaincus que les valeurs de départ x0 et x1 n'ont guère d'influence sur l'évolution à long terme du rapport xn/xn-1. Exprimons les xn en fonction de x0 et x1.
x2 = ax1 + bx0
x3 = ax2 + bx1 = a(ax1 + bx0) + bx1
= (a² + b)x1 + abx0
x4 = ax3 + bx2 = a[(a² + b)x1 + abx0] + b[ax1 + bx0]
=(a³ + 2ab)x1 + (a²b + b²)x0
etc.
On voit ainsi que xn = Pn(a,b)x1 + Qn(a,b)x0, où Pn et Qn sont 2 polynômes (de degré n-1) en a et b. Que peut-on dire de ces polynômes? Evidemment ils satisfont à une condition qui découle de la définition même de la suite.
xn = a[Pn-1x1 + Qn-1x0] + b[Pn-2x1 + Qn-2x0]
= (aPn-1 + bPn-2)x1 + (aQn-1 + bQn-2)x0
= (aPn-1 + bPn-2)x1 + (aQn-1 + bQn-2)x0
c'est-à-dire:
Pn = aPn-1 + bPn-2
et de même pour les polynômes Qn. Ces derniers ne sont guère intéressants car si nous posons P0 = 0 et P1 = 1, nous voyons que Qn = bPn-1. Nous pouvons donc oublier les polynômes Qn et ne nous intéresser qu'aux Pn.
On a donc:
xn = Pnx1 + bPn-1x0
Voici l'expression des premiers polynômes Pn:
P0 = 0
P1 = 1
P2 = a
P3 = a² + b
P4 = a³ + 2ab
P5 = a4 + 3a²b + b²
etc.
On voit apparaître une analogie avec le triangle de Pascal et on vérifie sans peine que les polynômes Pn s'obtiennent à partir du développement de (a + b)n en lisant le tableau "en oblique".
1
a + b
a² + 2ab + b²
a³ + 3a²b + 3ab² + b³
a4 + 4a³b + 6a²b² + 4ab³ + b4
a5 + 5a4b + 10a³b² + 10a²b³ + 5ab4 + b5
...................................................................................
a + b
a² + 2ab + b²
a³ + 3a²b + 3ab² + b³
a4 + 4a³b + 6a²b² + 4ab³ + b4
a5 + 5a4b + 10a³b² + 10a²b³ + 5ab4 + b5
...................................................................................
On a:
(il suffit de vérifier que P1 = 1 et P2 = a et que la relation de récurrence est satisfaite).
Revenons à la périodicité de la suite des rapports xn/xn-1.
Le rapport
Il y aura périodicité (de période n - 1) si xn/xn-1 = x1/x0 = λ
c'est à dire:
où λPn + bPn-1 - λ²Pn-1 - bλPn-2 = 0 ; mais Pn = aPn-1 + bPn-2, d'où
aλPn-1 + bλPn-2 + bPn-1 - λ²Pn-1 - bλPn-2 = 0 , c'est-à-dire
(aλ + b - λ²)Pn-1 = 0
Nous sommes précisément dans le cas où cette équation n'a pas de solution réelle (à comparer avec l'équation en φ plus haut). Le polynome en λ ne peut être nul et donc Pn-1 = 0. Le résultat est donc que la suite des rapports est périodique d'ordre n si Pn = 0. Inversement si Pn = 0 la suite des rapports est périodique, de période n, et par conséquent P2n = P3n =....= 0. Comme ces polynômes n'ont pas de racine multiple, l'ensemble Pn(a,b) possède donc la propriété remarquable que si m | n Pm(a,b) | Pn(a,b).
Une étude plus approfondie de ceux-ci montrerait qu'ils possèdent tous (au moins) une racine réelle négative dont la valeur absolue est fonction décroissante de n; les premières valeurs sont (pour a = 1)
| n | b |
| 3 4 5 6 7 8 9 10 ... |
-1 -0.5 -0.381966... -0.333333... -0.307978... -0.292893... -0.283118... -0.276393... ... |
Lorsque la période n tend vers l'infini, la plus petite racine négative, en valeur absolue, tend vers -0,25.