Récurrence forte

a) 1) Soit $n \geqslant 0$ tel que $P(k)$ soit vraie pour tout $k \in \llbracket 0, n \rrbracket$. Montrons $P(n+1)$.
2) Majoration : $n-1 \leqslant n$ est toujours vraie. Minoration : $n-1 \geqslant 0$ si et seulement si $n \geqslant 1$. Donc $n-1 \in \llbracket 0, n \rrbracket$ si et seulement si $n \geqslant 1$.
3) La valeur $n = 0$ est exclue : le rang visé $1$ se démontre à part, sans l'hypothèse, soit comme premier cas de l'hérédité, soit en ajoutant $P(1)$ à l'initialisation.

b) 1) Soit $n \geqslant 12$ tel que $P(k)$ soit vraie pour tout $k \in \llbracket 12, n \rrbracket$. Montrons $P(n+1)$.
2) Majoration : $n-3 \leqslant n$ toujours. Minoration : $n-3 \geqslant 12$ si et seulement si $n \geqslant 15$.
3) Les valeurs $n = 12$, $13$ et $14$ sont exclues : les rangs visés $13$, $14$ et $15$ se démontrent à part.

c) 1) Soit $n \geqslant 1$ tel que $P(k)$ soit vraie pour tout $k \in \llbracket 1, n \rrbracket$. Montrons $P(n+1)$.
2) Posons $m = \frac{n+1}{2}$, qui est un entier puisque $n+1$ est pair. Minoration : $n \geqslant 1$ donne $n+1 \geqslant 2$, donc $m \geqslant 1$. Majoration : $m \leqslant n$ équivaut à $n+1 \leqslant 2n$, c'est-à-dire à $n \geqslant 1$, qui est vraie. Donc $m \in \llbracket 1, n \rrbracket$ pour tout $n$ tel que $n+1$ soit pair.
3) Aucun rang visé pair n'est exclu. En revanche, si $n+1$ est impair, $\frac{n+1}{2}$ n'est pas un entier, donc pas un rang : ce cas demande un autre argument, rédigé comme second cas de l'hérédité.

d) 1) Soit $n \geqslant 3$ tel que $P(k)$ soit vraie pour tout $k \in \llbracket 3, n \rrbracket$. Montrons $P(n+1)$.
2) Le rang $n$ vérifie $3 \leqslant n \leqslant n$ : il est toujours couvert. Pour $n-2$ : $n-2 \leqslant n$ toujours, et $n-2 \geqslant 3$ si et seulement si $n \geqslant 5$. Les deux rangs sont couverts si et seulement si $n \geqslant 5$.
3) Les valeurs $n = 3$ et $n = 4$ sont exclues : les rangs visés $4$ et $5$ se démontrent à part.
À retenir : on résout la minoration du rang appelé, et les valeurs de $n$ qu'elle écarte donnent la liste exacte des rangs à traiter sans l'hypothèse.

1) [A] Pour tout entier $n \geqslant 2$, notons $P(n)$ : « $n$ est un produit de nombres premiers ».
[B] L'entier $2$ est premier, donc c'est un produit à un seul facteur premier : $P(2)$ est vraie.
[C] Soit $n \geqslant 2$ tel que $P(k)$ soit vraie pour tout $k \in \llbracket 2, n \rrbracket$. Montrons $P(n+1)$.
[D] Alors $n+1$ est un produit à un seul facteur premier, donc $P(n+1)$ est vraie, sans recours à l'hypothèse de récurrence.
[E] Situons $b$. Comme $a \geqslant 2$, on a $b = \frac{n+1}{a} \leqslant \frac{n+1}{2} \leqslant n$, la dernière inégalité venant de $n \geqslant 1$. Comme $a \leqslant n < n+1$, on a $b = \frac{n+1}{a} > 1$, et $b$ est entier, donc $b \geqslant 2$. Ainsi $a$ et $b$ appartiennent à $\llbracket 2, n \rrbracket$.
[F] Par hypothèse de récurrence appliquée aux rangs $a$ et $b$, les entiers $a$ et $b$ sont des produits de nombres premiers.
[G] Dans les deux cas, $P(n+1)$ est vraie.
[H] Par récurrence forte, tout entier $n \geqslant 2$ est un produit de nombres premiers.

2) Les facteurs $a$ et $b$ ne sont en général pas égaux à $n$. Pour $n+1 = 15 = 3 \times 5$, une hypothèse simple ne fournirait que $P(14)$, qui ne dit rien de $3$ ni de $5$. On ne sait pas à l'avance quels rangs de $\llbracket 2, n \rrbracket$ serviront : il faut les supposer tous, ce que fait l'hypothèse forte.