Suites récurrentes : cours de maths sup en PDF.

Une suite \((u_n)\) est arithmétique de raison \(r\) si \(u_{n+1} = u_n + r\) pour tout \(n \in \mathbb{N}\). Elle est géométrique de raison \(q\) si \(u_{n+1} = q\,u_n\) pour tout \(n \in \mathbb{N}\).

Pour tous entiers \(n\) et \(p\), une suite arithmétique vérifie \(u_n = u_p + (n – p)\,r\), et une suite géométrique vérifie \(u_n = u_0\,q^n\). De plus, on dispose des sommes suivantes :

\[\sum_{k=0}^{n} u_k = (n+1)\,\frac{u_0 + u_n}{2} \quad \text{(arithmétique)}, \qquad \sum_{k=0}^{n} q^k = \frac{1 – q^{n+1}}{1 – q} \quad (q \neq 1).\]

Une suite \((u_n)\) est arithmético-géométrique s’il existe deux réels \(a\) et \(b\) tels que \(u_{n+1} = a\,u_n + b\) pour tout \(n \in \mathbb{N}\).

Soit \(a \neq 1\) et \(\ell = \dfrac{b}{1 – a}\) l’unique solution de \(\ell = a\ell + b\). Alors, pour tout \(n \in \mathbb{N}\), on a

\[u_n = \ell + a^n\,(u_0 – \ell).\]

On soustrait membre à membre \(u_{n+1} = a u_n + b\) et \(\ell = a \ell + b\). On obtient \(u_{n+1} – \ell = a\,(u_n – \ell)\). Ainsi, la suite \(v_n = u_n – \ell\) est géométrique de raison \(a\). Par conséquent, \(v_n = a^n v_0\), ce qui donne la formule.

Pour une suite \(u_{n+1} = a u_n + b\) avec \(a \neq 1\) : d’abord, résoudre \(\ell = a\ell + b\) ; ensuite, poser \(v_n = u_n – \ell\) et vérifier que \(v_{n+1} = a v_n\) ; enfin, revenir à \(u_n = \ell + a^n (u_0 – \ell)\). Si \(|a| < 1\), la suite converge vers \(\ell\), quel que soit \(u_0\).

Soit \(u_0 = 1\) et \(u_{n+1} = \frac{1}{2} u_n + 3\). Le point fixe vérifie \(\ell = \frac{\ell}{2} + 3\), donc \(\ell = 6\). Par conséquent, \(u_n = 6 – 5 \cdot 2^{-n}\) et \(u_n \to 6\). Avec \(u_0 = 10\), on trouve \(u_n = 6 + 4 \cdot 2^{-n}\), qui décroît vers 6.

Soit \(a, b \in \mathbb{K}\) avec \(\mathbb{K} = \mathbb{R}\) ou \(\mathbb{C}\), et \(b \neq 0\). Une suite \((u_n)\) vérifie une récurrence linéaire homogène d’ordre 2 si \(u_{n+2} = a\,u_{n+1} + b\,u_n\) pour tout \(n\). Son équation caractéristique est \(r^2 = a r + b\), autrement dit \(r^2 – a r – b = 0\).

Pour \(r \neq 0\), la suite géométrique \((r^n)\) vérifie la récurrence si et seulement si \(r\) est racine de l’équation caractéristique.

On a \(r^{n+2} – a r^{n+1} – b r^n = r^n (r^2 – a r – b)\). Comme \(r^n \neq 0\), cette quantité est nulle pour tout \(n\) si et seulement si \(r^2 – ar – b = 0\).

Cas complexe (\(\mathbb{K} = \mathbb{C}\)) :

• si l’équation caractéristique a deux racines distinctes \(r_1\) et \(r_2\), alors les solutions sont les suites \(u_n = \lambda\,r_1^n + \mu\,r_2^n\), avec \(\lambda, \mu \in \mathbb{C}\) ;
• si elle a une racine double \(r_0\), alors les solutions sont les suites \(u_n = (\lambda + \mu n)\,r_0^n\).

