Récurrence simple

Un prédicat $P(n)$ est une phrase mathématique où figure un entier $n$ et qui devient, dès qu'on donne à $n$ une valeur, une assertion vraie ou fausse. Dans $P(n)$, la lettre $n$ est libre : aucun « pour tout $n$ » ni « il existe $n$ » ne la lie, sinon $P(n)$ ne dépendrait plus de $n$. L'énoncé « pour tout $n \geq n_0$, $P(n)$ » est au contraire une seule assertion, où $n$ est muette. Un prédicat peut en revanche quantifier d'autres lettres : « pour tout réel $x \geq -1$, $(1+x)^n \geq 1 + nx$ » est un prédicat en $n$.

L'initialisation est la preuve de $P(n_0)$, où $n_0$ est le rang de départ de la récurrence : en général le premier rang visé par l'énoncé, ou un rang plus tardif si l'hérédité l'exige, les rangs antérieurs se vérifiant alors à part. L'hérédité est l'assertion « pour tout $n \geq n_0$, $P(n) \Rightarrow P(n+1)$ » ; quand elle est vraie, on dit que $P$ est héréditaire à partir du rang $n_0$. Pour la démontrer, on fixe un entier $n \geq n_0$ et on suppose $P(n)$ : c'est l'hypothèse de récurrence, qui ne porte que sur cet entier. L'hérédité n'affirme jamais que $P(n)$ est vraie, seulement que la vérité passe de chaque rang au suivant.

Soit $P(n)$ un prédicat défini pour tout $n \in \mathbb{N}$. Si $P(0)$ est vraie et si, pour tout $n \in \mathbb{N}$, $P(n)$ entraîne $P(n+1)$, alors $P(n)$ est vraie pour tout $n \in \mathbb{N}$. Ce principe exprime une propriété de l'ensemble $\mathbb{N}$ ; on peut le déduire du fait que toute partie non vide de $\mathbb{N}$ admet un plus petit élément (voir « Principe du plus petit élément »). La récurrence est dite simple parce que l'hérédité ne s'appuie que sur le rang $n$ pour atteindre le rang $n+1$, à la différence des récurrences double et forte.

Soit $n_0 \in \mathbb{N}$ et $P(n)$ un prédicat défini pour tout entier $n \geq n_0$. Si $P(n_0)$ est vraie et si, pour tout $n \geq n_0$, $P(n)$ entraîne $P(n+1)$, alors $P(n)$ est vraie pour tout entier $n \geq n_0$. On le déduit du principe de récurrence appliqué au prédicat $Q(m)$ : « $P(n_0 + m)$ est vraie », pour $m \in \mathbb{N}$. La conclusion ne dit rien des entiers $n < n_0$, qui se traitent à part s'il le faut.

L'hérédité seule ne prouve rien : l'implication $P(n) \Rightarrow P(n+1)$ est vraie dès que $P(n)$ est fausse, donc un prédicat faux à tous les rangs est héréditaire, comme « $10^n + 1$ est divisible par $9$ ». Il faut un premier rang vrai pour que la vérité se transmette, et elle ne se transmet qu'aux rangs suivants. À l'inverse, vérifier beaucoup de rangs ne remplace pas l'hérédité : « $n^2 \leq 10n$ » est vraie pour $n = 0, 1, \ldots, 10$, puis fausse pour $n = 11$, car $11^2 = 121 > 110$. Une récurrence exige donc les deux preuves, au même rang de départ.

Soit $n \geq n_0$ introduit un entier fixé mais quelconque : ce qu'on démontre pour lui vaut pour chaque entier $n \geq n_0$. La précision tel que $P(n)$ soit vraie pose l'hypothèse de récurrence sur cet entier seulement ; l'écriture en deux phrases « Soit $n \geq n_0$ » puis « Supposons $P(n)$ vraie » dit la même chose, et la forme courte « soit $n \geq n_0$ tel que $P(n)$ » est admise. Montrons annonce le but, $P(n+1)$, sans rien affirmer encore. Par hypothèse de récurrence justifie la ligne où sert $P(n)$, comme « car $n \geq n_0$ » justifie celle où sert le rang. Par récurrence justifie la conclusion, et elle seule.

