Prépa, 1re année › Logique et raisonnements › Principe de récurrence simple
Principe de récurrence simple : énoncé (MPSI)
Théorème
Principe de récurrence simple
Soit $n_0\in\mathbb{N}$ et, pour tout entier $n\geq n_0$, une assertion $P(n)$. On suppose :
- (initialisation) $P(n_0)$ est vraie ;
- (hérédité) pour tout $n\geq n_0$, $P(n)\Rightarrow P(n+1)$.
Alors $P(n)$ est vraie pour tout entier $n\geq n_0$.
Démonstration : Principe de récurrence simple
Démonstration
Preuve à partir de la propriété fondamentale
Supposons par l'absurde que l'ensemble $A=\{n\in\mathbb{N},\ n\geq n_0\ \text{et}\ P(n)\ \text{fausse}\}$ soit non vide. Il admet un plus petit élément $m$. Comme $P(n_0)$ est vraie, $m\neq n_0$, donc $m\geq n_0+1$ et $m-1\geq n_0$. Par minimalité de $m$, $m-1\notin A$, donc $P(m-1)$ est vraie. Par hérédité, $P(m)$ est vraie, ce qui contredit $m\in A$. Donc $A$ est vide.
S’entraîner
- Comparer $2^n$ et $n^2$
- Suites récurrentes d'ordre 2
- Affranchir avec des timbres de 3 et 5
- Écriture unique $n=2^a(2b+1)$
- Examen : suite de Fibonacci et récurrences