Théorème de récurrence forte
Cet article présente le théorème de récurrence forte avec un exemple d'utilisation classique.
This article has been written by Robin Pourtaud ([email protected]) and published on July 28, 2021.
The content of this article is licensed under CC BY
NC 4.0 : You can freely share and adapt the content for non-commercial purposes as long as you give
appropriate credit and provide a link to the license. In my case, the link to the original article is enough.
Confidentiality if relevant: https://devmath.fr/page/confidentialite/
Théorème
Soit $\mathbb{N}$ muni de son ordre usuel. Soit $A(n)$ une assertion définie $\forall n \in \mathbb{N}$ :
- Si $A(n_0)$ vraie
- Si $\forall n > n_0$ et $\forall k \in \{n_0,\ldots , n-1\}$ tel que $A(k)$ vraie $\Rightarrow A(n)$ vraie
Alors $\forall n \geq n_0$, $A(n)$ vraie.
Démonstration
La démonstration du théorème de récurrence forte est analogue à celle du théorème de récurrence.
Cela s’explique car toute récurrence forte peut être reformulée en récurrence simple (et inversement).
Exemple d’utilisation du théorème
Prenons un exemple classique d’utilisation du théorème de récurrence forte.
Propriété
$\forall n \in (\mathbb{N},\leq_\mathbb{N}) : n\geq 2$, $P_n : n$ peut être décomposé en produit de facteurs premiers.
Par exemple :
- $9 = 3^2$
- $6 = 2 \times 3$
- $65 = 5 \times 13$
1 et 0 ne sont pas des nombres premiers, d’où le $n \geq 2$
Initialisation
Vérifions que $P_2$ est vraie.
$P_2$ correspond à notre $A(n_0)$.
$2$ est uniquement divisible par 1 et lui-même. $P_2$ est un nombre premier donc il est divisible en produit de facteurs premiers.
La propriété $P_2$ est donc vraie.
Induction
Supposons la propriété $P_k$ vraie $\forall k \in \{2,\ldots, n-1\}$ avec $n > 2$. Montrons que la propriété est également vraie pour le rang $n$.
Nous avons 2 possibilités pour $n$ :
- Si $n$ est un nombre premier, alors il est divisible en produit de facteurs premiers. La propriété est donc vraie au rang n.
- Si $n$ n’est pas un nombre premier, alors il possède un diviseur $d$ tel que $d\notin \{1,n\}$. Donc comme $d \textless n$, $n / d = m$ et nécessairement $m \textless n$. Par hypothèse de récurrence, comme $m$ et $d$ sont divisibles en facteurs de nombres premiers, $n$ l’est aussi. La propriété est donc vraie au rang $n$.
La propriété est bien vraie au rang $n$.
Conclusion
Par le théorème de récurrence forte, $\forall n \geq 2$, la propriété $P_n$ est vraie.