Dans l'hérédité, on découpe l'objet du rang $n+1$ pour y lire celui du rang $n$, auquel s'applique l'hypothèse de récurrence. Les découpages ci-dessous valent pour tout entier $n \geq 1$, tous nombres $a_1, \ldots, a_{n+1}$ et tout nombre $q$. Pour l'hérédité écrite de $n-1$ à $n$, on les emploie un rang plus bas : $S_n = S_{n-1} + a_n$, $n! = n \times (n-1)!$. Avant de découper, on écrit le terme général au rang $n+1$ en remplaçant chaque $n$ par $(n+1)$ : le dernier impair devient $2(n+1) - 1 = 2n + 1$.

Signal : l'énoncé affirme une propriété « pour tout entier $n \geq n_0$ », et la propriété au rang $n+1$ se relie à celle du rang $n$ (puissance, somme de $n$ termes, factorielle, suite définie par récurrence) ; ou l'énoncé demande explicitement une récurrence.
1) Prédicat : « Pour tout entier $n \geq n_0$, notons $P(n)$ l'assertion : “…”. »
2) Initialisation : « Pour $n = n_0$ : … donc $P(n_0)$ est vraie. »
3) Hérédité : « Soit $n \geq n_0$ tel que $P(n)$ soit vraie. Montrons que $P(n+1)$ est vraie. », puis la preuve, fermée par « donc $P(n+1)$ est vraie ».
4) Conclusion : « $P(n_0)$ est vraie et $P$ est héréditaire à partir du rang $n_0$ ; par récurrence, $P(n)$ est vraie pour tout entier $n \geq n_0$. »
Aucun des quatre temps ne se saute, et la conclusion vient après les deux preuves. Si le rang $n+1$ réclame les deux rangs précédents, ou tous, il faut une récurrence double ou forte (thèmes dédiés).
Rédaction modèle : divisibilité de $4^n - 1$ par $3$.

Montrer que pour tout $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$.
Pour tout $n \in \mathbb{N}$, notons $P(n)$ l'assertion : « $4^n - 1$ est divisible par $3$ ».
Initialisation. Pour $n = 0$ : $4^0 - 1 = 0 = 3 \times 0$, donc $P(0)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$, c'est-à-dire que $4^{n+1} - 1$ est divisible par $3$.
Par hypothèse de récurrence, il existe un entier $k$ tel que $4^n - 1 = 3k$, c'est-à-dire $4^n = 3k + 1$.
Alors $4^{n+1} - 1 = 4 \times 4^n - 1 = 4(3k + 1) - 1 = 12k + 3 = 3(4k + 1)$.
Or $4k + 1$ est un entier, donc $4^{n+1} - 1$ est divisible par $3$ : $P(n+1)$ est vraie.
Conclusion. $P(0)$ est vraie et $P$ est héréditaire ; par récurrence, $4^n - 1$ est divisible par $3$ pour tout $n \in \mathbb{N}$.
À retenir : les quatre temps s'écrivent tous, dans l'ordre, et l'hypothèse de récurrence se traduit d'abord en une relation qui se calcule, ici $4^n = 3k + 1$.

Signal : l'énoncé affirme une propriété « pour tout $n \in \mathbb{N}$ », « pour tout $n \in \mathbb{N}^*$ » ou « pour tout entier $n \geq n_0$ », et l'on a choisi de raisonner par récurrence.
1) Repérer le quantificateur sur $n$ et en lire le rang de départ $n_0$.
2) Recopier la phrase qui le suit, sans ce quantificateur : c'est $P(n)$, où $n$ désigne un entier donné.
3) Fixer avant le prédicat les objets que l'énoncé donne une fois pour toutes (un réel $x$, une fonction $f$) : ils ne bougent pas pendant la récurrence. Si l'énoncé quantifie une autre lettre, on peut aussi garder ce quantificateur dans $P(n)$ (voir « Choisir la propriété de récurrence »).
4) Nommer les nombres qui dépendent de $n$ ($S_n$, $u_n$) pour calculer avec eux : $P(n)$ reste une phrase, jamais un nombre.
5) Écrire : « Pour tout entier $n \geq n_0$, notons $P(n)$ l'assertion : “…”. »
Contrôle : en remplaçant $n$ par $n_0$, on doit lire une assertion précise, vraie ou fausse, sans aucun « pour tout $n$ ».
Rédactions modèles : encadrement d'une suite définie par récurrence (paramètre fixé, terme nommé) ; inégalité de Bernoulli (paramètre fixé avant le prédicat) ; somme des entiers impairs (somme nommée).

