Choisir la propriété de récurrence

Démontrer un énoncé par récurrence, c'est choisir un entier $n$, la variable de récurrence, et une propriété $P(n)$ où $n$ est libre, puis établir $P(n)$ pour tout $n \ge n_0$. Chacun des autres objets de l'énoncé reçoit l'un de deux statuts : il est fixé avant la récurrence, et $P(n)$ parle de lui sans le quantifier, ou bien il est quantifié à l'intérieur de $P(n)$. Un objet que l'énoncé définit lui-même, comme une suite donnée par ses premiers termes et sa relation de récurrence, est fixé d'office. Choisir la propriété de récurrence, c'est trancher trois questions : quelle variable, quoi fixer, quoi quantifier. On vérifie enfin que l'énoncé demandé découle de « pour tout $n \ge n_0$, $P(n)$ ».

Tout entier quantifié par « pour tout » dans l'énoncé peut servir de variable : pour démontrer $\forall m \in \mathbb{N},\ \forall n \in \mathbb{N},\ Q(m,n)$, il suffit d'établir par récurrence sur $n$ la propriété $P(n)$ : « $\forall m \in \mathbb{N},\ Q(m,n)$ », ou bien, pour chaque $m$ fixé, la propriété $Q(m,n)$. Si l'énoncé ne contient aucun entier (« toute famille finie de réels », « tout ensemble fini »), on en crée un : le nombre de termes, de réels ou d'éléments. La logique laisse donc le choix, et c'est l'hérédité qui le tranche : la variable est l'entier qui diminue quand on ramène le cas étudié à un cas plus petit. Pour majorer $\binom{n}{k}$, la formule de Pascal $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$, où $1 \le k \le n$, fait baisser $n$ dans les deux termes, tandis que $k$ reste ou baisse : la variable est $n$, et $k$, qui prend deux valeurs, se quantifie dans $P(n)$ (Méthode « Décider si un paramètre se fixe avant la récurrence ou se quantifie dans P(n) »).

Pour démontrer qu'une propriété vaut pour tous les objets d'une classe (familles finies de réels, sommes, produits, ensembles finis), on associe à chaque objet sa taille $n$ : nombre de termes, de réels, d'éléments. On démontre alors par récurrence $P(n)$ : « tout objet de taille $n$ a la propriété ». Comme chaque objet a une taille, « pour tout $n$, $P(n)$ » couvre tous les objets. L'objet ne peut pas être fixé avant la récurrence, puisque sa taille est $n$ : il est quantifié dans $P(n)$.

Signal : l'énoncé porte sur « tous réels $x_1, \dots, x_n$ », « toute partie à $n$ éléments », « toute somme de $n$ termes ».
1) Poser la propriété, l'objet quantifié dedans : « Pour $n \in \mathbb{N}^*$, notons $P(n)$ : pour tous réels $x_1, \dots, x_n$, … ».
2) Ouvrir l'hérédité, puis fixer un objet quelconque de taille $n + 1$ : « Soit $n \in \mathbb{N}^*$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$. Soit $x_1, \dots, x_{n+1}$ des réels. »
3) En extraire un objet de taille $n$ qui vérifie les hypothèses de $P(n)$, le plus souvent en retirant un terme.
4) Appliquer $P(n)$ en nommant l'objet : « D'après $P(n)$ appliquée aux $n$ réels $x_1, \dots, x_n$, … ».
5) Revenir à l'objet de départ en réintégrant le terme retiré, puis écrire la conclusion de $P(n+1)$ pour $x_1, \dots, x_{n+1}$.
6) Clore : « Les réels $x_1, \dots, x_{n+1}$ étant quelconques, $P(n+1)$ est vraie. »
L'ordre est imposé : on part de l'objet de taille $n + 1$ pour descendre à la taille $n$, jamais l'inverse.

