Relations de récurrence linéaires

Bonjour,

Dans notre leçon précédente, nous avons vu comment la formule du binôme de Newton permet de trouver une forme close pour le développement de $(a + b)^{n}$ . Cette démarche peut être vue comme la résolution d'une relation de récurrence simple du premier ordre, $S_{n} = (a + b) S_{n - 1}$ . Nous allons aujourd'hui généraliser cette approche pour résoudre une classe beaucoup plus large et fondamentale de récurrences : les relations de récurrence linéaires à coefficients constants.

L'objectif de cette leçon est de vous apprendre à résoudre les relations de récurrence linéaires à coefficients constants, dans le cas homogène comme dans le cas non homogène. Cette compétence est absolument centrale en informatique, notamment pour analyser la complexité temporelle d'algorithmes récursifs qui ne suivent pas le schéma "diviser pour régner" résolu par le théorème maître.

1. Structure des solutions et cas homogène

Commençons par définir précisément notre objet d'étude.

[PDF] Chapitre 7: récurrences - Introduction à la théorie de l'informatique

Ce document du cours d'introduction à la théorie de l'informatique de l'Université de Liège pose les définitions formelles. Il est important de bien distinguer le cas homogène du cas général (non homogène).

Lisez la diapositive intitulée "R´ecurrences lin´eaires" (page 371). Retenez la forme générale d'une récurrence linéaire homogène et celle d'une récurrence linéaire générale (qui inclut un terme additionnel g(n)).

Une récurrence est dite homogène si chaque terme est une combinaison linéaire des termes précédents. Pour une récurrence d'ordre 2, la forme type est :
$u_{n + 2} = a u_{n + 1} + b u_{n}$

Une idée fondamentale, digne de l'esprit de l'agrégation, est de ne pas voir ceci comme une simple équation à "résoudre", mais de comprendre la structure de l'ensemble de ses solutions.

La vidéo suivante expose brillamment cette structure en utilisant des concepts d'algèbre linéaire.

