Suites et formules récursives

Une suite est une liste ordonnée de nombres, où chaque élément a une place précise. On peut décrire une suite soit par une formule explicite, soit par une formule récursive.

Lorsqu’une suite est définie récursivement, le terme suivant dépend d’un ou de plusieurs termes précédents.

Exemple d’une suite récursive simple

On peut définir une suite où chaque terme est le double du précédent :

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

Ici $ \large a_{0} = 1 $ est le point de départ. D’après la formule, on obtient

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

Formule récursive

Dans une formule récursive, un terme est décrit à partir des précédents. Pour commencer, il faut connaître une ou plusieurs valeurs initiales, appelées conditions initiales.

Récurrence du premier ordre

Une récurrence du premier ordre signifie que chaque terme dépend uniquement du terme précédent. Un exemple est

$$ \large a_{n} = 3 \cdot a_{n-1}, \quad a_{0} = 2 $$

Ici, chaque terme est multiplié par 3 par rapport au précédent. La suite devient

$$ \large 2, \; 6, \; 18, \; 54, \ldots $$

Récurrence du deuxième ordre

Une récurrence du deuxième ordre signifie que chaque terme dépend des deux termes précédents. L’exemple le plus célèbre est la suite de Fibonacci :

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

Ici, chaque terme est la somme des deux précédents. La suite commence ainsi :

$$ \large 0, \; 1, \; 1, \; 2, \; 3, \; 5, \; 8, \; 13, \ldots $$

Il existe de nombreux autres exemples de récurrences du deuxième ordre. En voici un, où chaque terme est obtenu en multipliant le précédent par 2 puis en soustrayant l’avant-dernier :

$$ \large a_{n} = 2 \cdot a_{n-1} - a_{n-2}, \quad a_{0} = 1, \quad a_{1} = 2 $$

Si l’on remplace par les premières valeurs, on obtient :

$$ \large a_{2} = 3, \quad a_{3} = 4, \quad a_{4} = 5, \quad a_{5} = 6, \ldots $$

Dans ce cas, la récurrence produit une progression arithmétique simple, même si la formule initiale paraît plus compliquée.

Formule explicite

Ici, on peut en fait trouver une formule explicite qui décrit toute la suite directement :

$$ \large a_{n} = n + 1 $$

Cela montre que les formes récursives et explicites sont souvent étroitement liées. Une définition récursive apparemment complexe peut cacher une formule explicite très simple.

Terminologie

Dans le travail avec des formules récursives, certains concepts standards sont utilisés :

Conditions initiales : les premières valeurs qui initient la suite.
Ordre de récurrence : combien de termes précédents sont utilisés pour déterminer le suivant (par ex. premier ou deuxième ordre).
Base : les premiers pas de la définition sur lesquels le reste est construit.

Ces concepts apparaissent dans tous les types de définitions récursives et permettent de travailler plus systématiquement avec elles.

Résumé

Les formules récursives sont utiles pour décrire des structures où chaque nouveau terme découle des précédents. Elles donnent une image claire des relations entre les nombres, mais exigent de connaître les termes antérieurs pour continuer. Souvent, on peut ensuite trouver une formule explicite qui offre un moyen plus rapide de calculer directement.

Comprendre la différence entre récurrences du premier et du deuxième ordre, et leur relation avec les solutions explicites, est une première étape importante dans le travail avec des méthodes récursives.