Montrer que pour tout $n \in \mathbb{N}^*$ et tous réels $x_1, \dots, x_n$, l'un des $x_i$ est supérieur ou égal à tous les autres.
Pour $n \in \mathbb{N}^*$, notons $P(n)$ : « pour tous réels $x_1, \dots, x_n$, il existe $i \in \llbracket 1, n \rrbracket$ tel que pour tout $j \in \llbracket 1, n \rrbracket$, $x_i \ge x_j$ ».
Les réels sont au nombre de $n$ : ils ne peuvent pas être choisis avant $n$, ils sont donc quantifiés dans $P(n)$.
Initialisation. Soit $x_1$ un réel. Le seul indice de $\llbracket 1, 1 \rrbracket$ est $1$, et $x_1 \ge x_1$ : l'indice $i = 1$ convient. Donc $P(1)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}^*$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Soit $x_1, \dots, x_{n+1}$ des réels.
D'après $P(n)$ appliquée aux $n$ réels $x_1, \dots, x_n$, il existe $i \in \llbracket 1, n \rrbracket$ tel que $x_i \ge x_j$ pour tout $j \in \llbracket 1, n \rrbracket$.
Premier cas : $x_i \ge x_{n+1}$. Alors $x_i \ge x_j$ pour tout $j \in \llbracket 1, n+1 \rrbracket$, et $i \in \llbracket 1, n+1 \rrbracket$ : l'indice $i$ convient.
Second cas : $x_i < x_{n+1}$. Pour tout $j \in \llbracket 1, n \rrbracket$, on a $x_j \le x_i < x_{n+1}$, donc $x_{n+1} \ge x_j$ ; de plus $x_{n+1} \ge x_{n+1}$. Ainsi l'indice $n + 1$ convient.
Dans les deux cas, un indice de $\llbracket 1, n+1 \rrbracket$ convient. Les réels $x_1, \dots, x_{n+1}$ étant quelconques, $P(n+1)$ est vraie.
Conclusion. Par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}^*$, ce qui est le résultat demandé.
À retenir : l'hérédité fixe d'abord $n + 1$ réels quelconques, applique $P(n)$ aux $n$ premiers, puis réintègre le dernier par une disjonction de cas.

Énoncé : pour tout $n \in \mathbb{N}^*$, parmi $n$ réels de somme nulle, l'un au moins est négatif ou nul.
Ligne fautive : « Soit $x_1, \dots, x_n$ des réels de somme nulle ; d'après $P(n)$, l'un d'eux est négatif ou nul. Ajoutons un réel $x_{n+1}$ : pour que la somme reste nulle, $x_{n+1} = 0$, et la famille $x_1, \dots, x_{n+1}$ contient encore un réel négatif ou nul. »
On n'a traité que les familles de $n + 1$ réels dont le dernier terme est nul : la famille $(1, 1, -2)$ n'est pas obtenue ainsi. Or $P(n+1)$ porte sur toutes les familles de taille $n + 1$.
Version correcte : partir de la grande famille, « Soit $x_1, \dots, x_{n+1}$ des réels de somme nulle ». Si $x_{n+1} \le 0$, c'est fini. Sinon $x_1 + \cdots + x_n = -x_{n+1} < 0$ : la sous-famille n'est plus de somme nulle, et $P(n)$ ne s'applique pas. On pose donc, dès le départ, une propriété élargie, sous un nouveau nom, $Q(n)$ : « parmi $n$ réels de somme négative ou nulle, l'un au moins est négatif ou nul ».
Dans l'hérédité, on suppose $Q(n)$ et l'on écrit : « Soit $x_1, \dots, x_{n+1}$ des réels de somme $s \le 0$. Si $x_{n+1} \le 0$, c'est fini. Sinon $x_1 + \cdots + x_n = s - x_{n+1} < s \le 0$ ; d'après $Q(n)$ appliquée aux réels $x_1, \dots, x_n$, l'un d'eux est négatif ou nul. »
Enfin, une famille de somme nulle est de somme négative ou nulle : $Q(n)$ entraîne l'énoncé demandé.

Soit à démontrer $\forall a \in A,\ \forall n \ge n_0,\ Q(a,n)$. Fixer $a$ avant la récurrence, c'est démontrer, pour chaque $a$, la propriété $P_a(n) : Q(a,n)$ ; l'hypothèse de récurrence ne parle alors que de ce $a$. Quantifier $a$, c'est poser $P(n) : \forall a \in A,\ Q(a,n)$ ; l'hypothèse de récurrence s'applique alors à tout élément de $A$, mais la conclusion doit être établie pour tous. Les deux choix démontrent le même énoncé final, et le second est toujours permis. Un objet dont la définition fait intervenir $n$, comme une famille de $n$ réels, ne peut être que quantifié.

