Une démonstration du principe de récurrence

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

Y. Morel

Document pdf

Le principe de récurrence permet de démontrer un ensemble infini et dénombrable de propriétés. On note par exemple

ces propriétés. Pour démontrer que toutes les propriétés

sont vraies, à partir d'un premier entier

, 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

quelconque

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

, pour tous les entiers

, sont vraies, dès le premier

, jusqu'à … l'infini.

Une démonstration de ce principe, permettant de démontrer des propriétés

pour des entiers

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

, …,

, … une suite de propriétés telles que

est vraie
pour tout entier , si est vrai, alors $P_{n+1}$ est aussi vraie.

Alors, pour tout $n\geqslant0$ ,

est vraie.

Démonstration:

Supposons au contraire que pour un certain entier , 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, admet donc un plus petit élément, que l'on note , et on a donc

$m\in A$ , ce qui signifie que 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 doit aussi être vraie ce qui est contradictoire.

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

Remarque: Le point clé du principe de récurrence est la dénombrabilité: on numérote les propriétés

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