Suites récurrentes

Une suite récurrente est définie par la donnée de $u_0\in \mathbb{R}$ et la relation de récurrence

$$u_{n+1}=F(u_n)\;.$$

La suite est celle des itérés successifs de l'application $F$ à partir de $u_0$ :

$$u_1=F(u_0), u_2=F(F(u_0))=F\circ F(u_0), u_3=F\circ F\circ F(u_0),\ldots$$

On notera $F^{\circ n}$ la composée de $F$ avec elle-même $n$ fois :

$$u_n = F^{\circ n}(u_0) = F\circ F\circ\ldots\circ F(u_0)\;.$$

Il existe un moyen simple de visualiser les premiers termes de la suite $(F^{\circ n}(u_0))$ à partir du graphe de la fonction $F$, représenté dans le plan. Portons $u_0$ en abscisse et traçons le segment vertical allant de $(u_0,0)$ à $(u_0,F(u_0))$. Traçons ensuite le segment horizontal rejoignant la première bissectrice, de $(u_0,F(u_0))$ à $(F(u_0),F(u_0))$. L'abscisse du nouveau point est $u_1$. On itère alors le procédé en traçant alternativement des segments verticaux et horizontaux. On obtient ainsi une sorte de «toile d'araignée» (figure 2).

Figure: Représentation d'itérés successifs par une «toile d'araignée».

Cette représentation graphique suffit pour se faire une idée du comportement qualitatif d'une suite récurrente réelle. Elle permet de détecter les convergences ou divergences ainsi que les comportements oscillants. Pour étudier la suite $(u_n)$, le premier travail consiste à identifier les limites possibles. Si la suite $(u_n)$ converge vers $l$, alors la suite $(u_{n+1})$, qui est une suite extraite, converge vers la même limite $l$. Donc, si $F$ est continue en $l$ (définition 7), on doit avoir :

$$l=F(l)\;.$$

On dit que $l$ est un point fixe de $F$, car si $u_0=l$, alors la suite est constante. Il peut se faire que $F$ ait plusieurs points fixes. Le comportement de la suite $u_n$ (monotonie, convergence ou non vers un point fixe), dépend de $u_0$. Plutôt qu'une discussion générale, nous allons traiter l'exemple historique sans doute le plus célèbre : les rapports des nombres de Fibonacci. Les nombres de Fibonacci sont définis par $a_0=1$, $a_1=1$, et pour $n\geqslant 0$,

$$a_{n+2}=a_{n+1}+a_{n}\;.$$

Voici les $20$ premiers.

$$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765$$

La suite $(a_n)$ est une suite croissante d'entiers, elle ne s'annule pas. Pour $n\geqslant 1$, posons $u_n=a_{n+1}/a_n$. La suite $(u_n)$ vérifie $u_0=1$, et pour $n\geqslant 1$ :

$$u_{n+1} = 1+\frac{1}{u_n}\;.$$

C'est une récurrence du type $u_{n+1}=F(u_n)$, avec

$$F(x)=1+\frac{1}{x}\;.$$

La figure 2 représente les premières valeurs de $u_n$ en toile d'araignée. Pour étudier $(u_n)$, commençons par chercher les points fixes de l'application $F$, en résolvant l'équation

$$1+\frac{1}{x}=x\;\Longleftrightarrow\; x^2-x-1=0$$    et $$x\neq 0\;.$$

L'équation a deux solutions,

$$\phi = \frac{1+\sqrt{5}}{2}$$   et$$\quad -\frac{1}{\phi} = \frac{1-\sqrt{5}}{2}\;.$$

La première solution, $\phi\simeq 1.618$, est le célèbre nombre d'or ; on le retrouve (paraît-il) un peu partout, des pyramides d'Egypte aux coquilles de nautiles en passant par la Joconde. Comme $u_n$ reste positif, la seule limite possible pour $(u_n)$ est $\phi$. Nous allons démontrer les propriétés suivantes.

Proposition 4    

1. La suite des termes pairs $(u_{2k})$ est croissante
2. La suite des termes impairs $(u_{2k+1})$ est décroissante
3. Chacune de ces deux suites converge vers $\phi$ (elles sont adjacentes).

En d'autres termes, les termes $u_n$ approchent $\phi$, alternativement à gauche et à droite. Démonstration : En soustrayant les deux équations

$$u_{n+1}=1+\frac{1}{u_n}$$   et$$\quad \phi = 1+\frac{1}{\phi}\;,$$

on obtient :

$$u_{n+1}-\phi = \frac{\phi-u_n}{u_n\phi}\;.$$

Comme $u_n>0$, on en déduit que $u_{n+1}-\phi$ et $u_{n}-\phi$ sont de signe opposé. Puisque $u_0<\phi$, on obtient par récurrence que pour tout $k\geqslant 1$ :

$$u_{2k}<\phi<u_{2k+1}\;.$$

On peut aussi exprimer $u_{n+2}-\phi$ en fonction de $u_n-\phi$ :

$$u_{n+2}-\phi = \frac{u_n-\phi}{\phi^2 (u_n+1)}\;.$$

Or $u_n>0$, $\phi>1$, $u_0<\phi$ et $u_1>\phi$. On en déduit par récurrence que pour les termes pairs :

$$0<\phi-u_{2k+2}< \frac{1}{\phi^2}(\phi-u_{2k}) <\frac{1}{\phi^{2k+2}}(\phi-u_0)\;.$$

Pour les termes impairs :

$$0<u_{2k+3}-\phi< \frac{1}{\phi^{2}}(u_{2k+1}-\phi) <\frac{1}{\phi^{2k+2}}(u_1-\phi)\;.$$

Donc la suite des termes pairs est croissante et la suite des termes impairs décroissante. Mais de plus :

$$\phi-u_{2k} = O(\phi^{-2k})$$   et$$\quad u_{2k+1}-\phi = O(\phi^{-2k})\;.$$

Les deux suites $(u_{2k})$ et $(u_{2k+1})$ convergent vers $\phi$, car $\phi>1$, donc $\phi^{-2k}$ tend vers 0.$\square$