Théorie > Algèbre > Suites

Suites récurrentes linéaires

Connaître une suite $(a_n)$ uniquement grâce à une relation de récurrence n'est pas toujours satisfaisant. On préfère souvent connaître la suite de manière précise, c'est-à-dire avoir une formule pour $a_n$ dépendant de $n$. On peut parfois deviner cette formule en regardant les premiers termes de la suite, auquel cas vérifier que la formule est correcte est très simple : il suffit de vérifier qu'elle l'est pour les premiers termes et montrer par récurrence (grâce à la relation) qu'elle est en fait correcte pour tous les termes. Il n'est cependant parfois pas évident de deviner la formule générale (et il pourrait a priori ne pas exister de formule simple).

Dans un cas assez général, celui des suites linéaires récurrentes, il existe en fait une méthode pour trouver quelle est la formule qui se cache derrière la suite initialement définie par récurrence. On parle de suite linéaire récurrente d'ordre $p$ pour désigner une suite $(a_n)_{n \in \mathbb{N}}$ à valeur dans $\mathbb{C}$ (il peut en fait s'agir d'un corps commutatif quelconque) définie par une relation de récurrence de la forme suivante :
$$\left\{ \begin{array}{l}
a_0, a_1, \ldots, a_{p-1} \text{ sont fixés,}\\
a_{n+p} = c_0 a_n + c_1 a_{n+1} + \ldots + c_{p-1} a_{n+p-1} \text{ pour } n \geq 0.
\end{array}\right.$$
Exemples :
  • La suite $(a_n)$ définie par $a_0 = 0$, $a_1 = -1$, $a_2 = 5$ et $a_{n+3} = 3a_{n+2}-4a_n$ (pour $n \geq 0$) dont les premiers termes sont
    $$0, -1, 5, 15, 49, \ldots$$ est une suite linéaire récurrente d'ordre $3$.

  • La suite de Fibonacci $(F_n)$ (définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$ pour $n \geq 0$) est une suite linéaire récurrente d'ordre $2$.

La méthode pour trouver la formule générale derrière de telles suites est d'utiliser le résultat suivant, dont nous ne donnons pas la démonstration.

Théorème
Soit $(a_n)$ une suite de nombres complexes telle que
$$a_{n+p} = c_0 a_n + c_1 a_{n+1} + \ldots + c_{p-1} a_{n+p-1} \ \text{ pour } n \geq 0$$ (pour certains $c_0, c_1, \ldots, c_{p-1} \in \mathbb{C}$ fixés). Considérons le polynôme
$$P(x) = x^p - c_{p-1} x^{p-1} - c_{p-2} x^{p-2} - \ldots - c_1 x - c_0,$$ appelé polynôme caractéristique associé à la suite $(a_n)$. Si $r_1, r_2, \ldots, r_k$ sont les $k$ racines distinctes de $P$, de multiplicités respectives $m_1, m_2, \ldots, m_k$, alors il existe des polynômes $Q_1, Q_2, \ldots, Q_k \in \mathbb{C}[x]$ avec $\deg Q_i \leq m_i - 1$ tels que
$$a_n = Q_1(n) \cdot r_1^n + Q_2(n) \cdot r_2^n + \ldots + Q_k(n) \cdot r_k^n \ \text{ pour } n \geq 0.$$

Ce résultat nous donne donc une formule pour $a_n$ comme espéré. Il reste cependant que l'on ne connaît pas les polynômes $Q_1, \ldots, Q_k$, mais l'idée est de les trouver en exploitant les conditions initiales (c'est-à-dire les valeurs de $a_0, a_1, \ldots, a_{p-1}$).

Revenons au premier exemple ci-dessus. Nous considérions la suite $(a_n)$ définie par $a_0 = 0$, $a_1 = -1$, $a_2 = 5$ et
$$a_{n+3} = 3a_{n+2} - 4a_n \ \text{ pour } n \geq 0.$$ La première étape est de trouver le polynôme caractéristique. Pour ce faire, on met simplement tous les termes de l'égalité précédente dans le membre de gauche, puis on remplace $a_{n+i}$ par $x^i$ pour tout $i$. On obtient donc le polynôme
$$P(x) = x^3 - 3x^2 + 4.$$ Pour obtenir la formule générale pour $a_n$, il nous faut connaître les racines de $P$. Comme nous l'avons déjà dit précédemment, il n'est pas toujours facile de déterminer les racines d'un polynôme. Si le degré du polynôme (qui est égal à l'ordre de la suite linéaire récurrente) est $2$ alors on peut toujours les trouver. Lorsque le degré est plus élevé, on peut parfois deviner certaines racines et ainsi se ramener à un polynôme de plus petit degré pour déterminer les racines encore inconnues. Ici, on peut par exemple tester les petites valeurs entières et on se rend très vite compte que $-1$ est une racine de $P$. On peut donc le factoriser (par exemple par Horner) et obtenir
$$P(x) = (x+1)(x^2-4x+4).$$ Le polynôme quotient est visiblement un carré parfait, on a donc
$$P(x) = (x+1)(x-2)^2.$$ Les racines de $P$ sont donc $-1$ (de multiplicité $1$) et $2$ (de multiplicité $2$). Le résultat nous apprend donc qu'on a deux polynômes $Q_1$ et $Q_2$ dont les degrés sont strictement inférieurs à $1$ et $2$ respectivement et tels que
$$a_n = Q_1(n) \cdot (-1)^n + Q_2(n) \cdot 2^n.$$ Vu les degrés des polynômes, on peut écrire $Q_1(x) = A$ et $Q_2(x) = Bx + C$ pour $A, B, C \in \mathbb{C}$, et on a ainsi
$$a_n = A \cdot (-1)^n + (Bn + C) \cdot 2^n.$$ Il ne reste alors plus qu'à déterminer les valeurs de $A$, $B$ et $C$. Pour ce faire, on utilise les valeurs de $a_0, a_1$ et $a_2$, qui nous donnent justement trois équations pour trouver trois inconnues :
$$\left\{\begin{align}
0 = a_0 & = A + C \\
-1 = a_1 & = -A+2B+2C \\
5 = a_2 &= A + 8B + 4C
\end{align}\right.$$ En résolvant ce système, on trouve $A = 1, B = 1$ et $C = -1$. On a donc finalement la formule générale
$$a_n = (-1)^n + (n-1) \cdot 2^n.$$ On vérifiera toujours pour éviter les erreurs que les termes suivants ($a_3 = 15, a_4 = 49, \ldots$) vérifient également cette formule. Remarquons qu'il n'aurait pas été facile de deviner cette formule et que cette méthode est dès lors assez puissante, pourvu que l'on sache trouver les racines du polynôme caractéristique relatif à la suite qui nous intéresse.