Les suites et séries/Les suites récurrentes (cas général)

Dans le premier chapitre, nous avons vu qu'il existe deux manières de décrire une suite, l'une donnant les suites paramétrées et l'autre les suites récurrentes (les deux n'étant pas exclusives). Dans ce chapitre, nous allons parler des suites récurrentes dans le cas général. Celles-ci sont très nombreuses et font clairement partie des plus étudiées, loin devant les simples suites paramétrées. Dans les grandes lignes, il existe deux choses importantes à propos des suites récurrentes : leur trouver une expression paramétrée et étudier leur comportement quand le rang grandit. Trouver leur limite, si elle existe, est aussi intéressant pour certaines suites récurrentes. Pour rappel, les suites récurrentes sont définies pour tout rang n par une fonction de récurrence, comme suit :

$u_{n}=f(u_{n-1},u_{n-2},u_{n-3},...,u_{2},u_{1},u_{0})$

Comme on le voit, ces suites sont intégralement définies par une fonction, qui détermine la relation de récurrence. Étudier ces suites, c'est simplement étudier la fonction qui les définit : est-elle croissante, décroissante, stationnaire au-delà d'un point, continue, dérivable, linéaire, etc. Par exemple, on peut savoir si la suite est croissante ou décroissante en calculant la dérivée de la fonction f : la suite est croissante si cette dérivée est positive, décroissante si elle est négative, constante si elle est nulle. Malheureusement, il n'existe pas de méthode à tout faire qui puisse traiter toute suite récurrente existante et nous allons donc nous rabattre sur des cas particuliers de suites récurrentes.

Les concepts de base des suites récurrentes du premier ordre

Dans ce chapitre et le suivant, nous allons étudier deux cas particuliers : les suites récurrentes linéaires et certaines suites non-linéaires. Nous verrons les suites récurrentes linéaires dans le prochain chapitre. Dans ce chapitre, nous allons nous intéresser aux suites définies par une relation de la forme :

$u_{n+1}=f(u_{n})$

Dans ce qui suit, la fonction f est choisie pour avoir quelques propriétés qui simplifient l'analyse : elle est supposée continue, éventuellement dérivable.

Les intervalles stables

On pourrait croire que choisir une relation de récurrence $u_{n+1}=f(u_{n})$ et une valeur $u_{0}$ suffise à donner une suite. Mais il existe cependant quelques exceptions qui viennent compliquer la situation. Par exemple, regardez l'exemple suivant :

${\begin{cases}u_{0}=2\\u_{n+1}={\frac {1}{u_{n}-1}}\end{cases}}$

Les termes $u_{0}$ et $u_{1}$ existent, mais le terme $u_{2}$ non ! Il suffit de faire les calculs pour s'en rendre compte.

$u_{0}=2$

$u_{1}={\frac {1}{2-1}}=1$

$u_{2}={\frac {1}{1-1}}={\frac {1}{0}}\ldots$

Le calcul donne une belle division par zéro qui stoppe net la progression de la suite. Le problème est alors que les opérations utilisées pour le calcul de la fonction ne donnent pas un nombre, alors qu'on s'attend à ce que ce soit le cas dans une suite numérique. On pourrait trouver d'autres exemples du même genre , mais pour des suites plus complexes, voire des suites qui ne sont pas numériques. Et bien évidemment, les problèmes peuvent survenir pour d'autres raisons que des divisions par zéro : que pensez-vous d'une suite dont un terme donnerait $0^{0}$ ? Pour comprendre quand ce genre de problème peut arriver, nous devons introduire la notion d'intervalle stable. Un intervalle stable est défini comme suit :

Soit une fonction $f(x)$ et un intervalle $I$, ce dernier est un intervalle stable si $f(I)\in I$.

Cette définition nous donne une explication assez intuitive des problèmes mentionnés plus haut. Tout vient du fait que la fonction donne un résultat qui n'est ni un entier ni un réel, alors que la suite récurrente associée est censée être une suite d'entiers ou de réels. Pour reprendre l'exemple cité plus haut de la suite définie par $u_{n+1}={\frac {1}{u_{n}-1}}$. Le problème est que certains opérandes vont donner une division par zéro : les opérandes de la fonction sont censés être des entiers ou des réels ($u_{n}\in \mathbb {R}$), mais ce n'est pas le cas du résultat ! L'intervalle utilisé n'est pas stable, ce qui permet à ces problèmes de se manifester (ou du moins, ces problèmes peuvent potentiellement se manifester, vu que certains opérandes ne posent pas de problèmes).

