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 :
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 :
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 formula_2 et une valeur formula_4 suffise à donner une suite. Mais il existe cependant quelques exceptions qui viennent compliquer la situation. Par exemple, regardez l'exemple suivant :
Le terme formula_4 et formula_7 existent, mais le terme formula_8 non ! Il suffit de faire les calculs pour s'en rendre compte.
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 formula_12 ? 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 :
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 formula_16. 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 (formula_17), 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 :
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 formula_20 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 :
É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 formula_22 coupe la droite identité (formula_23).
É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.
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 :
En toute généralité, un point périodique est une valeur x telle que :
Si formula_20 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 formula_27 tel que formula_30 : 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 formula_31, alors cette limite est un des points fixes de f. En clair, on a : formula_32.
Faisons quelques remarques, histoire de bien comprendre la portée de ce résultat.
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.
Ils se distinguent par la valeur absolue de la dérivée de la fonction formula_20, formula_46, selon qu'elle est inférieure, supérieure ou égale à 1.
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 :
Voici une autre formulation équivalente, qui nous sera utile par la suite :
Le premier terme formula_4 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 formula_54. 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 formula_54. Pour comprendre pourquoi, imaginons que l'on choisisse un premier terme formula_4 tel que formula_57. Dans ce cas, le terme formula_58 sera tel que : formula_59. 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 formula_60. Pour obtenir une meilleure approximation de formula_54, 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 formula_62 et formula_58. 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 avaoir vérifier 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 formula_64 :
Développons et réarrangeons les termes :
Simplifions :
Multiplions par formula_62 :
Le terme de droite est nul si formula_71, positif quand formula_72 et négatif avec formula_73. La suite est donc constante si formula_71, croissante quand formula_72 et décroissante avec formula_73. 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 formula_77, ou encore formula_78. Pour simplifier les calculs, nous allons calculer le carré de l'inégalité précédente, à savoir :
On remplace formula_80 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é.
Développons le terme au carré :
Mettons au même dénominateur :
Factorisons :
En faisans appel à une identité remarquable, on trouve :
Vu que cette expression est un carré, elle est toujours positive ou nulle. Ce qu'il fallait démontrer.
Cette inégalité n'étant qu'une reformulation de l'inégalité formula_78, on peut en déduire que pour tout rang au-delà du premier terme : formula_77. La suite est donc minorée par formula_54 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 :
Multiplions par formula_91 :
En isolant A et en prenant la racine carrée, on trouve :
Ce résultat nous dit que si cette suite converge, elle converge vers formula_54.