Comment résoudre des relations de récurrence

Informations concernant l'auteur.e

Quand on cherche une formule du terme général d'une suite donnée, on passe souvent par le n^è terme, non pas en fonction de n, mais en fonction des termes précédents le n^è terme en question. C'est ainsi qu'il serait pratique d'avoir une formule type qui donne le n^è terme de la suite de Fibonacci, mais malheureusement, tout ce qu'on a, c'est la relation de récurrence, en l'occurrence le fait que chaque terme de la suite de Fibonacci est la somme des deux termes précédents. Dans cet article, nous vous présentons plusieurs méthodes pour trouver la formule analytique du n^è terme à partir d'une récurrence.

Méthode 1

Méthode 1 sur 5:
Utiliser la méthode pour une suite arithmétique

1
Prenons la suite arithmétique suivante : 5, 8, 11, 14, 17, 20, etc.
2
Voyez la relation de récurrence. Comme chacun des termes de la suite est la somme du précédent auquel on a ajouté 3, il est facile d'exprimer la relation de récurrence, comme on le voit ci-dessus.
3
Gardez à l'esprit que toute récurrence de a_n = a_n-1 + d est aussi une suite arithmétique.
4
Exprimez la formule type d'une suite arithmétique. Utilisez pour cela les coefficients inconnus comme montré ci-dessus.
5
Trouvez chaque coefficient en fonction du terme initial de la suite. Dans notre exemple, si 5 est le terme initial (de rang 0), la formule est : a_n = 5 + 3n. Si 5 est le terme de rang 1, la formule sera alors : a_n = 2 + 3n.

Publicité

Méthode 2

Méthode 2 sur 5:
Utiliser la méthode pour une suite géométrique

1
Prenons la suite géométrique suivante : 3, 6, 12, 24, 48, etc.
2
Employez la relation de récurrence. Comme chacun des termes de la suite est le double du précédent (raison 2), on peut utiliser la relation de récurrence indiquée ci-dessus.
3
Remarquez que toute récurrence de forme a_n = r x a_n-1 est une suite géométrique.
4
Exprimez la formule type du terme général d'une suite géométrique. Pour cela, employez les coefficients inconnus comme dans l'exemple.
5
Trouvez chaque coefficient en fonction du terme initial de la suite. Dans notre exemple, si 3 est le terme initial, la formule est : a_n = 3 x 2ⁿ. Si 3 est le terme de rang 1, la formule sera alors : a_n = 3 x 2^(n-1).

Publicité

Méthode 3

Méthode 3 sur 5:
Utiliser la méthode polynomiale

1
Prenons la suite suivante : 5, 0, - 8, - 17, - 25, - 30, etc. Elle est définie par la relation de récurrence suivante : a_n = a_n-1 + n² - 6n.
2
Mémorisez la formule. Toute récurrence de cette forme, c'est-à-dire dans laquelle p(n) est un polynôme de variable n, aura une formule générale de type polynomial d'un degré de p + 1.
3
Écrivez le polynôme général du degré requis. Dans cet exemple, p étant du second degré, vous allez avoir besoin d'une fonction du troisième degré pour représenter la suite a_n.
4
Résolvez le système. Étant donné qu'une fonction du troisième degré comporte quatre coefficients, quatre termes de la suite sont donc nécessaires pour résoudre le système. N'importe lesquels peuvent convenir, mais prenez plutôt les quatre premiers (de rang 0, 1, 2 et 3). Faites fonctionner la récurrence à l'envers pour trouver le terme précédent, ce qui rendra les calculs plus faciles.
5
Résolvez un système de (deg(p) + 2) équations à (deg(p) + 2) inconnues. Vous pouvez autrement utiliser un polynôme de Lagrange avec deg(p)+2 points connus.
- Si le terme initial était un des termes utilisés pour trouver les coefficients, vous trouverez automatiquement la constante et vous en déduisez un système à (deg(p)+1) équations à (deg(p)+1) inconnues comme dans l'exemple.
6
Présentez la formule générale pour a_n. Faites-le sous forme d'un polynôme avec les coefficients trouvés précédemment.

Publicité

Méthode 4

Méthode 4 sur 5:
Utiliser la méthode linéaire