Les suites récurrentes associées

Maintenant, prenons les deux hypothèses suivantes :

• la relation de récurrence est $u_{n+1}=f(u_{n})$ ;
• le terme $u_{0}$ appartient à un intervalle stable par f, que nous noterons I.

Alors une simple relation de récurrence nous permet de dire que la suite existe, qu'elle est définie pour tout entier n. Intuitivement, cela s'explique par le fait qu'à chaque passage par la fonction, le résultat sera bien dans l'intervalle I. Une véritable démonstration demande simplement de faire une démonstration par récurrence triviale. La suite alors définie est appelée la suite récurrente associée à f.

Si une fonction possède un intervalle stable fini (borné), alors la suite récurrente associée l'est tout autant. Ses termes sont dans l'intervalle stable, par définition, ce qui rend la suite bornée entre la borne inférieure et supérieure de l'intervalle. Par exemple, si une fonction $f$ a [0,1] pour intervalle stable, on sait que la suite récurrente associée est bornée entre 0 et 1. Là où les choses deviennent intéressantes, c'est que cette propriété évidente permet de déterminer rapidement si la suite associée converge ou non. Le cas le plus simple est celui où la suite associée est monotone (croissante ou décroissante). Dans ce cas, on sait que la limite va converger et on peut calculer sa limite facilement : c'est tout simplement la borne supérieure ou inférieure de l'intervalle (selon que la suite est croissante ou décroissante). Aussi, ne vous étonnez pas si beaucoup de démonstrations sur les suites récurrentes utilisent les théorèmes de convergence des fonctions monotones.

Les points fixes d'une suite

Ce qui va nous intéresser chez ces suites est l'étude des points fixes de la fonction f. Par point fixe on entend un nombre x tel que :

$x=f(x)$

Exemple de fonction avec plusieurs points fixes. On voit que son graphe coupe la ligne identité en plusieurs points fixes.

Évidemment, toutes les fonctions n'ont pas de point fixe, bien que cela soit quand même assez courant.

On peut trouver les points fixes d'une fonction en regardant son graphe. Formellement, les points fixes sont ceux où le graphe de la fonction $y=f(x)$ coupe la droite identité ($y=x$).

Évidemment, toutes les fonctions n'ont pas de point fixe et il n'y a alors aucun point d'intersection entre le graphe de la fonction et la droite identité. À l'inverse, une fonction peut aussi avoir plusieurs points d'intersection, et donc plusieurs points fixes, comme le montre le graphe ci-contre. On peut se demander si les fonctions admettant au moins un point fixe sont courantes ou non. Eh bien c'est le cas : toute fonction continue définie sur un intervalle stable admet au moins un point fixe. Cette propriété capture un grand nombre de fonctions, y compris des fonctions courantes comme les puissances, les logarithmes, l'exponentielle, etc.

Démonstration

On part d'une fonction $f(x)$ définie sur un intervalle stable $I=[a;b]$. On souhaite démontrer qu'il existe un point pour lequel $x=f(x)$, ce qui se reformule comme suit : $x-f(x)=0$. Considérons donc la fonction $g(x)=x-f(x)$. On déduit facilement que la fonction est continue sur l'intervalle $I=[a;b]$, cette propriété étant héritée de la fonction $f(x)$. Maintenant, regardons ce qui se passe aux bords $a$ et $b$ de l'intervalle. Vu que $g(a)\in I$ et $g(b)\in I$, on a : $g(a)=a-f(a)\leq 0$ $g(b)=b-f(b)\geq 0$ D’après le théorème des valeurs intermédiaires, on déduit que $g(x)$ doit s'annuler en une valeur précise de $x$. Ce qu'il fallait démontrer.

Les points périodiques d'une suite

Les points périodiques sont une sorte de généralisation des points fixes, la différence étant que la fonction est appliquée plusieurs fois au lieu d'une seule pour les points fixes. Par exemple, prenons le cas d'un point périodique pour lequel une fonction est appliquée deux fois. On a alors :