Dans le premier cas, \((r_1^n)\) et \((r_2^n)\) sont solutions d’après le lemme. Elles ne sont pas proportionnelles, car \(r_1 \neq r_2\). Elles forment donc une base de l’espace des solutions, qui est de dimension 2. Dans le second cas, on a \(a = 2 r_0\) et \(b = -r_0^2\). On vérifie alors que \((n r_0^n)\) est solution : \((n+2) r_0^{n+2} – 2r_0 (n+1) r_0^{n+1} + r_0^2\, n r_0^n = r_0^{n+2}(n + 2 – 2n – 2 + n) = 0\). Enfin, \((r_0^n)\) et \((n r_0^n)\) ne sont pas proportionnelles.

Cas réel (\(a, b\) réels, suites réelles) :

• si \(\Delta = a^2 + 4b > 0\), deux racines réelles \(r_1 \neq r_2\) et \(u_n = \lambda r_1^n + \mu r_2^n\) ;
• si \(\Delta = 0\), une racine double \(r_0\) et \(u_n = (\lambda + \mu n) r_0^n\) ;
• si \(\Delta < 0\), deux racines conjuguées \(\rho\,e^{\pm i\theta}\) et \(u_n = \rho^n\big(\lambda \cos(n\theta) + \mu \sin(n\theta)\big)\) ;

avec \(\lambda, \mu\) réels, fixés par \(u_0\) et \(u_1\).

Pour résoudre \(u_{n+2} = a u_{n+1} + b u_n\) : d’abord, écrire et résoudre \(r^2 – ar – b = 0\) ; ensuite, écrire la forme générale selon le signe de \(\Delta\) ; enfin, déterminer \(\lambda\) et \(\mu\) par un système de deux équations donné par \(u_0\) et \(u_1\). Vérifiez toujours le résultat sur \(u_2\).

La suite de Fibonacci vérifie \(F_0 = 0\), \(F_1 = 1\) et \(F_{n+2} = F_{n+1} + F_n\). L’équation \(r^2 – r – 1 = 0\) a pour racines \(\varphi = \frac{1 + \sqrt{5}}{2}\) et \(\psi = \frac{1 – \sqrt{5}}{2}\). Ainsi, \(F_n = \lambda \varphi^n + \mu \psi^n\). Les conditions \(\lambda + \mu = 0\) et \(\lambda \varphi + \mu \psi = 1\) donnent \(\lambda = -\mu = \frac{1}{\sqrt{5}}\). Par conséquent, \(F_n = \frac{\varphi^n – \psi^n}{\sqrt{5}}\) (formule de Binet).

Soit \(u_0 = u_1 = 1\) et \(u_{n+2} = u_{n+1} – \frac{1}{2} u_n\). L’équation \(r^2 – r + \frac{1}{2} = 0\) a pour racines \(\frac{1 \pm i}{2} = \frac{1}{\sqrt{2}}\,e^{\pm i\pi/4}\). Donc \(u_n = 2^{-n/2}\big(\lambda \cos\frac{n\pi}{4} + \mu \sin\frac{n\pi}{4}\big)\). On trouve \(\lambda = 1\), puis \(\frac{1}{2}(1 + \mu) = 1\), soit \(\mu = 1\).

Le module des racines règle le comportement asymptotique. Si toutes les racines sont de module strictement inférieur à 1, alors toute solution tend vers 0. En revanche, si une racine est de module strictement supérieur à 1, une solution générique n’est pas bornée.

Soit \(f : D \to \mathbb{R}\). Une partie \(I \subset D\) est stable par \(f\) si \(f(I) \subset I\), c’est-à-dire si \(\forall x \in I,\ f(x) \in I\).

Si \(I\) est stable par \(f\) et si \(u_0 \in I\), alors la relation \(u_{n+1} = f(u_n)\) définit une unique suite, et \(u_n \in I\) pour tout \(n \in \mathbb{N}\).