Soit $a$ un réel tel que $0 \leq a \leq 1$. On définit la suite $(u_n)$ par $u_0 = a$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = u_n(2 - u_n)$. Montrer que pour tout $n \in \mathbb{N}$, $0 \leq u_n \leq 1$.
Soit $a$ un réel tel que $0 \leq a \leq 1$ ; il reste fixé dans toute la démonstration, et avec lui la suite $(u_n)$.
Pour tout $n \in \mathbb{N}$, notons $P(n)$ l'assertion : « $0 \leq u_n \leq 1$ ».
Initialisation. Pour $n = 0$ : $u_0 = a$, et $0 \leq a \leq 1$ par hypothèse sur $a$, donc $P(0)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$, c'est-à-dire $0 \leq u_{n+1} \leq 1$.
Par hypothèse de récurrence, $0 \leq u_n \leq 1$.
Minoration. Comme $u_n \leq 1$, on a $2 - u_n \geq 1 > 0$.
Comme de plus $u_n \geq 0$, le nombre $u_{n+1} = u_n(2 - u_n)$ est le produit de deux nombres positifs, donc $u_{n+1} \geq 0$.
Majoration. On calcule $1 - u_{n+1} = 1 - 2u_n + u_n^2 = (1 - u_n)^2$.
Un carré est positif, donc $1 - u_{n+1} \geq 0$, c'est-à-dire $u_{n+1} \leq 1$.
Ainsi $0 \leq u_{n+1} \leq 1$ : $P(n+1)$ est vraie.
Conclusion. $P(0)$ est vraie et $P$ est héréditaire ; par récurrence, pour tout $n \in \mathbb{N}$, $0 \leq u_n \leq 1$.
À retenir : le paramètre $a$ est fixé avant le prédicat, le terme $u_n$ porte un nom, et $P(n)$ est une seule phrase sur ce nombre, sans quantificateur sur $n$ ; elle réunit les deux inégalités, car la minoration de $u_{n+1}$ se sert de $u_n \leq 1$.

Signal : l'énoncé fixe les entiers visés : $\mathbb{N}$, $\mathbb{N}^*$, « pour tout entier $n \geq 4$ ».
1) Lire le rang de départ $n_0$ : $0$ pour $\mathbb{N}$, $1$ pour $\mathbb{N}^*$, $4$ pour « $n \geq 4$ ».
2) Calculer séparément chaque membre de $P(n_0)$, sans écrire d'emblée la relation à vérifier, puis les comparer.
3) Écrire : « Pour $n = n_0$ : [premier membre] vaut …, [second membre] vaut …, donc $P(n_0)$ est vraie. »
4) Contrôler, une fois l'hérédité écrite, qu'elle vaut pour tout $n \geq n_0$. Si l'un de ses calculs exige $n \geq n_1$ avec $n_1 > n_0$, initialiser au rang $n_1$ et vérifier à la main les rangs de $n_0$ à $n_1 - 1$.
5) Si $P(n_0)$ est fausse, ne pas conclure par récurrence : $n_0$ est un contre-exemple, et l'énoncé est faux, sauf s'il a été mal lu.
Rédactions modèles : $2^n + 1 \geq n^2$ pour tout $n \in \mathbb{N}$ (initialisation au rang $3$, rangs $0$ à $2$ vérifiés à la main) ; $2^n \geq n^2$ pour tout entier $n \geq 4$.

