Comment résoudre les relations de récurrence?

Reconnaître que toute récurrence de la forme an = r * an-1 est une suite géométrique.

En essayant de trouver une formule pour une séquence mathématique, une étape intermédiaire courante consiste à trouver le n ^ième terme, non pas en fonction de n, mais en termes de termes antérieurs de la séquence. Par exemple, alors qu'il serait bien d'avoir une fonction de forme fermée pour le n ^ème terme de la suite de Fibonacci, parfois tout ce que vous avez est la relation de récurrence, à savoir que chaque terme de la suite de Fibonacci est la somme des deux termes précédents. Cet article présentera plusieurs méthodes pour déduire une formule fermée à partir d'une récurrence.

Méthode 1 sur 5: arithmétique

1

Considérons une suite arithmétique telle que 5, 8, 11, 14, 17, 20,....
2

Étant donné que chaque terme est 3 plus grand que le précédent, il peut être exprimé comme une récurrence comme indiqué.
3

Reconnaître que toute récurrence de la forme a _n = a _n-1 + d est une suite arithmétique.
4

Écrivez la formule fermée d'une suite arithmétique, éventuellement avec des inconnues comme indiqué.
5

Résolvez les inconnues en fonction de la façon dont la séquence a été initialisée. Dans ce cas, puisque 5 était le 0 ^e terme, la formule est un _n = 5 + 3n. Si à la place, vous vouliez que 5 soit le premier terme, vous obtiendriez _n = 2 + 3n.

Méthode 2 sur 5: géométrique

1

Considérons une séquence géométrique telle que 3, 6, 12, 24, 48,....
2

Étant donné que chaque terme est le double du précédent, il peut être exprimé comme une récurrence comme indiqué.
3

Reconnaître que toute récurrence de la forme a _n = r * a _n-1 est une suite géométrique.
4

Écrivez la formule fermée d'une suite géométrique, éventuellement avec des inconnues, comme indiqué.
5

Résolvez les inconnues en fonction de la façon dont la séquence a été initialisée. Dans ce cas, puisque 3 était le 0 ^e terme, la formule est a _n = 3*2 ⁿ. Si à la place, vous vouliez que 3 soit le premier terme, vous obtiendriez _n = 3*2 ^(n-1).

Reconnaître que toute récurrence de la forme an = an-1 + d est une suite arithmétique.

Méthode 3 sur 5: polynôme

1

Considérons la séquence 5, 0, -8, -17, -25, -30,... donné par la récursivité a _n = a _n-1 + n ² - 6n.
2

Toute récursivité de la forme indiquée, où p(n) est n'importe quel polynôme dans n, aura une formule polynomiale fermée de degré un supérieur au degré de p.
3

Écrivez la forme générale d'un polynôme du degré requis. Dans cet exemple, p est quadratique, nous aurons donc besoin d'un cube pour représenter la séquence a _n.
4

Puisqu'une cubique générale a quatre coefficients inconnus, quatre termes de la séquence sont nécessaires pour résoudre le système résultant. N'importe quel quatre fera l'affaire, alors utilisons les termes 0, 1, 2 et 3. Exécuter la récurrence en arrière pour trouver le -1 ^ème terme peut faciliter certains calculs, mais n'est pas nécessaire.
5
Soit résoudre le système résultant d'équations deg(p)+2 en deg(p)=2 inconnues, soit ajuster un polynôme de Lagrange aux points connus deg(p)+2.
- Si le terme zéro était l'un des termes que vous avez utilisés pour résoudre les coefficients, vous obtenez gratuitement le terme constant du polynôme et pouvez immédiatement réduire le système à deg(p)+1 équations en deg(p)+1 inconnues comme montré.
6

Présentez la formule fermée pour un _n comme un polynôme avec des coefficients connus.

Lisez aussi: Comment faire un arbre à facteurs?

Méthode 4 sur 5: linéaire

1

C'est la première méthode capable de résoudre la séquence de Fibonacci dans l'introduction, mais la méthode résout toute récurrence où le n ^ième terme est une combinaison linéaire des k termes précédents. Essayons donc sur les différents exemples présentés dont les premiers termes sont 1, 4, 13, 46, 157,....
2

Écrivez le polynôme caractéristique de la récurrence. Ceci est trouvé en remplaçant chaque a _n dans la récurrence par x ⁿ et en divisant par x ^(nk) laissant un polynôme monique de degré k et un terme constant non nul.
3

