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.