Ouvrir le menu principal

Suite récurrente linéaire

(Redirigé depuis Récurrence linéaire)

En mathématiques, on appelle suite récurrente linéaire d’ordre p toute suite à valeurs dans un corps commutatif K (par exemple ou  ; on ne se placera que dans ce cas dans cet article) définie pour tout par une relation de récurrence linéaire de la forme

, , … sont p scalaires fixés de K ( non nul).

Une telle suite est entièrement déterminée par la donnée de ses p premiers termes et par la relation de récurrence.

Les suites récurrentes linéaires d’ordre 1 sont les suites géométriques.

L'étude des suites récurrentes linéaires d'ordre supérieur se ramène à un problème d'algèbre linéaire. L'expression du terme général d'une telle suite est possible pour peu qu'on soit capable de factoriser un polynôme qui lui est associé, appelé polynôme caractéristique ; le polynôme caractéristique associé à une suite vérifiant la relation de récurrence ci-dessus est :

Son degré est ainsi égal à l'ordre de la relation de récurrence. En particulier, dans le cas des suites d'ordre 2, le polynôme est de degré 2 et peut donc être factorisé à l'aide d'un calcul de discriminant. Ainsi, le terme général des suites récurrentes linéaires d'ordre 2, peut être exprimé en utilisant seulement les deux premiers termes, quelques valeurs constantes, quelques opérations élémentaires de l'arithmétique (addition, soustraction, multiplication, exponentielle) et les fonctions sinus et cosinus (si le corps des scalaires est le corps des réels). Une des suites de ce type est la célèbre suite de Fibonacci, qui peut s'exprimer à partir de puissances faisant intervenir le nombre d'or.

Suite récurrente linéaire d’ordre 1Modifier

Les suites récurrentes linéaires d'ordre 1 sont les suites géométriques.

Si la relation de récurrence est  , le terme général est  .

Suite récurrente linéaire d’ordre 2Modifier

a et b étant deux scalaires fixés de K avec b non nul, la relation de récurrence est

 

Les scalaires r tels que la suite   vérifie (R) sont les solutions de l’équation du second degré  . Le polynôme   est alors appelé le polynôme caractéristique de la suite. Son discriminant est  . Il faudra alors distinguer plusieurs cas, selon le nombre de racines du polynôme caractéristique.

Théorème[1] —  Le terme général d'une suite à valeurs dans K et vérifiant (R) est :

  1.   si   et   sont deux racines distinctes (dans K) du polynôme  ,
  2.   si   est racine double du polynôme  ,

avec   paramètres dans K déterminés par les deux premières valeurs de la suite.

Le cas 1 se produit par exemple si   et si le discriminant   est strictement positif, ou si   et  . De plus, si les deux racines   du polynôme   sont deux complexes conjugués   et  , alors le terme général d'une telle suite s'écrit également[1] :

  •   avec A et B paramètres dans K (  ou  , selon qu'on s'intéresse aux suites réelles ou complexes) déterminés par les deux premières valeurs de la suite.

Le cas 2 se produit lorsque   et alors, la racine double est  .

On ne perd rien à la généralité de la suite en supposant que celle-ci est définie sur tout et pas seulement à partir de  . En effet, l'étude d'une suite u qui n’est définie qu’à partir de   se ramène à celle de la suite v définie sur ℕ par  .

Identités remarquablesModifier

Si une suite u vérifie

 

alors, elle peut être étendue aux indices négatifs et reliée aux puissances de la matrice

 

(inversible puisque b ≠ 0) par :

 .

Ceci permet de montrer que pour v égale à u ou à toute autre suite vérifiant la même relation de récurrence (R) et pour tous entiers i, j, k, l et r[2],[3] :

 .

En particulier :

 .

Suite récurrente d’ordre pModifier

Sous-espace vectoriel de dimension pModifier

Si l'on appelle   la relation de récurrence :

pour tout entier n,  

et si l'on note  , l’ensemble des suites à valeurs dans K et vérifiant  , on démontre que   est un sous-espace vectoriel de l'espace des suites à valeurs dans K. Cela tient à la linéarité de la relation de récurrence.

De plus, ce sous-espace est de dimension p. En effet, il existe un isomorphisme d'espaces vectoriels entre   et   : à chaque suite u de  , on associe le p-uplet  . Il suffit alors de connaître une famille libre de p suites vérifiant  , l’ensemble   est alors engendré par cette famille libre.

Terme généralModifier

La recherche du terme général et des suites particulières s’effectue en travaillant sur  . À chaque suite   on associe la suite   définie par

 

La relation de récurrence sur   induit une relation de récurrence sur  

 
 

(A est la matrice compagnon du polynôme caractéristique de la suite).

Le terme général de la suite U est alors déterminé par[4]

 

Le problème semble alors terminé. Mais la réelle difficulté consiste alors à calculer  … On préfère déterminer une base de  .

Recherche d'une baseModifier

Le polynôme caractéristique de la matrice A est  . Ce n'est pas un hasard si on le retrouve pour caractériser les suites   vérifiant  .

On note f la transformation linéaire qui, à une suite   associe la suite   définie par  . La condition « u vérifie   » se traduit alors par P(f)(u) = 0. L'ensemble   est donc le noyau de P(f). Si le polynôme P est scindé sur K (ce qui est toujours vrai si K = ℂ), il s'écrit  , où   sont les racines de P et   leurs ordres de multiplicité respectifs. Le noyau de P(f) est alors la somme directe des noyaux des  . Il suffit donc de trouver une base de chacun de ces noyaux pour déterminer une base de   .

On peut montrer que toute suite de terme général   est élément du noyau de   pour peu que le degré de Q soit inférieur strictement à  . Cette démonstration se fait par récurrence sur  . Comme les suites  , pour j = 0 à  , forment une partie libre de   éléments[5], les suites  , pour j de 0 à   et i de 1 à k, forment une famille libre de   éléments de   (de dimension p) donc une base de  . Les éléments de   sont donc des sommes de suites dont le terme général est   avec degré de Q strictement inférieur à  .

Retour à la récurrence d'ordre 2Modifier

Si le polynôme caractéristique se scinde en   alors les polynômes Q sont de degré 0 et les éléments de   sont des suites dont le terme général est  .

Si le polynôme caractéristique se scinde en   alors les polynômes Q sont de degré 1 et les éléments de   sont des suites dont le terme général est  .

Notes et référencesModifier

  1. a et b Pour une démonstration, voir par exemple le chapitre « Récurrence affine d'ordre 2 » sur Wikiversité.
  2. (en) Robert C. Johnson, « Fibonacci numbers and matrices », sur Université de Durham, , p. 40 (A.10).
  3. Pour une démonstration, voir par exemple l'exercice corrigé correspondant sur Wikiversité.
  4. Jean-Marie Monier, Algèbre et géométrie PC-PSI-PT : Cours, méthodes et exercices corrigés, Dunod, , 5e éd. (lire en ligne), p. 125.
  5. En réalité, ce résultat n'est vrai que si  , mais le cas d'une racine nulle se traite aisément par décalage d'indice.

Articles connexesModifier