[EM#3] Suites récurrentes linéaires d'ordre 2 (Démonstration)

Cette vidéo de la chaîne "Øljen – Les maths en finesse" va au-delà de la simple recette de cuisine. Elle explique pourquoi la méthode fonctionne en montrant que l'ensemble des suites solutions forme un espace vectoriel de dimension 2.

Regardez la section allant de 00:58 à 04:33. L'auteur y démontre que l'ensemble des suites vérifiant la récurrence est le noyau d'un endomorphisme, et qu'il est isomorphe à \mathbb{R}^2. Cela justifie pourquoi il suffit de trouver deux solutions de base non colinéaires pour décrire toutes les autres.

Puisque l'espace des solutions est de dimension 2, notre stratégie est de trouver une base de cet espace. L'approche la plus naturelle est de chercher des solutions de la forme de suites géométriques, $u_{n} = r^{n}$ , car elles sont les plus simples à manipuler.

En substituant $u_{n} = r^{n}$ dans la récurrence, on obtient :
$r^{n + 2} = a r^{n + 1} + b r^{n}$
En supposant $r \neq = 0$ , on peut diviser par $r^{n}$ pour obtenir l'équation caractéristique :
$r^{2} - a r - b = 0$

La résolution de cette équation du second degré détermine la forme des solutions. La vidéo suivante détaille la méthode pour les trois cas possibles du discriminant $Δ$ .

[EM#3] Suites récurrentes linéaires d'ordre 2 (Démonstration)

Nous continuons avec la même vidéo, qui expose de manière très claire et rigoureuse la résolution dans chaque cas.

Regardez les sections suivantes, qui correspondent aux trois cas : Cas \Delta > 0 (07:35 - 09:35) : Deux racines réelles distinctes r_1, r_2. La solution générale est u_n = \lambda r_1^n + \mu r_2^n. Cas \Delta = 0 (09:35 - 12:07) : Une racine réelle double r_0. La solution générale est u_n = (\lambda + \mu n)r_0^n. Portez une attention particulière à l'intuition de la "suite géométrique dérivée" pour justifier le terme en n r_0^n. Cas \Delta < 0 (12:07 - 14:58) : Deux racines complexes conjuguées \rho e^{\pm i\theta}. La solution générale réelle est u_n = \rho^n(\lambda \cos(n\theta) + \mu \sin(n\theta)).

Pour résumer la méthode de résolution du cas homogène :

Solving Linear Recurrence Relations with Constant Coefficients — Ce tableau synthétise les formes de la solution générale pour une récurrence homogène d'ordre 2, en fonction des racines de l'équation caractéristique.

Une fois la forme générale $u_{n}$ obtenue, les constantes $λ$ et $μ$ sont déterminées en résolvant un système de deux équations à deux inconnues, obtenu grâce aux conditions initiales (généralement $u_{0}$ et $u_{1}$ ).

Solving Linear Homogeneous Recurrence Relations Example — Cet exemple illustre la méthode complète pour un cas avec racine double, de l'équation caractéristique à la détermination des constantes avec les conditions initiales.

2. Le cas non homogène

Considérons maintenant le cas général, ou non homogène, d'une récurrence linéaire :
$u_{n + 2} = a u_{n + 1} + b u_{n} + g (n)$
Le terme additionnel $g (n)$ "casse" la structure d'espace vectoriel, mais une propriété fondamentale des systèmes linéaires vient à notre secours : le principe de superposition.

Théorème : La solution générale d'une récurrence linéaire non homogène est la somme de :

La solution générale de l'équation homogène associée (en posant $g (n) = 0$ ).
Une solution particulière de l'équation non homogène.

Autrement dit : $u_{n} = u_{n}^{(h)} + u_{n}^{(p)}$ , où $u_{n}^{(h)}$ est la solution homogène avec les constantes $λ, μ$ et $u_{n}^{(p)}$ est n'importe quelle suite qui vérifie l'équation complète.

La recherche de la solution homogène $u_{n}^{(h)}$ a été traitée ci-dessus. Le nouveau défi est de trouver une solution particulière $u_{n}^{(p)}$ . La méthode la plus courante est de "deviner" la forme de $u_{n}^{(p)}$ en se basant sur la forme de $g (n)$ .

Le document de l'ULiège que nous avons vu plus tôt propose une méthode systématique en 5 étapes, qui est la procédure standard à maîtriser.

[PDF] Chapitre 7: récurrences - Introduction à la théorie de l'informatique

Ce document présente une méthode complète pour résoudre les récurrences linéaires, y compris le cas non homogène. Nous nous concentrons sur les étapes pour trouver la solution particulière.

Étudiez attentivement les diapositives 376 à 384. Diapositive 376 : Résume la démarche globale. Étape 3 (Diapositive 378) : C'est le point crucial. Elle explique comment choisir la forme de la solution particulière en fonction de g(n). Si g(n) est un polynôme, on essaie un polynôme. Si c'est une exponentielle, on essaie une exponentielle. Diapositives 380-384 : Suivez l'exemple de résolution de f(n) = 8f(n-1) + 10^{n-1} qui illustre parfaitement les 5 étapes.

Voici les cas les plus fréquents pour la forme de $u_{n}^{(p)}$ :

Si $g (n)$ est...	On cherche $u_{n}^{(p)}$ sous la forme...
Un polynôme de degré $d$ , $P_{d} (n)$	Un polynôme de degré $d$ , $Q_{d} (n)$
Une exponentielle, $c \cdot k^{n}$	Une exponentielle de même base, $d \cdot k^{n}$
Un produit polynôme-exponentielle, $P_{d} (n) \cdot k^{n}$	Un produit polynôme-exponentielle, $Q_{d} (n) \cdot k^{n}$

Attention : Si la forme que vous choisissez pour $u_{n}^{(p)}$ est déjà une solution de l'équation homogène (par exemple, si $g (n) = r_{1}^{n}$ où $r_{1}$ est une racine de l'équation caractéristique), alors votre tentative échouera. Dans ce cas, il faut multiplier la forme tentée par $n$ (ou $n^{2}$ si la racine est double). C'est analogue au terme $(λ + μ n) r_{0}^{n}$ du cas homogène à racine double.

3. Exercices d'application

Exercice 1 : Cas homogène

Soit la suite $(u_{n})$ définie par $u_{0} = 1$ , $u_{1} = 1$ et pour tout $n \geq 0$ :
$u_{n + 2} = u_{n + 1} + 2 u_{n}$
Déterminer l'expression de $u_{n}$ en fonction de $n$ .

Solution

1. **Équation caractéristique :** $r^2 - r - 2 = 0$. 2. **Racines :** Le discriminant est $\Delta = (-1)^2 - 4(1)(-2) = 9 = 3^2$. Les racines sont $r_1 = \frac{1+3}{2} = 2$ et $r_2 = \frac{1-3}{2} = -1$. 3. **Solution homogène :** $u_n = \lambda \cdot 2^n + \mu \cdot (-1)^n$. 4. **Conditions initiales :** * Pour $n=0$: $u_0 = 1 = \lambda \cdot 2^0 + \mu \cdot (-1)^0 \implies \lambda + \mu = 1$. * Pour $n=1$: $u_1 = 1 = \lambda \cdot 2^1 + \mu \cdot (-1)^1 \implies 2\lambda - \mu = 1$. 5. **Résolution du système :** En additionnant les deux lignes, on trouve $3\lambda = 2 \implies \lambda = 2/3$. En substituant, $\mu = 1 - \lambda = 1/3$. 6. **Solution finale :** $u_n = \frac{2}{3} \cdot 2^n + \frac{1}{3} \cdot (-1)^n = \frac{2^{n+1} + (-1)^n}{3}$.

Exercice 2 : Cas non homogène

Soit la suite $(v_{n})$ définie par $v_{0} = 3$ et pour tout $n \geq 1$ :
$v_{n} = 2 v_{n - 1} + 3^{n}$
Déterminer l'expression de $v_{n}$ en fonction de $n$ .

Solution

1. **Équation homogène associée :** $v_n = 2v_{n-1}$. C'est une suite géométrique. La solution homogène est $v_n^{(h)} = C \cdot 2^n$. 2. **Solution particulière :** Le terme non homogène est $g(n) = 3^n$. On cherche une solution particulière de la forme $v_n^{(p)} = d \cdot 3^n$. 3. **Substitution :** On injecte $v_n^{(p)}$ dans l'équation complète : $$ d \cdot 3^n = 2(d \cdot 3^{n-1}) + 3^n $$ On divise par $3^{n-1}$ : $$ 3d = 2d + 3 \implies d = 3 $$ La solution particulière est donc $v_n^{(p)} = 3 \cdot 3^n = 3^{n+1}$. 4. **Solution générale :** $v_n = v_n^{(h)} + v_n^{(p)} = C \cdot 2^n + 3^{n+1}$. 5. **Condition initiale :** Pour $n=0$, $v_0 = 3 = C \cdot 2^0 + 3^{0+1} = C + 3 \implies C = 0$. 6. **Solution finale :** $v_n = 3^{n+1}$.

Conclusion

Vous disposez maintenant d'une méthode algorithmique pour trouver la forme close de toute suite définie par une récurrence linéaire à coefficients constants. C'est un outil d'une grande généralité.

Points clés à retenir :

Cas homogène : La résolution repose entièrement sur les racines de l'équation caractéristique. La structure des solutions est un espace vectoriel.
Cas non homogène : La solution est la somme de la solution générale homogène et d'une solution particulière.
Solution particulière : Sa forme est "mimée" sur celle du terme non homogène $g (n)$ .
Constantes : Les constantes de la solution homogène sont toujours déterminées à la toute fin, en utilisant les conditions initiales sur la solution générale complète.

Dans notre prochaine leçon, nous aborderons un nouveau pilier des mathématiques pour l'informatique : les probabilités discrètes. Nous commencerons par définir rigoureusement un espace probabilisé et par calculer des probabilités d'événements simples, des concepts indispensables pour l'analyse d'algorithmes randomisés et la modélisation de systèmes.

Recommended resources

1. Structure des solutions et cas homogène

2. Le cas non homogène

3. Exercices d'application

Conclusion