Montrer que pour tout $n \in \mathbb{N}$, $2^n + 1 \geq n^2$.
Pour tout $n \in \mathbb{N}$, notons $P(n)$ l'assertion : « $2^n + 1 \geq n^2$ ».
Rangs $0$, $1$ et $2$, vérifiés à la main. Pour $n = 0$ : $2^0 + 1 = 2$ et $0^2 = 0$, donc $P(0)$ est vraie.
Pour $n = 1$ : $2^1 + 1 = 3$ et $1^2 = 1$, donc $P(1)$ est vraie.
Pour $n = 2$ : $2^2 + 1 = 5$ et $2^2 = 4$, donc $P(2)$ est vraie.
Montrons par récurrence que $P(n)$ est vraie pour tout entier $n \geq 3$.
Initialisation. Pour $n = 3$ : $2^3 + 1 = 9$ et $3^2 = 9$, donc $P(3)$ est vraie.
Hérédité. Soit $n \geq 3$ un entier tel que $P(n)$ soit vraie. Montrons $P(n+1)$, c'est-à-dire $2^{n+1} + 1 \geq (n+1)^2$.
Par hypothèse de récurrence, $2^n + 1 \geq n^2$, c'est-à-dire $2^n \geq n^2 - 1$.
En multipliant par $2$, qui est positif, on obtient $2^{n+1} \geq 2n^2 - 2$, donc $2^{n+1} + 1 \geq 2n^2 - 1$.
Par ailleurs, $2n^2 - 1 - (n+1)^2 = n^2 - 2n - 2 = n(n-2) - 2$.
Comme $n \geq 3$, on a $n - 2 \geq 1$ ; les nombres $n$ et $n - 2$ étant positifs, $n(n-2) \geq 3 \times 1 = 3$, donc $n(n-2) - 2 \geq 1 > 0$.
Ainsi $2n^2 - 1 \geq (n+1)^2$.
Par transitivité, $2^{n+1} + 1 \geq 2n^2 - 1 \geq (n+1)^2$ : $P(n+1)$ est vraie.
Conclusion. $P(3)$ est vraie et $P$ est héréditaire à partir du rang $3$ ; par récurrence, $P(n)$ est vraie pour tout entier $n \geq 3$.
Comme $P(0)$, $P(1)$ et $P(2)$ sont vraies, on conclut que pour tout $n \in \mathbb{N}$, $2^n + 1 \geq n^2$.
À retenir : on écrit l'hérédité, on lit le rang qu'elle exige (ici $n \geq 3$, car $n(n-2) - 2$ vaut $-2$ pour $n = 2$), on initialise à ce rang, et l'on vérifie à la main, membre par membre, les rangs de l'énoncé situés avant ; la conclusion rassemble les deux.

Signal : l'initialisation est écrite ; il reste à montrer que, pour chaque $n \geq n_0$, $P(n)$ entraîne $P(n+1)$.
1) Ouvrir par : « Soit $n \geq n_0$ tel que $P(n)$ soit vraie. Montrons que $P(n+1)$ est vraie. » L'entier $n$ reste fixé jusqu'à la fin de l'hérédité.
2) Écrire le but $P(n+1)$ en toutes lettres, en remplaçant chaque $n$ par $(n+1)$, parenthèses comprises.
3) Écrire ce que fournit l'hypothèse de récurrence : une égalité, une inégalité, ou un entier $k$ introduit par « il existe ».
4) Aller du rang $n$ vers le but en justifiant chaque ligne : « par hypothèse de récurrence » là où sert $P(n)$, « car $n \geq n_0$ » là où sert le rang.
5) Fermer par : « donc $P(n+1)$ est vraie. »
Rédactions modèles : $2^n \geq n^2$ pour $n \geq 4$ ; divisibilité de $4^n - 1$ par $3$.

Montrer que pour tout entier $n \geq 4$, $2^n \geq n^2$.
Pour tout entier $n \geq 4$, notons $P(n)$ l'assertion : « $2^n \geq n^2$ ».
Initialisation. Pour $n = 4$ : $2^4 = 16$ et $4^2 = 16$, donc $P(4)$ est vraie.
Hérédité. Soit $n \geq 4$ un entier tel que $P(n)$ soit vraie. Montrons $P(n+1)$, c'est-à-dire $2^{n+1} \geq (n+1)^2$.
Par hypothèse de récurrence, $2^n \geq n^2$ ; en multipliant par $2$, qui est positif, on obtient $2^{n+1} \geq 2n^2$.
Comme $n \geq 4$ et $n \geq 0$, on a $n^2 \geq 4n$ ; comme de plus $2n \geq 8 \geq 1$, on a $4n = 2n + 2n \geq 2n + 1$. Donc $n^2 \geq 2n + 1$.
On en déduit $2n^2 = n^2 + n^2 \geq n^2 + 2n + 1 = (n+1)^2$.
Par transitivité, $2^{n+1} \geq 2n^2 \geq (n+1)^2$ : $P(n+1)$ est vraie.
Conclusion. $P(4)$ est vraie et $P$ est héréditaire à partir du rang $4$ ; par récurrence, $2^n \geq n^2$ pour tout entier $n \geq 4$.
À retenir : on initialise au rang annoncé par l'énoncé et on signale la ligne où sert $n \geq 4$ ; aucun départ plus tôt n'était possible, puisque $P(3)$ est fausse ($2^3 = 8 < 9$).