Signal : l'énoncé contient, en plus de $n$, un réel, une fonction, une suite ou une famille.
1) Écrire l'hérédité au brouillon et repérer à quel objet on applique $P(n)$.
2) Si la définition de l'objet fait intervenir $n$ (une famille $x_1, \dots, x_n$, une partie à $n$ éléments), il ne peut pas exister avant $n$ : le quantifier dans $P(n)$.
3) Si l'objet ne dépend pas de $n$ et que l'hérédité applique $P(n)$ au même objet, le fixer avant la récurrence : « Soit $a \ge 0$. Pour $n \in \mathbb{N}$, notons $P(n)$ : … ». Ses hypothèses restent alors disponibles à tous les rangs.
4) Si l'hérédité applique $P(n)$ à un autre objet ($x + 1$ au lieu de $x$, une famille privée d'un terme), le quantifier : « Pour $n \in \mathbb{N}$, notons $P(n)$ : pour tout réel $x$, … », puis ouvrir l'hérédité par « Soit $x$ un réel. ».
5) En cas de doute, quantifier : quand l'énoncé final porte sur tous ces objets, c'est toujours légitime.
Sur la copie, la place du « soit » tranche : écrit avant la définition de $P(n)$, il fixe l'objet pour tous les rangs ; écrit dans l'hérédité, il introduit un objet quelconque au rang considéré.

Montrer que pour tout réel $a \ge 0$ et tout $n \in \mathbb{N}$, $(1+a)^n \ge 1 + na + \frac{n(n-1)}{2}a^2$.
Soit $a \ge 0$. Ce réel ne dépend pas de $n$, et l'hérédité n'utilisera la propriété que pour ce même réel : on le fixe avant la récurrence.
Pour $n \in \mathbb{N}$, notons $P(n)$ : « $(1+a)^n \ge 1 + na + \frac{n(n-1)}{2}a^2$ ».
Initialisation. On a $(1+a)^0 = 1$ et $1 + 0 \cdot a + \frac{0 \cdot (0-1)}{2}a^2 = 1$. Donc $P(0)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
D'après $P(n)$, $(1+a)^n \ge 1 + na + \frac{n(n-1)}{2}a^2$.
Or $1 + a > 0$ car $a \ge 0$. En multipliant l'inégalité précédente par ce réel strictement positif, on obtient $(1+a)^{n+1} \ge \left(1 + na + \frac{n(n-1)}{2}a^2\right)(1+a)$.
En développant, $\left(1 + na + \frac{n(n-1)}{2}a^2\right)(1+a) = 1 + (n+1)a + \left(\frac{n(n-1)}{2} + n\right)a^2 + \frac{n(n-1)}{2}a^3$.
Or $\frac{n(n-1)}{2} + n = \frac{n^2 + n}{2} = \frac{(n+1)n}{2}$.
De plus, $a^3 \ge 0$ car $a \ge 0$, et $n(n-1) \ge 0$ car, $n$ étant un entier naturel, ou bien $n = 0$, ou bien $n$ et $n - 1$ sont positifs ; donc $\frac{n(n-1)}{2}a^3 \ge 0$.
Ainsi $(1+a)^{n+1} \ge 1 + (n+1)a + \frac{(n+1)n}{2}a^2 + \frac{n(n-1)}{2}a^3 \ge 1 + (n+1)a + \frac{(n+1)n}{2}a^2$, ce qui est $P(n+1)$.
Conclusion. Par récurrence, pour tout $n \in \mathbb{N}$, $(1+a)^n \ge 1 + na + \frac{n(n-1)}{2}a^2$. Le réel $a \ge 0$ étant quelconque, l'inégalité est établie pour tout réel $a \ge 0$ et tout $n \in \mathbb{N}$.
À retenir : un paramètre indépendant de $n$, que l'hérédité ne remplace par aucune autre valeur, s'introduit par « Soit » avant la définition de $P(n)$, et son hypothèse $a \ge 0$ reste utilisable à chaque rang.

