Chapitre 6 — démontrer une propriété pour tous les entiers naturels d'un seul coup, en grimpant les marches une à une.
Naviguez avec les flèches ← → du clavier, ou via le Sommaire.
Deux conditions suffisent : la propriété est vraie au départ, et elle se transmet d'un rang au suivant.
L'axiome (N5) est le plus puissant : c'est lui qui fonde le raisonnement par récurrence.
Si $A\subset\mathbb{N}$ vérifie $0\in A$ et $\forall n\in\mathbb{N},\ (n\in A\Rightarrow n+1\in A)$, alors $A=\mathbb{N}$.
Toute partie non vide de $\mathbb{N}$ admet un plus petit élément.
Si $\mathcal{P}(0)$ est vraie et si $\forall n,\ \mathcal{P}(n)\Rightarrow\mathcal{P}(n+1)$, alors $\mathcal{P}(n)$ est vraie pour tout $n\in\mathbb{N}$.
L'escalier peint en jaune : la marche $0$ est jaune (initialisation), et toute marche jaune rend la suivante jaune (hérédité) — donc toutes le sont.
Si $\mathcal{P}(n_0)$ est vraie et si $\forall n\geqslant n_0,\ \mathcal{P}(n)\Rightarrow\mathcal{P}(n+1)$, alors $\mathcal{P}(n)$ est vraie pour tout $n\geqslant n_0$.
On se ramène au cas du rang $0$ en posant $k=n-n_0$.
On ajoute $(n+1)^2$ à l'hypothèse, puis on factorise par $(n+1)$ ; l'identité $(n+2)(2n+3)=2n^2+7n+6$ conclut.
La proposition $9\mid(10^n+1)$ est héréditaire... mais fausse dès $n=0$ ($10^0+1=2$).
Sans marche de départ jaune, rien ne se propage : l'hérédité seule ne prouve rien.
Si $\mathcal{P}(0)$ et $\mathcal{P}(1)$ sont vraies et si $\big(\mathcal{P}(n-1)\wedge\mathcal{P}(n)\big)\Rightarrow\mathcal{P}(n+1)$, alors $\mathcal{P}(n)$ est vraie pour tout $n$.
Les deux rangs précédents donnent le suivant — d'où une double initialisation.
$u_0=1$, $u_1=3$ et $u_{n+1}=2u_n-u_{n-1}$. On conjecture, puis on démontre :
$u_{n+1}=2(2n+1)-(2n-1)=2n+3=2(n+1)+1$.
Si $\mathcal{P}(0)$ est vraie et si $\big(\mathcal{P}(0)\wedge\dots\wedge\mathcal{P}(n)\big)\Rightarrow\mathcal{P}(n+1)$, alors $\mathcal{P}(n)$ est vraie pour tout $n$.
On suppose la propriété acquise jusqu'au rang $n$ pour en déduire le rang $n+1$.
Tout entier $n\geqslant 2$ s'écrit comme produit d'un ou plusieurs nombres premiers.
Si $n+1$ est premier, c'est immédiat. Sinon $n+1=ab$ avec $a,b\in[\![2,n]\!]$ : l'hypothèse forte s'applique à $a$ et à $b$.