Signal : $P(n)$ est une égalité, typiquement une somme de $n$ termes égale à une formule en $n$.
1) Écrire le but $P(n+1)$ et choisir le membre où l'on peut reconnaître le rang $n$, en général la somme.
2) Partir de ce membre seul et le découper pour y faire apparaître un membre de $P(n)$ : $S_{n+1} = S_n + a_{n+1}$.
3) Remplacer ce morceau par l'autre membre de $P(n)$, en écrivant « par hypothèse de récurrence ».
4) Calculer (développer, factoriser) jusqu'à obtenir exactement l'autre membre de $P(n+1)$.
5) Écrire : « donc $P(n+1)$ est vraie. »
On ne part jamais de l'égalité $P(n+1)$ elle-même. Si le calcul coince, on peut calculer séparément les deux membres de $P(n+1)$ et constater qu'ils coïncident (voir « Démontrer une égalité »).
Rédaction modèle : somme des $n$ premiers entiers impairs.

Montrer par récurrence que pour tout $n \in \mathbb{N}^*$, $1 + 3 + \cdots + (2n-1) = n^2$.
Pour tout $n \in \mathbb{N}^*$, notons $S_n = 1 + 3 + \cdots + (2n-1)$ la somme des $n$ premiers entiers impairs, et $P(n)$ l'assertion : « $S_n = n^2$ ».
Initialisation. Pour $n = 1$ : $S_1 = 1$ et $1^2 = 1$, donc $P(1)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}^*$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$, c'est-à-dire $S_{n+1} = (n+1)^2$.
Le dernier terme de $S_{n+1}$ est $2(n+1) - 1 = 2n + 1$, donc $S_{n+1} = S_n + (2n + 1)$.
Par hypothèse de récurrence, $S_n = n^2$, donc $S_{n+1} = n^2 + 2n + 1 = (n+1)^2$.
Ainsi $P(n+1)$ est vraie.
Conclusion. $P(1)$ est vraie et $P$ est héréditaire à partir du rang $1$ ; par récurrence, pour tout $n \in \mathbb{N}^*$, $1 + 3 + \cdots + (2n-1) = n^2$.
À retenir : on part du membre de $P(n+1)$ qui contient le rang $n$, on y isole $S_n$, on le remplace grâce à $P(n)$, et le calcul s'arrête sur l'autre membre.

Signal : on bloque dans l'hérédité, ou on la relit avant de conclure.
1) Avant tout calcul, écrire ce que fournit $P(n)$ sous la forme exacte où l'on s'en servira : $4^n = 3k + 1$, $S_n = n^2$, $(1+x)^n \geq 1 + nx$.
2) Chercher, dans l'objet du rang $n+1$, la quantité que $P(n)$ contrôle, et l'y faire apparaître par un découpage : $4^{n+1} = 4 \times 4^n$, $(1+x)^{n+1} = (1+x)(1+x)^n$.
3) Appliquer $P(n)$ à cette ligne, avec la mention « par hypothèse de récurrence » ; pour une inégalité, justifier au même endroit le signe du facteur par lequel on multiplie (voir « Rédiger une inégalité »).
4) Signaler de même la ligne où sert chaque autre hypothèse : le rang $n \geq n_0$, les conditions sur un paramètre.
5) Relire : si aucune ligne n'invoque $P(n)$, la preuve est directe (la récurrence est de trop) ou trouée ; si une ligne s'appuie sur $P(n+1)$, elle tourne en rond.
Rédaction modèle : inégalité de Bernoulli.