Montrer que pour tout $n \in \mathbb{N}^*$ et tous réels $x_1, \dots, x_n$ de $[0,1]$, $(1-x_1)(1-x_2)\cdots(1-x_n) \ge 1 - (x_1 + x_2 + \cdots + x_n)$.
Les réels $x_1, \dots, x_n$ sont au nombre de $n$ : ils ne peuvent pas être fixés avant $n$. De plus, au rang $n + 1$, la propriété sera appliquée à une sous-famille de la famille considérée : elle doit donc valoir pour toute famille de $n$ réels de $[0,1]$. Ces réels sont quantifiés dans la propriété.
Pour $n \in \mathbb{N}^*$, notons $P(n)$ : « pour tous réels $x_1, \dots, x_n$ de $[0,1]$, $(1-x_1)\cdots(1-x_n) \ge 1 - (x_1 + \cdots + x_n)$ ».
Initialisation. Soit $x_1 \in [0,1]$. On a $1 - x_1 \ge 1 - x_1$. Donc $P(1)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}^*$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Soit $x_1, \dots, x_{n+1}$ des réels de $[0,1]$. Posons $p = (1-x_1)\cdots(1-x_n)$ et $s = x_1 + \cdots + x_n$.
Les réels $x_1, \dots, x_n$ sont dans $[0,1]$, donc, d'après $P(n)$ appliquée à ces $n$ réels, $p \ge 1 - s$.
Or $1 - x_{n+1} \ge 0$ car $x_{n+1} \le 1$. En multipliant par ce réel positif, on obtient $p(1-x_{n+1}) \ge (1-s)(1-x_{n+1})$.
En développant, $(1-s)(1-x_{n+1}) = 1 - (s + x_{n+1}) + s\,x_{n+1}$.
Or $s \ge 0$, comme somme de réels positifs, et $x_{n+1} \ge 0$ ; donc $s\,x_{n+1} \ge 0$.
Ainsi $(1-x_1)\cdots(1-x_{n+1}) = p(1-x_{n+1}) \ge 1 - (s + x_{n+1}) + s\,x_{n+1} \ge 1 - (s + x_{n+1})$.
Comme $s + x_{n+1} = x_1 + \cdots + x_{n+1}$, on a obtenu $(1-x_1)\cdots(1-x_{n+1}) \ge 1 - (x_1 + \cdots + x_{n+1})$. Les réels $x_1, \dots, x_{n+1}$ de $[0,1]$ étant quelconques, $P(n+1)$ est vraie.
Conclusion. Par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}^*$, ce qui est le résultat demandé.
À retenir : une famille dont la taille est $n$ se quantifie dans $P(n)$ ; l'hérédité fixe une famille quelconque de taille $n + 1$, puis applique $P(n)$ à la sous-famille, nommée explicitement.

Ligne fautive : « Soit $x_1, \dots, x_n$ des réels de $[0,1]$. Montrons par récurrence sur $n$ que $(1-x_1)\cdots(1-x_n) \ge 1 - (x_1 + \cdots + x_n)$. »
L'entier $n$ sert avant d'être introduit, et la famille est fixée avec $n$ termes : dans l'hérédité, le réel $x_{n+1}$ n'existe pas, et l'hypothèse ne parle que de cette seule famille. Même faute avec « Posons $\varepsilon = \frac{1}{n}$ » écrit avant la récurrence : un objet fixé est le même à tous les rangs, il ne peut pas varier avec $n$.
Version correcte : « Pour $n \in \mathbb{N}^*$, notons $P(n)$ : pour tous réels $x_1, \dots, x_n$ de $[0,1]$, $(1-x_1)\cdots(1-x_n) \ge 1 - (x_1 + \cdots + x_n)$. » Les réels sont introduits dans l'hérédité : « Soit $x_1, \dots, x_{n+1}$ des réels de $[0,1]$. »

