@ccueil Colles

Une démonstration du principe de récurrence

Atteindre l'infini à partir de l'existence d'un plus petit nombre



Document pdf pdf



Le principe de récurrence permet de démontrer un ensemble infini et dénombrable de propriétés. On note par exemple $P_n$ ces propriétés. Pour démontrer que toutes les propriétés $P_n$ sont vraies, à partir d'un premier entier $n_0$, on démontre tout d'abord que la première de ces propriétés $P_{n_0}$ est vraie (initialisation), ensuite on démontre que cette véracité se propage "de proche en proche": si pour un entier $n$ quelconque $P_n$ est vraie, alors la propriété suivante $P_{n+1}$ est aussi vraie.

Le principe de récurrence est celui qui permet alors justement de conclure, à partir de ces deux étapes, que toutes les propriétés $P_n$, pour tous les entiers $n$, sont vraies, dès le premier $n_0$, jusqu'à … l'infini.

Une démonstration de ce principe, permettant de démontrer des propriétés $P_n$ pour des entiers $n$ aussi grands que souhaités, repose au contraire sur l'existence d'un plus petit nombre entier dans un ensemble d'entiers:

Propriété
Tout sous-ensemble de $\N$ non vide possède un plus petit élément.

Cette propriété admise ici est des plus simples: un sous-ensemble de $\N$ est un ensemble de nombres entiers naturels.
Ces nombres sont donc au moins positifs, plus grands que zéro, et peuvent être ordonnés: il y en a nécessairement un plus petit que tous les autres.
Cette nécessité repose sur le fait qu'on manipule ici des nombres entiers, voir la remarque à la fin.


À partir de cette propriété, le principe de récurrence est un théorème:
Théorème:
Soit $P_0$, $P_1$, …, $P_n$, … une suite de propriétés telles que
  1. $P_0$ est vraie
  2. pour tout entier $n$, si $P_n$ est vrai, alors $P_{n+1}$ est aussi vraie.
Alors, pour tout $n\geqslant0$, $P_n$ est vraie.


Démonstration:
Supposons au contraire que pour un certain entier $n$, $P_n$ soit fausse.

On note alors $A=\la k\in\N, P_k \text{ est fausse }\ra$, qui est donc un sous-ensemble non vide de $\N$.
D'après la propriété précédente, $A$ admet donc un plus petit élément, que l'on note $m$, et on a donc
  • $m\in A$, ce qui signifie que $P_m$ et fausse
  • $m-1\not\in A$, ce qui signifie que $P_{m-1}$ n'est pas fausse, donc est vraie.
Or, on sait que, comme $P_{m-1}$ est vraie, la propriété suivante $P_m$ doit aussi être vraie ce qui est contradictoire.

Ainsi, il n'existe pas d'entier $n$ tel que $P_n$ soit fausse, ou encore $P_n$ est vraie pour tous les entiers $n$.
$\square$


Remarque: Le point clé du principe de récurrence est la dénombrabilité: on numérote les propriétés $P_n$ avec les entiers naturels, pour lesquels on a la propriété d'existence du plus petit élément.

Pour les nombres réels, cette propriété est fausse: tout sous-ensemble de $\R$, non-vide, n'admet pas nécessairement un plus petit élément. Par exemple, le sous-ensemble $E=]0;3]$ n'en admet pas.
$0\not\in E$ et pour tout nombre réel $x\in E$, on peut trouver un réel $y$ tel que $y\in E$ et $y<x$: on peut par exemple prendre $y=\dfrac{x}2$ car pour tout nombre $x\in E$, $y=\dfrac{x}2\in E$ et $y<x$.
Ainsi, aucun nombre $x$ de $E$ ne peut être le plus petit élément, on peut toujours en trouver un plus petit.


Voir aussi