Pourquoi utiliser la récurrence forte ?
La récurrence forte est un mode de raisonnement mathématiques qu’on utilise généralement pour montrer qu’une proposition \mathrm{P}(\mathrm{n}) est vraie pour tout \mathrm{n} appartenant à \mathbb{N} ou à une partie de \mathbb{N}.
L’emploi de la récurrence forte plutôt que de la récurrence simple n’est pas un choix superflu, mais une nécessité. Prenons, par exemple, l’exercice suivant que nous tenterons de résoudre en utilisant la récurrence simple :
Exercice :
On considère la suite numérique \left(u_{n}\right) définie par u_{0}=1 et \forall n \in \mathbb{N}, u_{n+1}=\sum_{k=0}^{n} \sqrt{u_{k}}.
Montrer que \forall n \in \mathbb{N}, u_{n} \geq 0.
Solution :
On note, pour tout \mathrm{n} entier naturelle, \mathrm{P}(\mathrm{n}) la proposition u_{n} \geq 0.
On va essayer de traiter cet exercice par la récurrence simple.
Initialisation :
Pour n=0, on a u_{0}=1 donc u_{0} \geq 0 ce qui signifie que la proposition \mathrm{P}(0) est vraie.
Hérédité :
Soit n \in \mathbb{N}. Supposons que P(n) est vraie et montrons que P(n+1) est vraie.
On n’arrivera jamais à montrer que u_{n+1} \geq 0 uniquement à l’aide de notre l’hypothèse de récurrence u_{n} \geq 0, car u_{n+1} ne dépend pas uniquement de u_{n}, il faut aussi avoir le signe des termes u_{0}, u_{1}, \cdots, u_{n-1} pour pouvoir conclure. On ne peut pas alors résoudre cet exercice avec une récurrence simple.
Principe de la récurrence forte :
Soit \mathrm{A} une partie non vide de \mathbb{N} et n_{0}=\min (A). Pour montrer par la récurrence forte qu’une proposition \mathrm{P}(\mathrm{n}) est vraie pour tout \mathrm{n} appartenant à \mathrm{A} on procède comme suit :
Initialisation :
On vérifie que P\left(n_{0}\right) est vraie.
Hérédité :
Soit n \in A. On suppose que pour tout entier naturel \mathrm{k} compris entre n_{0} et \mathrm{n}, la proposition \mathrm{P}(\mathrm{k}) est vraie. Puis on montre que la proposition \mathrm{P}(\mathrm{n}+1) est vraie.
Conclusion :
On conclut que pour tout n appartenant à \mathrm{A}, la proposition \mathrm{P}(\mathrm{n}) est vraie.
Récurrence forte exemple :
Revenant maintenant à notre exercice et appliquons cette fois une récurrence forte.
Initialisation :
Pour n=0, on a u_{0}=1 donc u_{0} \geq 0 ce qui signifie que la proposition \mathrm{P}(0) est vraie.
Hérédité :
Soit n \in \mathbb{N}. Supposons que, pour tout entier naturel k compris entre 0 et n, P(n) est vraie et montrons que P(n+1) est vraie.
Par hypothèse de récurrence u_{0}, u_{1}, \cdots, u_{n} sont positifs, donc leur somme l’est également.
Ainsi u_{n+1} \geq 0 ce qui signifie que la proposition \mathrm{P}(\mathrm{n}+1) est varie.
Conclusion :
Par le principe de la récurrence forte on conclut que \forall n \in \mathbb{N}, u_{n} \geq 0.
Récurrence forte exercices corrigés :
La récurrence forte joue un rôle clé dans la preuve de nombreux théorèmes et propriétés issus de divers domaines mathématiques. À titre d’exemple :
Le théorème fondamental de l’arithmétique illustre l’utilisation de la récurrence forte pour démontrer que tout entier supérieur à 2 peut être décomposé en un produit de nombres premiers.
Voici quelques exercices corrigés qui illustrent l’utilisation de la récurrence forte :
Exercice 1 :
Montrer que \forall n \in \mathbb{N}^{*}, \exists(p, q) \in \mathbb{N}^{2}, n=2^{p}(2 q+1).
Exercice 2 :
On considère la suite \left(u_{n}\right)_{n \in \mathbb{N}} définie par :
u_{0}=1 \text { et } \forall n \in \mathbb{N} \quad u_{n+1}=\frac{2}{n+1} \sum_{k=0}^{n} u_{k} u_{n-k}.
Montrer que \forall n \in \mathbb{N}, \quad u_{n}=2^{n}.
En cliquant sur ce lien, vous découvrirez un article plus riche, incluant de nombreux exercices supplémentaires sur la récurrence forte.