Principe de récurrence

L’axiomatisation de l’ensemble des entiers naturels par Peano à la fin du XIXe siècle réduit la fondation de l’arithmétique aux cinq propositions suivantes.

  1. L’élément appelé zéro et noté 0, est un entier naturel.
  2. Tout entier naturel a un unique successeur.
  3. Aucun entier naturel n’a 0 pour successeur.
  4. Deux entiers naturels ayant le même successeur sont égaux.
  5. Si un ensemble d’entiers naturels contient 0 et contient le successeur de chacun de ses éléments, alors cet ensemble contient tous les entiers naturels.

Le dernier axiome justifie la démonstration par récurrence.

Formulations

Soit Pn un prédicat dépendant d'une variable n.

Récurrence simple
Si les deux conditions suivantes sont remplies :
  • la proposition initiale P0 est vraie ;
  • la proposition est héréditaire, c’est-à-dire que pour tout entier naturel n on a l’implication Pn ⇒ Pn+1
alors toutes les propositions Pn sont vraies.

Ce principe peut être aménagé pour démontrer une propriété seulement à partir du rang n = 1 voire à partir d’un rang supérieur, en modifiant la proposition initiale et en démontrant l’hérédité à partir de ce rang.

Ce principe permet de démontrer également les principes suivants.

Récurrence double
Si les deux conditions suivantes sont remplies :
  • les propositions initiales P0 et P1 sont vraies ;
  • pour tout n ∈ N on a l’implication (Pn et Pn+1) ⇒ Pn+2
alors toutes les propositions Pn sont vraies.
Récurrence forte
Si les deux conditions suivantes sont remplies :
  • la proposition initiale P0 est vraie ;
  • pour tout n ∈ N on a l’implication (P0, …, Pn) ⇒ Pn+1
alors toutes les propositions Pn sont vraies.

Applications

Ordre dans N

Tout entier naturel est positif.

On procède par récurrence.
Soit n ∈ N tel que n ≥ 0. On a 1 ≥ 0 donc n + 1 ≥ 0.
Finalement, par principe de récurrence, tout entier naturel est positif.

Pour tout n ∈ N, il n'existe aucun entier naturel strictement compris entre n−1 et  n.

On procède par récurrence.

Puisque tout entier naturel est positif, il n'existe aucun entier naturel dans ]−1 ; 1[ donc l'entier 0 satisfait la propriété.

Soit n ∈ N tel que N ∩ ]n − 1 ; n[ = ∅. On pose E = N \ ]n ; n + 1[.

Pour tout k ∈ N tel que k ≤ n − 1, on a k + 1 ≤ n donc k + 1 ∈ E et pour tout k ∈ N tel que k ≥ n, on a k + 1 ≥ n + 1 donc k + 1 ∈ E.
Par conséquent, on trouve N ⊂ E donc la propriété est vraie au rang n+1.

Finalement, par principe de récurrence, on trouve que pour tout n ∈ N, il n'existe aucun entier naturel strictement compris entre n−1 et  n.

Toute partie non vide majorée de N admet un plus grand élément.

On montre par récurrence sur n ∈ N que toute partie non vide majorée par n admet un plus grand élément.

Toute partie non vide majorée par 0 est réduite au singleton {0} dont 0 est le plus grand élément.

Soit n ∈ N tel que toute partie non vide de N ∩ [0 ; n] admette un maximum. Soit A une partie non vide de N ∩ [0 ; n + 1]. On distingue deux cas.

Finalement, par principe de récurrence, toute partie non vide et majorée dans N admet un plus grand élément.

L'ensemble N n'est pas majoré.

Supposons que l'ensemble N est majoré. Alors il admet un plus grand élément, que l'on note n. Mais on a n < n + 1 ∈ N, donc n ne majore pas N, ce qui contredit sa définition.
Finalement, l'ensemble N n'est pas majoré.

Toute partie non vide de N admet un plus petit élément.

Soit A une partie non vide de N.

On note B l'ensemble des minorants de A. Il existe a ∈ A donc l'ensemble B est majoré par a et il est non vide puisqu'il contient au moins 0. Donc B admet un plus grand élément, que l'on note b.

L'entier b appartient à B donc c'est un minorant de A et on montre par l'absurde qu'il appartient à A.

Supposons b ∉ A. Alors pour tout n ∈ A on a n > b donc n ≥ b + 1 donc b+1 est un minorant de A qui est strictement plus grand que b, ce qui contredit la définition de b.

Finalement, l'entier b est un minorant de A qui appartient à A donc A admet un plus petit élément.

Stabilité par les opérations arithmétiques

Pour tout (n, p) ∈ N2, on a n + p ∈ N.

Soit p ∈ N. On raisonne par récurrence sur n ∈ N.

Par définition, on a 0 + p = p ∈ N.

Soit n ∈ N tel que n + p ∈ N. On a (n + 1) + p = (n + p) + 1 ∈ N.

Pour tout (n, p) ∈ N2, on a n × p ∈ N.

Soit p ∈ N. On raisonne par récurrence sur n ∈ N.

Par définition, on a 0 × p = 0 ∈ N.

Soit n ∈ N tel que n × p ∈ N. On a (n + 1) × p = n × p + n ∈ N.

Pour tout (n, p) ∈ N2 tel que n ≥ p, on a n − p ∈ N.

Soit p ∈ N. On raisonne par récurrence sur n ∈ N.

Si 0 ≥ p ∈ N alors p = 0 et 0 − p = 0 ∈ N.

Soit n ∈ N tel que la propriété soit vraie pour n et supposons n + 1 ≥ p. On distingue deux cas.