$x=f(f((x))$

En toute généralité, un point périodique est une valeur x telle que :

$x=f_{n}(x)$, où $f_{n}(x)=f(f(f(f(f(f(...(x))))))$ avec f appliquée sur elle-même $n$ fois.

Si $f$ possède un ou plusieurs points périodiques, alors la suite associée appartient à une classe de suite particulière : les suites périodiques ou quasi-périodiques. Si on omet les suites constantes ou stationnaires, aucune suite périodique ou ultimement périodique n'a de point fixe vers lequel elles peuvent converger. Ce qui signifie que toute suite (ultimement) périodique de période > 1 diverge.

La convergence d'une suite récurrente associée

La présence de points fixes fait que la suite peut devenir stationnaire (constante au-delà d'un certain rang). Il suffit qu'il existe un rang $n$ tel que $u_{n}=x$ : tous les rangs supérieurs donneront une sous-suite stationnaire. Mais ce qui est intéressant est que cela permet de déterminer la limite de la suite si celle-ci converge. En effet, on peut démontrer que la limite d'une suite récurrente est aussi un cas particulier de point fixe.

La limite, si elle existe, est un point fixe

Si une suite récurrente associée possède une limite $l$, alors cette limite est un des points fixes de f. En clair, on a : $l=f(l)$.

Démonstration

Partons de la relation de récurrence d'une suite, définie comme suit : $u_{n+1}=f(u_{n})$ Passons à la limite quand $n$ tend vers l'infini : $\lim _{n\rightarrow \infty }u_{n+1}=\lim _{n\rightarrow \infty }f(u_{n})$ On peut alors écrire : $\lim _{n\rightarrow \infty }u_{n+1}=f\left(\lim _{n\rightarrow \infty }u_{n}\right)$ Les deux limites sont égales à la limite de la suite, par définition. Si on note $l$ la limite de la suite, on a : $l=f(l)$ Ce qui nous dit que la limite $l$ est bien un point fixe.

Faisons quelques remarques, histoire de bien comprendre la portée de ce résultat.

1. On doit s'assurer que la suite converge pour utiliser ce théorème. Il existe en effet des suites qui divergent, mais qui admettent quand même un ou plusieurs points fixes. Trouver les points fixes d'une fonction ne suffit pas à dire que la suite récurrente associée converge vers ce point fixe : il faut encore prouver que la suite converge effectivement. Dit autrement : l'existence d'un point fixe est une condition nécessaire, mais pas suffisante pour la convergence. Par contre, on sait que la réciproque est vraie : si la fonction $f$ n'a pas de point fixe, alors la suite récurrente associée ne converge pas. L'inexistence d'un point fixe implique de facto la divergence. Pour donner un exemple, la fonction $f(x)={\sqrt {1+x^{2}}}$ n'a pas de point fixe, ce qui fait que toute suite définie par $u_{n+1}={\sqrt {1+{u_{n}}^{2}}}$ ne converge pas.
2. Le point fixe peut ne s'exprimer que pour certains $u_{0}$ bien précis, qui sont les seuls à faire converger la fonction. Par exemple, la suite définie par $u_{n+1}={\frac {1}{u_{n}}}$ ne converge que si le premier terme vaut 1 et diverge systématiquement sinon.
3. Un autre problème est le cas où la fonction f a plusieurs points fixes. Dans ce cas, on sait que la limite de la suite est un de ces points fixes, mais on ne sait pas lequel. Pour en donner un exemple, prenons la suite définie par la relation suivante (un exemple de suite logistique, dont nous reparlerons plus tard) : $u_{n+1}={\frac {3}{2}}u_{n}(1-u_{n})$. Cette suite possède deux points fixes : 0 et 1/3. La limite, si elle existe, ne peut être qu'un de ces deux points fixes, mais on ne sait pas l'avance lequel. Pour cet exemple, la suite converge effectivement et sa limite est de 1/3, mais l'analyse des points fixes seule ne nous permet pas de le déduire.

Les points précédents sont assez importants et font que la découverte d'un point fixe ne suffit pas à déterminer la limite d'une suite récurrente. Il faut d'abord s'assurer que la suite converge effectivement, avant de déterminer quel point fixe est le bon. Dans les démonstrations qui suivront, nous aurons à respecter ces deux étapes, dans cet ordre. D'abord on prouvera la convergence, avant de dire quel est le point fixe qui sert de limite. Pour cette seconde étape, il arrivera qu'on prouve que la fonction ne dispose que d'un seul point fixe, ce qui rend la tâche assez aisée.

Les différents types de points fixes

On peut classer les points fixes d'une fonction en deux types, selon la manière dont la limite converge vers ce point fixe.

• Avec un point fixe répulsif, la suite ne converge vers un point fixe $l$ que si elle est constante et égale à $l$ au-delà d'un certain rang. En clair, la suite doit non seulement être stationnaire, mais les termes de sa portion constante doivent être égaux à $l$.
• Avec un point fixe attractif, ce n'est pas nécessairement le cas : la suite peut converger vers $l$ progressivement, sans pour autant être stationnaire. Un point attractif $a$ cause la convergence de toutes les suites construites avec la fonction f, sous condition que le premier terme soit suffisamment proche de $a$.

Ils se distinguent par la valeur absolue de la dérivée de la fonction $f$, $|f'(x)|$, selon qu'elle est inférieure, supérieure ou égale à 1.

• Si $|f'(x)|>1$, les points fixes de la suite sont répulsifs ;
• Si $|f'(x)|<1$, les points fixes de la suite sont attractifs ;
• Si $|f'(x)|=1$, la suite peut converger ou non vers ses points fixes, qui peuvent être autant attractifs que répulsifs.

Un exemple : la suite de Héron

Dans la suite de ce chapitre, nous allons étudier quelques exemples emblématiques de suites récurrentes de premier ordre. Pour commencer, nous allons étudier un exemple classique de suite récurrente : la suite de Héron, définie par :

$u_{n+1}={\frac {1}{2}}\left(u_{n}+{\frac {A}{u_{n}}}\right)$, avec $A$ un nombre constant positif.

Voici une autre formulation équivalente, qui nous sera utile par la suite :

$u_{n+1}={\frac {1}{2}}{\frac {u_{n}^{2}+A}{u_{n}}}={\frac {u_{n}^{2}+A}{2u_{n}}}$

Le premier terme $u_{0}$ est choisi plus ou moins arbitrairement, mais cela ne change pas grand-chose à sa limite. Dans ce qui va suivre, nous allons étudier la convergence de cette suite et démontrer qu'elle converge vers ${\sqrt {A}}$. Nous allons utiliser pour cela quelques arguments, dont l'étude du point fixe de cette suite.

Avant toute chose, on peut donner l'intuition qui se cache derrière cette suite, expliquer pourquoi elle converge vers ${\sqrt {A}}$. Pour comprendre pourquoi, imaginons que l'on choisisse un premier terme $u_{0}$ tel que $u_{0}<{\sqrt {A}}$. Dans ce cas, le terme ${\frac {A}{u_{n}}}$ sera tel que : ${\frac {A}{u_{n}}}>{\sqrt {A}}$. Le premier terme est donc inférieur à la racine carrée, tandis que le second est supérieur. On peut appliquer le même raisonnement avec un premier terme tel que $u_{0}>{\sqrt {A}}$. Pour obtenir une meilleure approximation de ${\sqrt {A}}$, on peut prendre la moyenne des deux termes. C'est ce que fait la relation de récurrence : c'est la moyenne de deux termes $u_{n}$ et ${\frac {A}{u_{n}}}$. Il suffit ensuite d'itérer ce calcul de moyenne avec l'approximation obtenue, le raisonnement précédent valant pour toutes les étapes. Ce raisonnement intuitif ne vaut cependant pas une démonstration en bonne et due forme, chose que nous allons faire dans ce qui suit.

Avant d'utiliser les points fixes de cette suite, nous devons avoir vérifié si celle-ci converge effectivement. On pourrait imaginer un cas où la suite ne converge pas, ce qui rendrait l'utilisation du point fixe inutile. Il nous faut donc démontrer que la suite de Héron converge, avant de crier victoire. Heureusement, cette démonstration est très simple, vu que la suite est monotone. On peut alors utiliser les théorèmes vus dans le chapitre sur les limites pour dire si elle converge ou non.

Preuve de la monotonie de la suite de Héron

Pour commencer, vérifions si la suite est croissante, décroissante ou constante. Pour cela, calculons simplement le terme $u_{n+1}-u_{n}$ :

$u_{n+1}-u_{n}={\frac {1}{2}}\left(u_{n}+{\frac {A}{u_{n}}}\right)-u_{n}$

Développons et réarrangeons les termes :

$u_{n+1}-u_{n}=\left[{\frac {1}{2}}u_{n}-u_{n}\right]+{\frac {1}{2}}{\frac {A}{u_{n}}}$

Simplifions :

$u_{n+1}-u_{n}={\frac {1}{2}}{\frac {A}{u_{n}}}-{\frac {1}{2}}u_{n}$

$u_{n+1}-u_{n}={\frac {1}{2}}\left({\frac {A}{u_{n}}}-u_{n}\right)$

Multiplions par $u_{n}$ :

$u_{n+1}-u_{n}={\frac {1}{2}}\left(A-{u_{n}}^{2}\right)$

Le terme de droite est nul si $u_{n}={\sqrt {A}}$, positif quand $u_{n}<{\sqrt {A}}$ et négatif avec $u_{n}>{\sqrt {A}}$. La suite est donc constante si $u_{n}={\sqrt {A}}$, croissante quand $u_{n}<{\sqrt {A}}$ et décroissante avec $u_{n}>{\sqrt {A}}$. Reste enfin à trouver des minorants et des majorants à la suite.

Les minorants et majorants de la suite

Pour finir la démonstration, il nous reste à trouver des minorants et des majorants à la suite. Il se trouve que, quel que soit le premier terme, tous les termes suivants de la suite seront tels que $x_{n}\geq {\sqrt {A}}$, ou encore $x_{n}-{\sqrt {A}}\geq 0$. Pour simplifier les calculs, nous allons calculer le carré de l'inégalité précédente, à savoir :

$x_{n+1}^{2}-A$

On remplace $x_{n+1}$ par sa valeur déterminée par récurrence. Cela signifie que les calculs qui vont suivre ne seront valables qu'au-delà du premier rang, le premier terme n'étant pas concerné.

$\left({\frac {u_{n}^{2}+A}{2u_{n}}}\right)^{2}-A$

Développons le terme au carré :

$\left({\frac {u_{n}^{4}+A^{2}+2Au_{n}^{2}}{4u_{n}^{2}}}\right)-A$

Mettons au même dénominateur :

$\left({\frac {u_{n}^{4}+A^{2}+2Au_{n}^{2}}{4u_{n}^{2}}}\right)-{\frac {4u_{n}^{2}A}{4u_{n}^{2}}}$

Factorisons :

${\frac {u_{n}^{4}+A^{2}-2Au_{n}^{2}}{4u_{n}^{2}}}$

En faisant appel à une identité remarquable, on trouve :

$\left({\frac {u_{n}^{2}-A}{2u_{n}}}\right)^{2}$

Vu que cette expression est un carré, elle est toujours positive ou nulle. Ce qu'il fallait démontrer.

$\left({\frac {u_{n}^{2}-A}{2u_{n}}}\right)^{2}\geq 0$

Cette inégalité n'étant qu'une reformulation de l'inégalité $x_{n}-{\sqrt {A}}\geq 0$, on peut en déduire que pour tout rang au-delà du premier terme : $x_{n}\geq {\sqrt {A}}$. La suite est donc minorée par ${\sqrt {A}}$ au-delà du premier rang. Sachant qu'on a démontré au-dessus que la suite est alors décroissante, on en déduit qu'elle converge. La suite de Héron converge donc vers la racine carrée du nombre A.

Le point fixe de la suite de Héron

D'après ce qu'on a vu en introduction, on sait que la limite de la suite de Héron est un point fixe de la fonction de récurrence. Calculons donc la valeur de ce point fixe, définit par :

$l={\frac {1}{2}}\left(l+{\frac {A}{l}}\right)$

Multiplions par $2l$ :

$2l^{2}=l^{2}+A$

En isolant A et en prenant la racine carrée, on trouve :

$l={\sqrt {A}}$

Ce résultat nous dit que si cette suite converge, elle converge vers ${\sqrt {A}}$.