Contexte : $g : \mathbb{R} \to \mathbb{R}$ vérifie $g(x+1) \ge g(x) + 1$ pour tout réel $x$, et l'on veut $g(x+n) \ge g(x) + n$ pour tout réel $x$ et tout $n \in \mathbb{N}$.
Ligne fautive : « Soit $x$ un réel. Notons $P(n)$ : $g(x+n) \ge g(x) + n$. […] D'après $P(n)$, $g(x+n+1) = g\big((x+1)+n\big) \ge g(x+1) + n$. »
La propriété $P(n)$ ne parle que du réel $x$ fixé ; l'appliquer au réel $x + 1$ invoque une hypothèse que l'on n'a pas.
Version correcte, au choix. Garder $x$ fixé et découper autrement : « $g(x+n+1) = g\big((x+n)+1\big) \ge g(x+n) + 1$ par hypothèse sur $g$, et $g(x+n) + 1 \ge g(x) + n + 1$ d'après $P(n)$ ». Ou bien quantifier : « Notons $P(n)$ : pour tout réel $y$, $g(y+n) \ge g(y) + n$ », puis appliquer $P(n)$ au réel $y = x + 1$.

Si $Q(n)$ entraîne $P(n)$ pour tout $n \ge n_0$, démontrer par récurrence « pour tout $n \ge n_0$, $Q(n)$ » établit « pour tout $n \ge n_0$, $P(n)$ ». La propriété plus forte demande davantage à conclure, mais elle fournit une hypothèse de récurrence plus riche, et c'est souvent ce qui fait passer l'hérédité. Une propriété vraie à tous les rangs peut en effet avoir une hérédité qu'on ne sait pas démontrer : si $P(n)$ ne contient pas l'information dont le calcul de $P(n+1)$ a besoin, on ne peut établir $P(n+1)$ à partir de $P(n)$ sans connaître déjà le résultat. On renforce en remplaçant une borne constante par une borne dépendant de $n$, en ajoutant une information (un encadrement au lieu d'une minoration) ou en élargissant la classe des objets.

Signal : au brouillon, on aboutit à « il faudrait encore que … » sans pouvoir le tirer de l'hypothèse.
1) Tester l'énoncé sur les premières valeurs : un contre-exemple le réfute. S'il résiste, l'échec vient le plus souvent de la propriété choisie, non de l'énoncé.
2) Écrire la ligne exacte où l'on bloque, nommer ce qui manque, puis appliquer le remède correspondant.
3) Il manque une marge (de $1 + \frac{1}{4} + \cdots + \frac{1}{n^2} \le 2$, on ne tire au rang suivant qu'une majoration par $2 + \frac{1}{(n+1)^2}$) : remplacer la borne constante par une borne dépendant de $n$.
4) Il manque une information (le signe de $1 - u_n$, quand $P(n)$ dit seulement $u_n > 0$) : ajouter cette information à $P(n)$.
5) L'hypothèse porte sur le mauvais objet (on voudrait $P(n)$ en $x + 1$, alors que $x$ est fixé) : quantifier ce paramètre dans $P(n)$.
6) L'objet extrait ne vérifie pas les hypothèses de $P(n)$ (une sous-famille d'une famille de somme nulle n'est plus de somme nulle) : élargir ces hypothèses.
7) L'étape fait appel à un autre rang que $n$ : passer à une récurrence double ou forte.
Sur la copie, on annonce en une phrase la propriété retenue et sa raison : « L'hypothèse $u_n > 0$ ne donne pas le signe de $1 - u_n$ ; on démontre donc la propriété plus forte $P(n)$ : $0 < u_n < 1$. »

