Démonstration - Théorème de récurrence

Définition

Soit $A(n)$ une assertion définie pour tout $n\in\mathbb N$, et soit $n_0\in\mathbb N$ fixé.

• $A(n_0)$ est vraie ;
• pour tout $n\geq n_0$, si $A(n)$ est vraie, alors $A(n+1)$ est vraie.

Alors $A(n)$ est vraie pour tout $n\geq n_0$.

Démonstration

Une version détaillée est également disponible ici : Théorème de récurrence faible.

Posons $\mathbb N_0=\{n\in\mathbb N\mid n\geq n_0\}$ et

$P=\{n\in\mathbb N_0\mid A(n)\text{ est vraie}\}.$

Montrons par l’absurde que $P=\mathbb N_0$. Supposons que son complémentaire $\mathbb N_0\setminus P$ ne soit pas vide. Comme toute partie non vide de $\mathbb N$ possède un plus petit élément, notons $p$ son minimum.

L’initialisation donne $n_0\in P$, donc $p\geq n_0+1$ et $p-1\in\mathbb N_0$. Par minimalité de $p$, on a $p-1\in P$, donc $A(p-1)$ est vraie.

L’hypothèse d’induction implique alors que $A(p)$ est vraie, donc $p\in P$. Cela contredit $p\in\mathbb N_0\setminus P$.

Le complémentaire est donc vide : $P=\mathbb N_0$. Ainsi, $A(n)$ est vraie pour tout $n\geq n_0$.