Solution explicite des formules récursives
Lorsqu’une suite est définie par une formule récursive, il peut être difficile de calculer un terme quelconque, car il faut toujours connaître les précédents. C’est pourquoi on cherche souvent une solution explicite, où chaque terme peut être calculé directement à partir de \( \large n \).
De récursif à explicite
Une méthode courante consiste à écrire les premiers termes et à essayer de trouver un motif. Souvent, les premiers calculs révèlent une relation qui peut être généralisée.
Exemple 1
Nous considérons la suite
$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$
Les premières valeurs sont
$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16 $$
Le motif est clair : chaque terme est une puissance de 2. La formule explicite est
$$ \large a_{n} = 2^n $$
Exemple 2
Nous considérons la suite
$$ \large a_{n} = 2 \cdot a_{n-1} + 1, \quad a_{0} = 1 $$
Les premières valeurs sont
$$ \large a_{1} = 3, \quad a_{2} = 7, \quad a_{3} = 15, \quad a_{4} = 31 $$
Ici, nous voyons le motif : \( \large a_{n} = 2^{\,n+1} - 1 \). Cela peut être démontré par induction ou en “dépliant la récurrence” étape par étape.
Déplier la récurrence
Au lieu de seulement deviner le motif, on peut essayer de substituer plusieurs fois dans la formule. Par exemple :
$$ \large a_{n} = 2 \cdot a_{n-1} + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2 \cdot (2 \cdot a_{n-2} + 1) + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2^2 \cdot a_{n-2} + 2 + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2^3 \cdot a_{n-3} + 2^2 + 2 + 1 $$
Si nous continuons ce motif jusqu’à \( \large a_{0} = 1 \), nous obtenons
$$ \large a_{n} = 2^n \cdot a_{0} + (2^n - 1) $$
Comme \( \large a_{0} = 1 \), le résultat devient
$$ \large a_{n} = 2^n + 2^n - 1 \quad \Leftrightarrow $$
$$ \large a_{n} = 2^{\,n+1} - 1 $$
Exemple d’une récurrence du 2ᵉ ordre
Nous considérons maintenant une suite qui dépend des deux termes précédents :
$$ \large a_{n} = a_{n-1} + a_{n-2}, \quad a_{0} = 2, \quad a_{1} = 3 $$
Les premiers termes sont :
$$ \large a_{2} = 5, \quad a_{3} = 8, \quad a_{4} = 13, \quad a_{5} = 21, \ldots $$
Pour trouver une formule explicite, nous utilisons la méthode des racines caractéristiques. Nous supposons une solution de la forme :
$$ \large a_{n} = r^n $$
Pourquoi cette supposition ?
La récurrence est linéaire et a des coefficients constants.
Lorsqu’un terme est toujours une combinaison linéaire d’un nombre fixe de termes précédents, il est naturel d’essayer une forme exponentielle \( \large r^n \). Si nous insérons cette supposition, la récurrence se réduit à une équation en \( \large r \), qui ne dépend pas de \( \large n \).
Cela signifie que toute la récurrence peut être satisfaite par une suite géométrique où le rapport entre deux termes successifs est constant.
D’autres suppositions, comme \( \large n^\alpha \), ne pourraient pas satisfaire la récurrence pour tout \( \large n \).
Inséré dans la récurrence, cela donne :
$$ \large r^n = r^{n-1} + r^{n-2} $$
En divisant par \( \large r^{\,n-2} \) (pour \( \large r \neq 0 \)), nous obtenons
$$ \large r^2 = r + 1 $$
Ceci s’appelle l’équation caractéristique. Elle peut s’écrire :
$$ \large r^2 - r - 1 = 0 $$
Avec la formule quadratique, nous trouvons le discriminant :
$$ \large \Delta = (-1)^2 - 4 \cdot 1 \cdot (-1) \quad \Leftrightarrow $$
$$ \large \Delta = 1 + 4 \quad \Leftrightarrow $$
$$ \large \Delta = 5 $$
D’où provient la racine carrée de 5. Les solutions sont :
$$ \large r_1 = \frac{1 + \sqrt{5}}{2}, \quad r_2 = \frac{1 - \sqrt{5}}{2} $$
Ainsi, la solution générale est
$$ \large a_{n} = C_1 \cdot r_1^n + C_2 \cdot r_2^n $$
Nous déterminons les constantes à partir des conditions initiales :
$$ \large a_{0} = 2 = C_1 + C_2 $$
$$ \large a_{1} = 3 = C_1 \cdot r_1 + C_2 \cdot r_2 $$
D’où :
$$ \large C_1 = \frac{1 + \sqrt{5}}{\sqrt{5}}, \quad C_2 = \frac{\sqrt{5} - 1}{\sqrt{5}} $$
La formule explicite devient donc :
$$ \large a_{n} = \frac{1 + \sqrt{5}}{\sqrt{5}} \cdot \left(\frac{1 + \sqrt{5}}{2}\right)^n \;+\; \frac{\sqrt{5} - 1}{\sqrt{5}} \cdot \left(\frac{1 - \sqrt{5}}{2}\right)^n $$
Avec cette formule, on peut calculer directement n’importe quel terme. Par exemple, pour \( \large n = 5 \) :
$$ \large a_{5} = 21 $$
Résumé
Une solution explicite permet d’aller directement au terme numéro \( \large n \) sans calculer tous les précédents. On trouve souvent la formule en observant un motif ou en dépliant la récurrence. Dans des cas plus avancés, comme pour des récurrences du 2ᵉ ordre, on peut utiliser la méthode des racines caractéristiques. De nombreuses formules récursives peuvent ainsi être réécrites sous une forme explicite simple, qui apporte à la fois une compréhension de la structure et une facilité de calcul.