Récurrence forte : énoncé (MPSI)
Récurrence forte
Soit $n_0\in\mathbb{N}$ et $P(n)$ une assertion pour $n\geq n_0$. On suppose :
- $P(n_0)$ est vraie ;
- pour tout $n\geq n_0$, si $P(k)$ est vraie pour tout $k\in\llbracket n_0,n\rrbracket$, alors $P(n+1)$ est vraie.
Alors $P(n)$ est vraie pour tout $n\geq n_0$.
Démonstration : Récurrence forte
Preuve
Pour $n\geq n_0$, notons $Q(n)$ : « pour tout $k\in\llbracket n_0,n\rrbracket$, $P(k)$ est vraie ». On montre $Q$ par récurrence simple.
$Q(n_0)$ se réduit à $P(n_0)$, vraie par hypothèse. Soit $n\geq n_0$ tel que $Q(n)$ soit vraie. Par la seconde hypothèse, $P(n+1)$ est vraie ; joint à $Q(n)$, cela donne $Q(n+1)$.
Par récurrence simple, $Q(n)$ est vraie pour tout $n\geq n_0$, et $Q(n)$ contient $P(n)$.
Tout entier $n\geq 2$ est un produit de nombres premiers
Pour $n\geq 2$, notons $P(n)$ : « $n$ est un produit (éventuellement à un seul facteur) de nombres premiers ».
Initialisation. $2$ est premier, donc $P(2)$ est vraie.
Hérédité. Soit $n\geq 2$ tel que $P(k)$ soit vraie pour tout $k\in\llbracket 2,n\rrbracket$. Considérons $n+1$.
- Si $n+1$ est premier, $P(n+1)$ est vraie.
- Sinon, $n+1$ admet un diviseur $a$ avec $2\leq a\leq n$, et $n+1=ab$ avec $b=\dfrac{n+1}{a}$ entier vérifiant $2\leq b\leq n$. Par hypothèse, $a$ et $b$ sont des produits de nombres premiers, donc $n+1=ab$ aussi.
Conclusion. Par récurrence forte, $P(n)$ est vraie pour tout $n\geq 2$. En particulier, tout entier $n\geq 2$ admet un diviseur premier, ce qui justifie la preuve de l'infinité des nombres premiers. Une récurrence simple échoue ici : $a$ et $b$ ne sont pas égaux à $n$ en général.
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