Principe d'induction

Après avoir justifié ce principe du raisonnement par récurrence, (ou principe d'induction,) plusieurs variantes peuvent être données.

Ce principe peut s'écrire en terme de propriété.

Il suffit de poser \(E= \{ n \in N | P(n) \},\) pour se ramener à l'énoncé précédent.

On peut aussi varier l'initiation : dans certaines applications, l'initialisation se fait par exemple à 2 et non à 0. L'énoncé est adapté en conséquence.

On peut faire varier la forme de la propriété d'hérédité et adopter une forme forte à la fois sous forme ensembliste, et également en terme de propriété.

Si une propriété \(P(n)\) dépendant d'un entier naturel \(n\) est vérifiée pour 0 et si lorsqu'elle est vérifiée pour un entier quelconque \(k,\) elle est vérifiée pour l'entier suivant \(k + 1,\) alors elle est vraie pour tous les entiers.

Si une propriété \(P(n)\) dépendant d'un entier naturel \(n\) est vérifiée pour \(n_0 ,\) et si lorsqu'elle est vérifiée pour un entier quelconque \(k \geq n_0 ,\) elle est vérifiée pour l'entier suivant \(k + 1,\) alors elle est vraie pour tous les entiers \(n \geq n_0.\)

Si un sous-ensemble \(E\) de \(\mathbb N\) possède les deux propriétés suivantes :

• Initialisation: \(0 \in E\)

• Propriété d'hérédité: \(\forall n \in \mathbb N, (( \forall k < n, k \in E) \Rightarrow n \in E)\)

alors cet ensemble est l'ensemble de tous les entiers, \(E = \mathbb N\).

Si \(P(n)\) est une propriété dépendant d'un entier naturel \(n\) telle que

• Initialisation : \(P(0)\) est vraie

• Propriété d'hérédité : \(\forall n \in \mathbb N, si P(k)\) est vraie pour tout entier naturel \(k\) strictement inférieur à \(n,\) alors elle est vraie pour \(n.\)

alors la propriété \(P(n)\) est vraie pour tous les entiers.