Soit $a \in \left]0,1\right[$ et $(u_n)$ la suite définie par $u_0 = a$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = u_n(1-u_n)$. Montrer que $u_n > 0$ pour tout $n \in \mathbb{N}$.
Le signe de $u_{n+1} = u_n(1-u_n)$ dépend de celui de $1 - u_n$, que l'hypothèse $u_n > 0$ ne donne pas. On démontre donc une propriété plus forte.
Pour $n \in \mathbb{N}$, notons $P(n)$ : « $0 < u_n < 1$ ».
Initialisation. $u_0 = a$ et $0 < a < 1$. Donc $P(0)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
D'après $P(n)$, $u_n > 0$ et $u_n < 1$ ; donc $1 - u_n > 0$.
Ainsi $u_{n+1} = u_n(1-u_n)$ est le produit de deux réels strictement positifs, donc $u_{n+1} > 0$.
Par ailleurs, $u_n > 0$, donc $1 - u_n < 1$ ; en multipliant cette inégalité par le réel strictement positif $u_n$, on obtient $u_n(1-u_n) < u_n$, c'est-à-dire $u_{n+1} < u_n$.
Or $u_n < 1$, donc $u_{n+1} < 1$.
Ainsi $0 < u_{n+1} < 1$ : $P(n+1)$ est vraie.
Conclusion. Par récurrence, $0 < u_n < 1$ pour tout $n \in \mathbb{N}$ ; en particulier, $u_n > 0$ pour tout $n \in \mathbb{N}$.
À retenir : quand l'hérédité réclame une information que l'hypothèse ne contient pas, on l'ajoute à $P(n)$, puis l'on démontre au rang $n + 1$ chacune des deux parties.

Signal : on veut majorer par une constante $M$ une quantité qui augmente à chaque rang, $S_{n+1} = S_n + t_{n+1}$ avec $t_{n+1} > 0$, et l'hypothèse $S_n \le M$ ne laisse aucune marge pour absorber $t_{n+1}$.
1) Chercher une borne $M - b_n$, avec $b_n \ge 0$, dont la marge $b_n$ absorbe le terme ajouté : il suffit que $b_n - b_{n+1} \ge t_{n+1}$ pour tout $n \ge n_0$. Pour trouver $b_n$, majorer le terme ajouté par une différence télescopique : $\frac{1}{(n+1)^2} \le \frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$ donne $b_n = \frac{1}{n}$. En sommant ces conditions d'un rang au suivant, on voit que $b_n$ majore toute somme $t_{n+1} + \cdots + t_N$ : la marge doit couvrir tout ce qui reste à ajouter.
2) Vérifier l'initialisation $S_{n_0} \le M - b_{n_0}$. Si elle échoue, il faut une marge plus petite, par exemple $\frac{1}{2}b_n$ : l'initialisation devient plus facile, mais l'écart $b_n - b_{n+1}$ est lui aussi divisé par deux, et la condition de l'étape 1 est à revérifier pour cette nouvelle marge.
3) Annoncer : « Montrons par récurrence la propriété plus forte $Q(n)$ : $S_n \le M - b_n$. »
4) Dans l'hérédité, écrire $S_{n+1} = S_n + t_{n+1} \le M - b_n + t_{n+1}$ d'après $Q(n)$, puis établir $M - b_n + t_{n+1} \le M - b_{n+1}$ en calculant la différence des deux membres.
5) Conclure en deux temps : « Par récurrence, $Q(n)$ est vraie pour tout $n \ge n_0$. Or $b_n \ge 0$, donc $S_n \le M$ pour tout $n \ge n_0$. »

Montrer que pour tout $n \in \mathbb{N}^*$, $1 + \frac{1}{4} + \cdots + \frac{1}{n^2} \le 2$.
Pour $n \in \mathbb{N}^*$, posons $S_n = \sum_{k=1}^{n} \frac{1}{k^2}$.
L'hypothèse $S_n \le 2$ ne suffit pas à établir $S_{n+1} \le 2$ : elle ne donne que $S_{n+1} = S_n + \frac{1}{(n+1)^2} \le 2 + \frac{1}{(n+1)^2}$. On démontre donc une propriété plus forte.
Pour $n \in \mathbb{N}^*$, notons $Q(n)$ : « $S_n \le 2 - \frac{1}{n}$ ».
Initialisation. $S_1 = 1$ et $2 - \frac{1}{1} = 1$. Donc $Q(1)$ est vraie.
Hérédité. Soit $n \in \mathbb{N}^*$ tel que $Q(n)$ soit vraie. Montrons $Q(n+1)$.
D'après $Q(n)$, $S_{n+1} = S_n + \frac{1}{(n+1)^2} \le 2 - \frac{1}{n} + \frac{1}{(n+1)^2}$.
Comparons ce majorant à $2 - \frac{1}{n+1}$ en calculant leur différence :
$\left(2 - \frac{1}{n+1}\right) - \left(2 - \frac{1}{n} + \frac{1}{(n+1)^2}\right) = \frac{1}{n} - \frac{1}{n+1} - \frac{1}{(n+1)^2} = \frac{1}{n(n+1)} - \frac{1}{(n+1)^2} = \frac{(n+1) - n}{n(n+1)^2} = \frac{1}{n(n+1)^2}$.
Or $n \ge 1$, donc $\frac{1}{n(n+1)^2} > 0$, et par suite $2 - \frac{1}{n} + \frac{1}{(n+1)^2} < 2 - \frac{1}{n+1}$.
Ainsi $S_{n+1} \le 2 - \frac{1}{n+1}$ : $Q(n+1)$ est vraie.
Conclusion. Par récurrence, $S_n \le 2 - \frac{1}{n}$ pour tout $n \in \mathbb{N}^*$.
Enfin, soit $n \in \mathbb{N}^*$. Comme $\frac{1}{n} > 0$, on a $S_n \le 2 - \frac{1}{n} < 2$, donc $S_n \le 2$.
À retenir : on démontre par récurrence la borne héréditaire $2 - \frac{1}{n}$, puis, une fois la récurrence conclue, on en déduit la borne constante en une ligne.