Pour tout réel $x \geq -1$ et tout $n \in \mathbb{N}$, $(1+x)^n \geq 1 + nx$. Elle se démontre par récurrence sur $n$, à $x$ fixé : l'hypothèse $x \geq -1$ sert à multiplier l'hypothèse de récurrence par $1 + x \geq 0$ sans changer le sens de l'inégalité. Elle minore une puissance par une expression affine en $n$ : pour $q > 1$, avec $x = q - 1 > 0$, on obtient $q^n \geq 1 + n(q-1)$, qui tend vers $+\infty$, donc $q^n$ tend vers $+\infty$ par comparaison.

Soit $x$ un réel tel que $x \geq -1$. Montrer que pour tout $n \in \mathbb{N}$, $(1+x)^n \geq 1 + nx$.
Soit $x$ un réel tel que $x \geq -1$ ; il reste fixé dans toute la démonstration.
Pour tout $n \in \mathbb{N}$, notons $P(n)$ l'assertion : « $(1+x)^n \geq 1 + nx$ ».
Initialisation. Pour $n = 0$ : $(1+x)^0 = 1$ et $1 + 0 \times x = 1$, donc $P(0)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$, c'est-à-dire $(1+x)^{n+1} \geq 1 + (n+1)x$.
Par hypothèse de récurrence, $(1+x)^n \geq 1 + nx$.
Or $(1+x)^{n+1} = (1+x) \times (1+x)^n$.
Comme $x \geq -1$, on a $1 + x \geq 0$ ; en multipliant par $1 + x$ les deux membres de l'hypothèse de récurrence, on conserve le sens de l'inégalité, donc $(1+x)^{n+1} = (1+x)(1+x)^n \geq (1+x)(1+nx)$.
En développant, $(1+x)(1+nx) = 1 + (n+1)x + nx^2$.
De plus $nx^2 \geq 0$ car $n \geq 0$ et $x^2 \geq 0$, donc $(1+x)(1+nx) \geq 1 + (n+1)x$.
Par transitivité, $(1+x)^{n+1} \geq 1 + (n+1)x$ : $P(n+1)$ est vraie.
Conclusion. $P(0)$ est vraie et $P$ est héréditaire ; par récurrence, pour tout $n \in \mathbb{N}$, $(1+x)^n \geq 1 + nx$.
À retenir : le paramètre $x$ est fixé avant le prédicat, et chaque geste a sa ligne : le découpage $(1+x)^{n+1} = (1+x)(1+x)^n$ fait apparaître la quantité que contrôle $P(n)$, puis $x \geq -1$ permet de multiplier par $1 + x$ sans changer le sens.

Signal : l'objet se relie naturellement au rang précédent ($n! = n \times (n-1)!$, $S_n = S_{n-1} + a_n$), ou les expressions sont plus simples au rang $n$ qu'au rang $n+1$.
1) Constater que les deux hérédités sont la même assertion : dans « pour tout $n \geq n_0$, $P(n) \Rightarrow P(n+1)$ », poser $m = n + 1$, puis renommer $m$ en $n$, donne « pour tout $n \geq n_0 + 1$, $P(n-1) \Rightarrow P(n)$ ».
2) Ouvrir par : « Soit $n \geq n_0 + 1$ tel que $P(n-1)$ soit vraie. Montrons que $P(n)$ est vraie. » Le plus petit $n$ admis est celui pour lequel $n - 1 = n_0$.
3) Écrire $P(n-1)$ en remplaçant chaque $n$ par $(n-1)$, puis mener l'hérédité comme d'habitude, en signalant la ligne où sert $n \geq n_0 + 1$.
4) Garder l'initialisation $P(n_0)$ et la conclusion « pour tout $n \geq n_0$ » telles quelles.
Rédaction modèle : $n! \geq 2^{n-1}$ pour tout entier $n \geq 1$.