On raisonne par récurrence sur \(n\). D’abord, \(u_0 \in I\). Ensuite, si \(u_n\) est défini et appartient à \(I\), alors \(u_n \in D\). Donc \(u_{n+1} = f(u_n)\) est défini, et il appartient à \(f(I) \subset I\).

Sans intervalle stable, la suite peut ne pas exister. Par exemple, avec \(f(x) = \sqrt{x – 1}\) et \(u_0 = 5\), on obtient \(u_1 = 2\), puis \(u_2 = 1\), puis \(u_3 = 0\). Le terme \(u_4 = \sqrt{-1}\) n’est donc pas défini.

Soit \(I\) un intervalle stable par \(f\) et \(u_0 \in I\). Si \(f(x) – x \geq\, 0\) pour tout \(x \in I\), alors \((u_n)\) est croissante. Si \(f(x) – x \leq\, 0\) pour tout \(x \in I\), alors \((u_n)\) est décroissante.

Pour tout \(n\), on a \(u_{n+1} – u_n = f(u_n) – u_n\). Or \(u_n \in I\), donc cette différence a le signe de \(f – \mathrm{id}\) sur \(I\).

Soit \(I\) stable par \(f\) et \(u_0 \in I\).

• Si \(f\) est croissante sur \(I\), alors \((u_n)\) est monotone. Elle est croissante si \(u_1 \geq\, u_0\), et décroissante si \(u_1 \leq\, u_0\).
• Si \(f\) est décroissante sur \(I\), alors \(f \circ f\) est croissante sur \(I\). Par conséquent, les suites \((u_{2n})\) et \((u_{2n+1})\) sont monotones, de sens contraires.

Supposons \(f\) croissante et \(u_0 \leq\, u_1\). Si \(u_n \leq\, u_{n+1}\), alors \(f(u_n) \leq\, f(u_{n+1})\), soit \(u_{n+1} \leq\, u_{n+2}\). On conclut par récurrence. Si \(f\) est décroissante, \(f \circ f\) est croissante. De plus, \(u_{2n+2} = (f \circ f)(u_{2n})\) et \(u_{2n+3} = (f \circ f)(u_{2n+1})\). On applique donc le premier point à chacune des deux suites extraites. Enfin, si \(u_{2n} \leq\, u_{2n+2}\), alors \(u_{2n+1} = f(u_{2n}) \geq\, f(u_{2n+2}) = u_{2n+3}\) : les sens sont contraires.

Une suite récurrente n’est pas « de même monotonie que \(f\) ». Si \(f\) est croissante, \((u_n)\) peut être décroissante : tout dépend de la position de \(u_1\) par rapport à \(u_0\). Si \(f\) est décroissante, \((u_n)\) n’est en général pas monotone.

Un réel \(\ell\) est un point fixe de \(f\) si \(f(\ell) = \ell\). Graphiquement, c’est l’abscisse d’un point d’intersection de la courbe de \(f\) avec la droite \(y = x\).

Soit \((u_n)\) définie par \(u_{n+1} = f(u_n)\). Si \(u_n \to \ell\), si \(\ell\) appartient au domaine de \(f\) et si \(f\) est continue en \(\ell\), alors \(f(\ell) = \ell\).

Par continuité de \(f\) en \(\ell\) et par composition des limites, \(f(u_n) \to f(\ell)\). Or \(f(u_n) = u_{n+1}\), et \((u_{n+1})\) est une suite extraite de \((u_n)\). Donc \(u_{n+1} \to \ell\). Par unicité de la limite, on obtient \(f(\ell) = \ell\).

Si \(I = [\alpha, \beta]\) est un segment stable et si \(u_0 \in I\), alors tous les termes sont dans \(I\). Donc la limite éventuelle appartient aussi à \(I\), par passage à la limite dans les inégalités larges. C’est ainsi qu’on choisit le bon point fixe lorsqu’il y en a plusieurs.