Avec $S_n = \sum_{k=1}^{n} \frac{1}{k^2}$, ligne fautive : « Supposons $S_n \le 2$. Alors $S_{n+1} = S_n + \frac{1}{(n+1)^2} \le 2$. »
La dernière inégalité ne découle pas de l'hypothèse, qui donne seulement $S_{n+1} \le 2 + \frac{1}{(n+1)^2}$ : le terme positif a été effacé pour obtenir la conclusion attendue. La réaction inverse est tout aussi fautive : déclarer l'énoncé faux parce que l'hérédité ne passe pas, alors que $S_n \le 2$ est vrai pour tout $n \ge 1$.
Version correcte : « L'hypothèse $S_n \le 2$ ne suffit pas à établir $S_{n+1} \le 2$. Montrons par récurrence la propriété plus forte $Q(n)$ : $S_n \le 2 - \frac{1}{n}$. » On démontre $Q(n)$ pour tout $n \ge 1$, puis on en déduit $S_n \le 2$.

Avec $S_n = \sum_{k=1}^{n} \frac{1}{k^2}$, ligne fautive : « Notons $Q(n)$ : $S_n \le 2 - \frac{1}{n}$. […] Soit $n \ge 1$ tel que $Q(n)$ soit vraie. […] Donc $S_{n+1} \le 2$, ce qui achève l'hérédité. »
L'hérédité devait établir $Q(n+1)$, soit $S_{n+1} \le 2 - \frac{1}{n+1}$ : avec $S_{n+1} \le 2$ seulement, l'hypothèse du rang suivant n'est pas acquise et la chaîne des rangs est rompue. La faute symétrique annonce $P(n)$ : $S_n \le 2$, puis suppose $S_n \le 2 - \frac{1}{n}$ dans l'hérédité : on s'accorde alors à chaque rang plus que ce qui a été démontré au rang précédent.
Version correcte : écrire la propriété une seule fois, supposer exactement $Q(n)$, et vérifier que la dernière ligne de l'hérédité est mot pour mot $Q(n+1)$. Le résultat demandé ne se déduit qu'après la conclusion de la récurrence.

Les récurrences simple, double et forte démontrent la même chose, « pour tout $n \ge n_0$, $P(n)$ », et chacune se ramène à une récurrence simple sur une propriété auxiliaire. Elles diffèrent par l'hypothèse disponible dans l'hérédité : $P(n)$ seule ; $P(n)$ et $P(n+1)$ pour conclure $P(n+2)$ ; $P(k)$ pour tout $k \in \llbracket n_0, n \rrbracket$. L'initialisation suit : $P(n_0)$ pour la simple et pour la forte, $P(n_0)$ et $P(n_0+1)$ pour la double ; en forte, on traite en outre à part les petits rangs pour lesquels l'étape n'a aucun rang inférieur utilisable. On choisit la plus petite hypothèse qui contient tous les rangs réellement utilisés.

