Théorème de récurrence forte

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, pour tout $n>n_0$ , l’hypothèse « $A(k)$ est vraie pour tout $k\in\{n_0,\ldots,n-1\}$ » implique que $A(n)$ est vraie

Alors $\forall n \geq n_0$ , $A(n)$ vraie.

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).

Prenons un exemple classique d’utilisation du théorème de récurrence forte.

$\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$

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.

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$ .

Par le théorème de récurrence forte, $\forall n \geq 2$ , la propriété $P_n$ est vraie.