Le théorème ne dit pas que la suite converge. Il affirme seulement que la limite, si elle existe, est un point fixe. Par ailleurs, l’hypothèse de continuité est indispensable. Par exemple, si \(f(x) = \frac{x}{2}\) pour \(x > 0\) et \(f(0) = 1\), la suite issue de \(u_0 = 1\) tend vers 0. Pourtant, \(f(0) = 1 \neq 0\).

Pour étudier \(u_{n+1} = f(u_n)\) :

1. étudier les variations de \(f\) et le signe de \(f(x) – x\), ce qui donne les points fixes ;
2. trouver un intervalle stable contenant \(u_0\) (souvent délimité par des points fixes) ;
3. en déduire la monotonie de \((u_n)\), ou celle de \((u_{2n})\) et \((u_{2n+1})\) ;
4. conclure par le théorème de la limite monotone, puis identifier la limite parmi les points fixes de l’intervalle ;
5. si la suite est croissante et qu’aucun point fixe ne convient, conclure que \(u_n \to +\infty\).

Soit \(f(x) = x^2\). Les points fixes sont 0 et 1, et \(f(x) – x = x(x – 1)\). Si \(u_0 \in [0, 1[\), l’intervalle \([0, 1[\) est stable et \(f(x) \leq\, x\) sur cet intervalle. La suite est donc décroissante et minorée par 0. Elle converge vers un point fixe de \([0, u_0]\), c’est-à-dire vers 0. Si \(u_0 > 1\), la suite est croissante. Si elle convergeait, sa limite \(\ell \geq\, u_0 > 1\) serait un point fixe : c’est impossible. Par conséquent, \(u_n \to +\infty\).

S’il existe \(k \in [0, 1[\) tel que \(|u_{n+1} – \ell| \leq\, k\,|u_n – \ell|\) pour tout \(n\), alors \(|u_n – \ell| \leq\, k^n\,|u_0 – \ell|\) et \(u_n \to \ell\).

Pour garantir \(|u_n – \ell| \leq\, \varepsilon\), il suffit que \(k^n M \leq\, \varepsilon\), où \(M\) majore \(|u_0 – \ell|\). Autrement dit, il suffit que

\[n \geq\, \frac{\ln(M/\varepsilon)}{\ln(1/k)}.\]

On prend donc le plus petit entier qui vérifie cette inégalité. Ce rang est suffisant, mais il n’est pas forcément optimal.

Pour \(u_{n+1} = \frac{u_n}{2} + 3\) et \(u_0 = 1\), on a exactement \(|u_n – 6| = 5 \cdot 2^{-n}\). Pour obtenir une erreur au plus \(10^{-6}\), il faut \(2^n \geq\, 5 \cdot 10^6\). Or \(2^{22} = 4\,194\,304\) et \(2^{23} = 8\,388\,608\). Ainsi, il faut et il suffit que \(n \geq\, 23\).

La méthode de Newton associée à \(g\) est la suite récurrente \(u_{n+1} = f(u_n)\), avec

\[f(x) = x – \frac{g(x)}{g^{\prime}(x)} \qquad (g^{\prime}(x) \neq 0).\]

Les points fixes de \(f\) sont exactement les zéros de \(g\).

Pour \(g(x) = x^2 – 2\), on obtient \(f(x) = \frac{1}{2}(x + \frac{2}{x})\). Un calcul direct donne

\[u_{n+1} – \sqrt{2} = \frac{(u_n – \sqrt{2})^2}{2\,u_n}.\]

Ainsi, l’erreur est élevée au carré à chaque étape : on parle de convergence quadratique. En pratique, le nombre de décimales exactes double environ à chaque itération. Avec \(u_0 = 2\), on trouve \(u_1 = \frac{3}{2}\), \(u_2 = \frac{17}{12}\) et \(u_3 = \frac{577}{408}\), déjà exact à \(3 \cdot 10^{-6}\) près.

La méthode de Newton exige un bon point de départ. Loin du zéro, ou près d’un point où \(g^{\prime}\) s’annule, la suite peut diverger. C’est pourquoi on commence souvent par localiser le zéro, par dichotomie par exemple, avant d’itérer.