Signal : avant d'écrire « Soit $n$ tel que … », il faut choisir entre récurrence simple, double et forte.
1) Au brouillon, exprimer l'objet du rang à atteindre à l'aide d'objets de rangs inférieurs, lister les rangs qui apparaissent et noter leur distance au rang visé.
2) Seul le rang précédent apparaît ($u_{n+1} = f(u_n)$) : récurrence simple, « Soit $n \ge n_0$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$. »
3) Les deux rangs précédents apparaissent ($u_{n+2} = \alpha u_{n+1} + \beta u_n$) : récurrence double, avec deux initialisations, « Soit $n \ge n_0$ tel que $P(n)$ et $P(n+1)$ soient vraies. Montrons $P(n+2)$. »
4) Les rangs utilisés sont à distance fixe du rang visé, la plus grande valant $d$ ($u_{n+2} = f(u_n)$ : $d = 2$ ; $u_{n+3} = f(u_n, u_{n+1})$ : $d = 3$) : prendre pour hypothèse les $d$ rangs consécutifs $P(n), \dots, P(n+d-1)$, initialiser les $d$ premiers rangs $P(n_0), \dots, P(n_0+d-1)$, et montrer $P(n+d)$. Pour $d = 2$, c'est la récurrence double, même si l'étape n'utilise que $P(n)$ ; on peut aussi raisonner par récurrence forte.
5) Un rang à distance variable apparaît ($\lfloor \frac{n+1}{2} \rfloor$, un diviseur de $n + 1$, les morceaux d'une décomposition), ou bien tous les rangs précédents : récurrence forte, « Soit $n \ge n_0$ tel que $P(k)$ soit vraie pour tout $k \in \llbracket n_0, n \rrbracket$. Montrons $P(n+1)$. »
6) En forte, justifier sur la copie que chaque rang utilisé appartient à $\llbracket n_0, n \rrbracket$.
7) Relire l'hérédité rédigée : si elle n'invoque que $P(n)$ pour conclure $P(n+1)$, la réécrire en récurrence simple ; si elle invoque un rang que l'hypothèse annoncée ne couvre pas, changer d'hypothèse.

Soit $(u_n)_{n \ge 1}$ la suite définie par $u_1 = 0$ et, pour tout entier $n \ge 2$, $u_n = u_{\lfloor n/2 \rfloor} + 1$. Montrer que pour tout entier $n \ge 1$, $2^{u_n} \le n$.
Le terme $u_{n+1}$ s'exprime à l'aide de $u_{\lfloor (n+1)/2 \rfloor}$, dont le rang n'est en général ni $n$ ni $n - 1$ : on raisonne par récurrence forte.
Pour tout entier $n \ge 1$, notons $P(n)$ : « $2^{u_n} \le n$ ».
Initialisation. $u_1 = 0$ et $2^0 = 1 \le 1$. Donc $P(1)$ est vraie.
Hérédité. Soit $n \ge 1$ un entier tel que $P(k)$ soit vraie pour tout $k \in \llbracket 1, n \rrbracket$. Montrons $P(n+1)$.
Posons $m = \lfloor \frac{n+1}{2} \rfloor$. Comme $n + 1 \ge 2$, la définition de la suite donne $u_{n+1} = u_m + 1$.
Vérifions que $m \in \llbracket 1, n \rrbracket$. D'une part, $\frac{n+1}{2} \ge 1$ car $n \ge 1$ ; comme $m$ est le plus grand entier inférieur ou égal à $\frac{n+1}{2}$ et que l'entier $1$ en est un, $m \ge 1$. D'autre part, $m \le \frac{n+1}{2} \le n$, car $n + 1 \le 2n$ lorsque $n \ge 1$.
D'après l'hypothèse de récurrence appliquée au rang $m$, on a donc $2^{u_m} \le m$.
Ainsi $2^{u_{n+1}} = 2^{u_m + 1} = 2 \cdot 2^{u_m} \le 2m$.
Or $m \le \frac{n+1}{2}$, donc $2m \le n + 1$.
Par conséquent $2^{u_{n+1}} \le n + 1$ : $P(n+1)$ est vraie.
Conclusion. Par récurrence forte, $2^{u_n} \le n$ pour tout entier $n \ge 1$.
À retenir : on liste d'abord les rangs dont dépend l'étape ; un rang à distance variable impose la récurrence forte, et la copie vérifie que ce rang appartient à $\llbracket 1, n \rrbracket$.