1
Comprenez la méthode linéaire. C'est la première méthode pour résoudre une suite de Fibonacci, mais elle permet de résoudre également toute récurrence dans laquelle le n^è terme est une combinaison linéaire des k précédents termes. Prenons l'exemple de la suite dont les premiers termes sont 1, 4, 13, 46, 157, etc.
2
Formulez le polynôme caractéristique de la récurrence. Pour cela, il faut remplacer chaque a_n de la récurrence par xⁿ et diviser par x^(n-k) aboutissant ainsi à un monôme de degré k avec une constante non nulle.
3
Trouvez les racines du polynôme caractéristique. Ici, il est de degré 2, on peut donc le résoudre avec le discriminant afin de trouver les racines.
4
Chaque expression de la formule ci-dessus vérifie la récurrence. Les c_i sont les constantes et la base des puissances sont les racines de l'équation résolue. Cela peut être vérifié par intuition et tâtonnements.
- Si le polynôme caractéristique a plusieurs racines, il faudra apporter une légère modification. Si la racine r est multiple d'ordre m, utilisez cette formule : c₁rⁿ + c₂nrⁿ + c₃n²rⁿ +... + c_mn^m-1rⁿ à la place de : c₁rⁿ. Ainsi, la suite 5, 0, - 4, 16, 144, 640, 2 240, etc. vérifie la relation de récurrence a_n = 6a_n-1 - 12a_n-2 + 8a_n-3. Le polynôme caractéristique a 2 pour racine triple et la formule générale suivante : a_n = 5 x 2ⁿ - 7 x n x 2ⁿ + 2 x n² x 2ⁿ.
5
Trouvez c_i afin de satisfaire les conditions initiales. Comme dans le cas du polynôme, vous avez besoin d'un système linéaire d'équations à partir des termes initiaux. Comme il y a deux inconnues dans notre exemple, vous avez besoin de deux termes. N'importe lesquels peuvent convenir ! Prenez simplement le terme initial et celui de rang 1 pour éviter d'avoir à élever à la puissance un nombre irrationnel.
6
Résolvez le système d'équations.
7
Remplacez dans la formule les coefficients par les valeurs trouvées précédemment.

Publicité

Méthode 5

Méthode 5 sur 5:
Maitriser les fonctions génératrices

1
Prenez la suite suivante : 2, 5, 14, 41, 122, etc. Prenez aussi sa formule de récurrence (indiquée sur l'image). On ne peut la résoudre avec les méthodes vues précédemment, c'est pourquoi nous allons recourir aux fonctions génératrices.
2
Écrivez la fonction génératrice de la suite. Une fonction génératrice est tout simplement une série dans laquelle le coefficient de xⁿ est le n^è terme de la suite.
3
Réorganisez la fonction génératrice. Le but ici est de formuler une équation qui nous permette de résoudre la fonction génératrice A(x). Isolez le terme initial. Appliquez la relation de récurrence aux termes restants. Développez les termes de la somme. Mettez en facteur les constantes. Utilisez la définition de A(x). Utilisez la formule de la somme des termes consécutifs d'une suite géométrique.
4
Trouvez la fonction génératrice A(x).
5
Trouvez le coefficient de xⁿ dans A(x). Pour ce faire, la méthode va dépendre de l'écriture de A(x), mais la méthode des fractions partielles, combinée avec ce qu'on sait de la fonction génératrice d'une suite géométrique, marche aussi, comme on peut le voir ci-dessus.
6
Récrivez la formule pour a_n en reprenant le coefficient de xⁿ dans A(x).

Publicité

Conseils

La méthode intuitive est pratique. Avec ce raisonnement, il est facile de prouver qu'une formule générale vérifie la récurrence, mais cela suppose de deviner dès le départ la formule.
Certaines de ces méthodes entrainent des calculs complexes lors desquels les risques de faire des erreurs sont importants. Aussi est-il conseillé de vérifier la formule avec quelques termes faciles à contrôler.
En mathématiques, la suite de Fibonacci (aussi appelée « nombre de Fibonacci ») est la suite d'entiers suivante : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.
- La spirale de Fibonacci : c'est une approximation de la spirale d'or créée en dessinant des arcs de cercle unissant les coins opposés de carrés dans un pavage Fibonacci. Celui-ci utilise des carrés de tailles 1, 1, 2, 3, 5, 8, 13, 21 et 34.
- Par définition, les deux premiers termes de la suite de Fibonacci sont soit 1 et 1, soit 0 et 1, tout dépendra du point de départ choisi pour la suite et chaque nombre de la suite est la somme des deux précédents.
- Mathématiquement parlant, la suite F_n de Fibonacci a comme relation de récurrence : F_n= F_n-1 + F_n-2 (si F₁ = F₂ = 1 ou si F₀ = 0 et F₁ = 1).
- Le rapport F_n/F_n-1 est connu sous le nom de « nombre d'or » ou encore « phi » (Φ) et il en va de même avec le rapport F_n-1/F_n.