Raisonnement par récurrence
Principe du raisonnement par récurrence
Si un sous-ensemble \(E \subset \mathbb N\) possède les deux propriétés suivantes :
Initialisation : \(0 \in E\)
Propriété d'hérédité : \((\forall k \in N), k \in E \Rightarrow k+1 \in E\)
alors cet ensemble est l'ensemble de tous les entiers, \(E = \mathbb N\).
Preuve :
Ce principe du raisonnement par récurrence, appelé aussi principe d'induction résulte du principe du bon ordre.
On veut montrer que le complémentaire de \(E\) dans \(\mathbb N\) est vide. Si nous le supposons non vide, il possède un plus petit élément \(n\) d'après le principe du bon ordre, \(n\) est non nul puisque 0 est dans \(E\), et donc \(n\) - 1 appartient à \(\mathbb N\) et est dans \(E\) ; d'après la propriété d'hérédité, \(n - 1\) étant dans \(E, n\) aussi, ce qui est contraire à la façon dont nous avons défini \(n,\) comme le plus petit élément du complémentaire de \(E.\)
Plan d'une démonstration par récurrence
Il est conseillé d'adopter le plan suivant pour toute démonstration par récurrence. On veut montrer que la propriété \(P(n)\) est vraie pour tout \(n\).
Énoncé de la propriété \(P(n)\).
Initialisation de la propriété \(P(n)\) pour \(n = 0.\)
Hérédité de la propriété : montrer \(P(n) \Rightarrow P(n+1)\) à partir de \(n = 0.\)
Conclusion : lorsque la propriété est vraie pour un nombre entier positif \(n,\) elle est vraie aussi pour \(n + 1.\) Comme elle est vraie pour \(n = 0 ,\) elle est donc vraie pour tous les entiers.