Montrer que pour tout entier $n \geq 1$, $n! \geq 2^{n-1}$.
Pour tout entier $n \geq 1$, notons $P(n)$ l'assertion : « $n! \geq 2^{n-1}$ ».
Initialisation. Pour $n = 1$ : $1! = 1$ et $2^0 = 1$, donc $P(1)$ est vraie.
Hérédité. Soit $n \geq 2$ un entier tel que $P(n-1)$ soit vraie ; comme $n - 1 \geq 1$, ce rang est bien couvert par l'énoncé. Montrons $P(n)$, c'est-à-dire $n! \geq 2^{n-1}$.
Par hypothèse de récurrence, $(n-1)! \geq 2^{n-2}$.
Or $n! = n \times (n-1)!$ et $n > 0$, donc $n! \geq n \times 2^{n-2}$.
Comme $n \geq 2$ et $2^{n-2} > 0$, on a $n \times 2^{n-2} \geq 2 \times 2^{n-2} = 2^{n-1}$.
Par transitivité, $n! \geq 2^{n-1}$ : $P(n)$ est vraie.
Conclusion. $P(1)$ est vraie et, pour tout entier $n \geq 2$, $P(n-1)$ entraîne $P(n)$ ; par récurrence, $n! \geq 2^{n-1}$ pour tout entier $n \geq 1$.
À retenir : l'hérédité de $n-1$ à $n$ part du rang $n_0 + 1$, ici $2$, et ce rang sert vraiment : pour $n = 1$, la minoration $n \times 2^{n-2} \geq 2 \times 2^{n-2}$ serait fausse.

Signal : l'initialisation et l'hérédité sont démontrées, et seulement alors.
1) Rappeler les deux faits établis : « $P(n_0)$ est vraie et $P$ est héréditaire à partir du rang $n_0$ ».
2) Invoquer le principe : « par récurrence, $P(n)$ est vraie pour tout entier $n \geq n_0$ ».
3) Retraduire, si besoin, dans les termes de l'énoncé : « c'est-à-dire que pour tout $n \geq n_0$, … ».
4) Vérifier que le rang de la conclusion est à la fois celui de l'initialisation et celui de l'énoncé ; si l'énoncé visait des rangs antérieurs, les traiter à part.
On n'écrit ni « donc $P(n)$ est vraie » sans dire pour quels $n$, ni aucune conclusion quand l'initialisation échoue.
Rédactions modèles : somme des entiers impairs ; propriété héréditaire mais toujours fausse.

Pour tout $n \in \mathbb{N}$, on note $P(n)$ l'assertion « $10^n + 1$ est divisible par $9$ ». Montrer que $P$ est héréditaire, mais que $P(n)$ est fausse pour tout $n \in \mathbb{N}$.
Hérédité de $P$. Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Comme $P(n)$ est vraie, il existe un entier $k$ tel que $10^n + 1 = 9k$, c'est-à-dire $10^n = 9k - 1$.
Alors $10^{n+1} + 1 = 10(9k - 1) + 1 = 90k - 9 = 9(10k - 1)$, et $10k - 1$ est un entier, donc $P(n+1)$ est vraie.
Ainsi, pour tout $n \in \mathbb{N}$, $P(n)$ entraîne $P(n+1)$ : $P$ est héréditaire.
Fausseté de $P$. Pour tout $n \in \mathbb{N}$, notons $Q(n)$ l'assertion : « $10^n - 1$ est divisible par $9$ ». Montrons par récurrence que $Q(n)$ est vraie pour tout $n \in \mathbb{N}$.
Initialisation. Pour $n = 0$ : $10^0 - 1 = 0 = 9 \times 0$, donc $Q(0)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ tel que $Q(n)$ soit vraie. Montrons $Q(n+1)$.
Par hypothèse de récurrence, il existe un entier $j$ tel que $10^n - 1 = 9j$.
Alors $10^{n+1} - 1 = 10(10^n - 1) + 9 = 90j + 9 = 9(10j + 1)$, et $10j + 1$ est un entier, donc $Q(n+1)$ est vraie.
Conclusion. $Q(0)$ est vraie et $Q$ est héréditaire ; par récurrence, $Q(n)$ est vraie pour tout $n \in \mathbb{N}$.
Soit maintenant $n \in \mathbb{N}$, et supposons par l'absurde que $P(n)$ est vraie.
Alors $9$ divise $10^n + 1$ et, d'après $Q(n)$, $9$ divise $10^n - 1$ ; donc $9$ divise leur différence $(10^n + 1) - (10^n - 1) = 2$, ce qui est absurde car $0 < 2 < 9$.
Donc $P(n)$ est fausse ; l'entier $n$ étant quelconque, $P(n)$ est fausse pour tout $n \in \mathbb{N}$.
À retenir : une hérédité démontrée ne conclut rien tant qu'aucun rang n'est initialisé ; ici, aucun rang ne peut servir d'initialisation.