Résoudre le polynôme caractéristique. Dans ce cas, la caractéristique a le degré 2, nous pouvons donc utiliser la formule quadratique pour trouver ses racines.
4
Toute expression de la forme indiquée satisfait la récursivité. Le c _i sont des constantes et la base des exposants sont les racines de la caractéristique trouve au- dessus. Ceci peut être vérifié par induction.
- Si la caractéristique a une racine multiple, cette étape est légèrement modifiée. Si r est une racine de multiplicité m, utilisez (c ₁ r ⁿ + c ₂ nr ⁿ + c ₃ n ² r ⁿ +... + c _m n ^m-1 r ⁿ) au lieu de simplement (c ₁ r ⁿ). Par exemple, la séquence commençant par 5, 0, -4, 16, 144, 640, 2240,... satisfait la relation récursive a _n = 6a _n-1 - 12a _n-2 + 8a _n-3. Le polynôme caractéristique a une racine triple de 2 et la formule de forme fermée a _n = 5*2ⁿ - 7*n*2 ⁿ + 2*n ² *2 ⁿ.
5

Trouvez les c _i qui satisfont aux conditions initiales spécifiées. Comme pour l'exemple polynomial, cela se fait en créant un système linéaire d'équations à partir des termes initiaux. Puisque cet exemple a deux inconnues, nous avons besoin de deux termes. N'importe quel deux fera l'affaire, alors prenez le 0 ^ème et le 1 ^er pour éviter d'avoir à élever un nombre irrationnel à une puissance élevée.
6

Résoudre le système d'équations résultant.
7

Branchez les constantes résultantes dans la formule générale en tant que solution.

Il peut être exprimé comme une récurrence comme indiqué — Étant donné que chaque terme est le double du précédent, il peut être exprimé comme une récurrence comme indiqué.

Méthode 5 sur 5: générer des fonctions

1

Considérons la séquence 2, 5, 14, 41, 122.... donnée par la récursivité représentée. Cela ne peut être résolu par aucune des méthodes ci-dessus, mais une formule peut être trouvée en utilisant des fonctions génératrices.
2

Écrivez la fonction génératrice de la suite. Une fonction génératrice est simplement une série entière formelle où le coefficient de x ⁿ est le n ^ième terme de la séquence.
3

Manipulez la fonction génératrice comme indiqué. L'objectif de cette étape est de trouver une équation qui nous permettra de résoudre pour la fonction génératrice A(x). Extraire le terme initial. Appliquez la relation de récurrence aux termes restants. Divisez la somme. Extraire les termes constants. Utilisez la définition de A(x). Utilise la formule de la somme d'une série géométrique.
4

Trouvez la fonction génératrice a(x).
5

Trouvez le coefficient du x ⁿ dans a(x). Les méthodes pour le faire varieront en fonction de l'apparence exacte de A(x), mais la méthode des fractions partielles, combinée à la connaissance de la fonction génératrice d'une séquence géométrique, fonctionne ici comme indiqué.
6

Écrivez la formule de a _n en identifiant le coefficient de x ⁿ dans a(x).

Conseils

L'induction est également une technique populaire. Il est souvent facile de prouver par induction qu'une formule spécifiée satisfait une récursivité spécifiée, mais le problème est que cela nécessite de deviner la formule à l'avance.
Certaines de ces méthodes sont gourmandes en calculs avec de nombreuses possibilités de commettre une erreur stupide. Il est bon de comparer la formule à quelques termes connus.
"En mathématiques, les nombres de Fibonacci ou suite de Fibonacci sont les nombres de la suite entière suivante: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
- La spirale de Fibonacci: une approximation de la spirale dorée créée en dessinant des arcs de cercle reliant les coins opposés des carrés du pavage de 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 nombres de la séquence de Fibonacci sont soit 1 et 1, soit 0 et 1, selon le point de départ choisi de la séquence, et chaque nombre suivant est la somme des deux précédents.
- En termes mathématiques, la suite F _n des nombres de Fibonacci est définie par la relation de récurrence
- F _n = F _n-1 + F _n-2 avec valeurs de départ F ₁ = 1, F ₂ = 1 ou F ₀ = 0, F ₁ = 1.
- La limite lorsque n augmente le rapport F _n /F _n-1 est connue sous le nom de nombre d'or ou nombre d'or ou Phi (Φ), de même que la limite lorsque n augmente du rapport F _n-1 /F _n." ¹