Récurrence finie, descendante et sur d'autres ensembles d'indices

Pour deux entiers $a$ et $b$, on note $[\![a, b]\!]$ l'ensemble des entiers $n$ tels que $a \leq n \leq b$ ; il est vide si $a > b$ et compte $b - a + 1$ éléments si $a \leq b$. Un prédicat indexé par $[\![n_0, N]\!]$ associe à chaque entier $n$ de cet intervalle une assertion $P(n)$, et à aucun autre entier. On borne ainsi le prédicat quand les objets dont il parle n'existent que pour ces rangs : termes $u_0, \dots, u_N$ d'une famille finie, valeur d'une variable après chacun des $N$ passages d'une boucle.

Une récurrence est montante quand son hérédité va du rang $n$ au rang $n + 1$, et descendante quand elle va du rang $n + 1$ au rang $n$. Elle est finie quand ses indices parcourent un intervalle $[\![n_0, N]\!]$. Le pas décrit le passage d'un rang à l'autre dans l'hérédité : ajouter $1$, retirer $1$, ajouter $2$, ou doubler. Dans la conclusion, « par récurrence finie » ou « par récurrence descendante » nomme le principe invoqué, et l'on écrit ensuite explicitement l'ensemble atteint : « pour tout $n \in [\![n_0, N]\!]$ ». La phrase « soit $n \in [\![n_0, N - 1]\!]$ tel que $P(n)$ soit vraie » fixe un seul entier $n$ et ne suppose $P$ qu'en ce rang, jamais en tous.

L'ensemble atteint par une récurrence est l'ensemble des rangs qu'on obtient en partant des rangs initialisés et en appliquant l'hérédité autant de fois qu'on veut, chaque fois à un rang où elle a été démontrée. C'est exactement l'ensemble sur lequel la récurrence permet de conclure. Par exemple, une initialisation au rang $0$ suivie d'une hérédité qui passe de $n$ à $n + 2$ atteint les entiers pairs, et eux seuls. On le détermine avant de rédiger : s'il ne contient pas tous les rangs de la question, il manque une initialisation, une seconde récurrence ou une descente.

Soient $n_0 \leq N$ deux entiers et $P$ un prédicat indexé par $[\![n_0, N]\!]$. Si $P(n_0)$ est vraie et si, pour tout $n \in [\![n_0, N - 1]\!]$, $P(n)$ entraîne $P(n + 1)$, alors $P(n)$ est vraie pour tout $n \in [\![n_0, N]\!]$. Ce principe découle de la récurrence simple appliquée, pour $n \geq n_0$, à l'assertion « si $n \leq N$, alors $P(n)$ », vraie d'office dès que $n > N$.

Dans une récurrence finie sur $[\![n_0, N]\!]$, l'hérédité se démontre pour $n \in [\![n_0, N - 1]\!]$ : ce sont exactement les rangs $n$ tels que $n$ et $n + 1$ appartiennent tous deux à l'intervalle. La borne $n \leq N - 1$ n'est pas une contrainte subie mais une hypothèse disponible : pour une famille $u_{n_0}, \dots, u_N$, elle garantit que $u_{n+1}$ existe et que les relations données pour $n \leq N - 1$ s'appliquent au rang $n$. On la cite à l'endroit où elle sert. Si $N = n_0$, il n'y a aucune hérédité à démontrer et l'initialisation suffit.

Signal dans l'énoncé : les objets ne sont définis que jusqu'à un rang $N$ (famille $u_0, \dots, u_N$, boucle de $N$ passages), ou une hypothèse n'est donnée que pour $n \leq N - 1$.
1) Poser le prédicat avec son intervalle : « Pour tout $n \in [\![n_0, N]\!]$, notons $P(n)$ l'assertion : … »
2) Initialiser : « On a …, donc $P(n_0)$ est vraie. »
3) Ouvrir l'hérédité en bornant $n$ : « Soit $n \in [\![n_0, N - 1]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$. »
4) Citer la borne là où elle sert : « Comme $n \leq N - 1$, l'hypothèse … s'applique au rang $n$. » Utiliser ensuite $P(n)$ et finir par « donc $P(n + 1)$ est vraie ».
5) Conclure sur l'intervalle, et sur lui seul : « Par récurrence finie, $P(n)$ est vraie pour tout $n \in [\![n_0, N]\!]$. »

Soient $N \in \mathbb{N}^*$ et $u_0, \dots, u_N$ des réels tels que $u_0 = 0$ et, pour tout $n \in [\![0, N - 1]\!]$, $u_{n+1} \leq u_n + 1$. Montrer que $u_n \leq n$ pour tout $n \in [\![0, N]\!]$.
Pour tout $n \in [\![0, N]\!]$, notons $P(n)$ l'assertion « $u_n \leq n$ ».
Initialisation. On a $u_0 = 0$, donc $u_0 \leq 0$ : $P(0)$ est vraie.
Hérédité. Soit $n \in [\![0, N - 1]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$.
Comme $n \leq N - 1$, le réel $u_{n+1}$ fait partie de la famille et l'hypothèse de l'énoncé s'applique au rang $n$ : $u_{n+1} \leq u_n + 1$.
Or $u_n \leq n$ d'après $P(n)$, donc $u_n + 1 \leq n + 1$.
Par transitivité, $u_{n+1} \leq n + 1$ : $P(n + 1)$ est vraie.
Conclusion. Par récurrence finie, $P(n)$ est vraie pour tout $n \in [\![0, N]\!]$, c'est-à-dire $u_n \leq n$ pour tout $n \in [\![0, N]\!]$.
À retenir : l'hérédité s'ouvre sur $[\![0, N - 1]\!]$, et c'est cette borne qu'on invoque pour appliquer l'hypothèse au rang $n$.

Ligne fautive : « Soit $n \in [\![0, N]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$. »
Pour $n = N$, il faudrait démontrer $P(N + 1)$, qui parle de $u_{N+1}$ : ce terme n'existe pas, et l'hypothèse $u_{n+1} \leq u_n + 1$ n'est donnée que pour $n \leq N - 1$. La preuve applique donc une hypothèse hors de son domaine et prétend établir une assertion dénuée de sens. Dans la rédaction modèle « une famille qui s'arrête au rang N », présentée plus loin, où $u_{n+1} = \sqrt{u_n^2 - 1}$ et $u_N = 0$, la même faute affirmerait que $u_{N+1} = \sqrt{-1}$ est défini.
Version correcte : « Soit $n \in [\![0, N - 1]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$. » Le rang $n + 1$ parcourt alors exactement $[\![1, N]\!]$.

Ligne fautive : « Par récurrence, $u_n \leq n$ pour tout $n \in \mathbb{N}$. »
L'initialisation au rang $0$ et l'hérédité démontrée pour $n \leq N - 1$ n'atteignent que $[\![0, N]\!]$. Au-delà, $u_n$ n'est même pas défini : la phrase n'a pas de sens, et la conclusion ne répond plus à la question posée.
Version correcte : « Par récurrence finie, $u_n \leq n$ pour tout $n \in [\![0, N]\!]$. »

Construire pas à pas une famille $(x_{n_0}, \dots, x_N)$, c'est donner $x_{n_0}$ puis, pour chaque $n \in [\![n_0, N - 1]\!]$, un procédé qui fournit $x_{n+1}$ à partir des termes déjà construits. Une étape n'est souvent possible que si le terme courant vérifie une condition (appartenir au domaine d'une fonction, être non nul) : on démontre par récurrence finie que cette condition est remplie à chaque rang de $[\![n_0, N - 1]\!]$. La construction peut devenir impossible après le rang $N$, ce qui interdit toute conclusion sur $\mathbb{N}$. Le cas d'une suite infinie relève de la fiche « Définir un objet par récurrence ».

Signal dans l'énoncé : une relation $u_{n+1} = f(u_n)$ ne s'applique que si $u_n$ appartient au domaine de $f$, et cette condition, remplie aux rangs $0, \dots, N - 1$, cesse de l'être au rang $N$.
1) Poser un prédicat qui contient l'existence du terme et de quoi assurer l'étape suivante : « Pour tout $n \in [\![0, N]\!]$, notons $P(n)$ l'assertion : $u_n$ est défini et $u_n = \dots$ »
2) Initialiser : « $u_0$ est donné et vaut …, donc $P(0)$ est vraie. »
3) Hérédité : « Soit $n \in [\![0, N - 1]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$. » Vérifier que $u_n$ appartient au domaine de $f$ en citant $P(n)$ et la borne $n \leq N - 1$, puis écrire « donc $u_{n+1} = f(u_n)$ est défini ».
4) Conclure : « Par récurrence finie, les termes $u_0, \dots, u_N$ sont définis et … pour tout $n \in [\![0, N]\!]$. »
5) Si la question le demande, calculer $u_N$ et montrer qu'il sort du domaine de $f$ : la construction s'arrête au rang $N$.

Soit $N \in \mathbb{N}^*$. On pose $u_0 = \sqrt{N}$ puis, pour tout $n \in \mathbb{N}$ tel que $u_n$ soit défini et $u_n^2 \geq 1$, $u_{n+1} = \sqrt{u_n^2 - 1}$. Montrer que $u_0, \dots, u_N$ sont définis, que $u_n = \sqrt{N - n}$ pour tout $n \in [\![0, N]\!]$, et que $u_{N+1}$ n'est pas défini.
Pour tout $n \in [\![0, N]\!]$, notons $P(n)$ l'assertion « $u_n$ est défini et $u_n = \sqrt{N - n}$ ».
Initialisation. Par définition, $u_0$ est défini et $u_0 = \sqrt{N} = \sqrt{N - 0}$, donc $P(0)$ est vraie.
Hérédité. Soit $n \in [\![0, N - 1]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$.
D'après $P(n)$, $u_n$ est défini et $u_n^2 = N - n$, donc $u_n^2 - 1 = N - (n + 1)$.
Or $n \leq N - 1$, donc $N - (n + 1) \geq 0$, c'est-à-dire $u_n^2 \geq 1$.
Ainsi $u_{n+1} = \sqrt{u_n^2 - 1}$ est défini et $u_{n+1} = \sqrt{N - (n + 1)}$ : $P(n + 1)$ est vraie.
Conclusion. Par récurrence finie, $P(n)$ est vraie pour tout $n \in [\![0, N]\!]$ : les réels $u_0, \dots, u_N$ sont définis et $u_n = \sqrt{N - n}$ pour tout $n \in [\![0, N]\!]$.
Rang $N + 1$. D'après $P(N)$, $u_N = \sqrt{0} = 0$, donc $u_N^2 = 0 < 1$ : la condition de construction n'est pas remplie au rang $N$, et $u_{N+1}$ n'est pas défini.
À retenir : dans une construction pas à pas, on cite la borne $n \leq N - 1$ au moment précis où elle rend l'étape suivante possible.

Signal dans l'énoncé : un algorithme contient une boucle « pour $k$ allant de $1$ à $N$ », et l'on demande ce que vaut une variable après chaque passage ou à la sortie. La notion d'invariant de boucle est présentée dans la fiche « Algorithmes élémentaires et preuve de programmes » ; on rédige ici sa preuve.
1) Nommer les valeurs, pas seulement la variable : « Notons $s_0$ la valeur de $s$ avant la boucle et, pour tout $k \in [\![1, N]\!]$, $s_k$ sa valeur à la fin du passage d'indice $k$. »
2) Traduire l'affectation en relation entre deux valeurs : « Le passage d'indice $k$ donne $s_k$ en fonction de $s_{k-1}$ et de $k$ » (par exemple $s_k = s_{k-1} + k$).
3) Poser $P(k)$ pour $k \in [\![0, N]\!]$ et l'initialiser avec la valeur d'entrée $s_0$.
4) Hérédité : « Soit $k \in [\![0, N - 1]\!]$ tel que $P(k)$ soit vraie. Comme $k + 1 \leq N$, le passage d'indice $k + 1$ a lieu et $s_{k+1} = \dots$ »
5) Conclure : « Par récurrence finie, $P(k)$ est vraie pour tout $k \in [\![0, N]\!]$. En particulier, à la sortie de la boucle, $s = s_N = \dots$ »

Soit $N \in \mathbb{N}^*$. On exécute l'algorithme « $s \leftarrow 0$ ; pour $k$ allant de $1$ à $N$ : $s \leftarrow s + k$ ». Démontrer que, pour tout $k \in [\![1, N]\!]$, on a $s = \frac{k(k + 1)}{2}$ à la fin du passage d'indice $k$.
Notons $s_0 = 0$ la valeur de la variable $s$ avant le premier passage et, pour tout $k \in [\![1, N]\!]$, $s_k$ sa valeur à la fin du passage d'indice $k$.
Pour tout $k \in [\![1, N]\!]$, le passage d'indice $k$ remplace la valeur $s_{k-1}$, présente au début de ce passage, par $s_{k-1} + k$ ; donc $s_k = s_{k-1} + k$.
Pour tout $k \in [\![0, N]\!]$, notons $P(k)$ l'assertion « $s_k = \frac{k(k + 1)}{2}$ ».
Initialisation. On a $s_0 = 0 = \frac{0 \times 1}{2}$, donc $P(0)$ est vraie.
Hérédité. Soit $k \in [\![0, N - 1]\!]$ tel que $P(k)$ soit vraie. Montrons $P(k + 1)$.
Comme $k + 1 \in [\![1, N]\!]$, le passage d'indice $k + 1$ a lieu, et $s_{k+1} = s_k + (k + 1)$.
Or $s_k = \frac{k(k + 1)}{2}$ d'après $P(k)$, donc $s_{k+1} = \frac{k(k + 1)}{2} + (k + 1) = (k + 1)\left(\frac{k}{2} + 1\right) = \frac{(k + 1)(k + 2)}{2}$.
Ainsi $P(k + 1)$ est vraie.
Conclusion. Par récurrence finie, $P(k)$ est vraie pour tout $k \in [\![0, N]\!]$. Pour tout $k \in [\![1, N]\!]$, à la fin du passage d'indice $k$, on a donc $s = s_k = \frac{k(k + 1)}{2}$ ; en particulier, l'algorithme se termine avec $s = \frac{N(N + 1)}{2}$.
À retenir : on raisonne sur les valeurs nommées $s_k$, jamais sur la variable $s$ elle-même, et la récurrence finie s'arrête au dernier passage.

Ligne fautive : « Au passage d'indice $k + 1$, $s = s + (k + 1) = \frac{k(k + 1)}{2} + (k + 1)$. »
Lue comme une égalité entre nombres, $s = s + (k + 1)$ imposerait $k + 1 = 0$ : la lettre $s$ y désigne deux nombres différents, la valeur avant et la valeur après l'affectation. On ne sait plus à quelle valeur s'applique $P(k)$, ni ce que la ligne démontre.
Version correcte : « Notons $s_k$ la valeur de $s$ à la fin du passage d'indice $k$. Le passage d'indice $k + 1$ donne $s_{k+1} = s_k + (k + 1)$. »

Soient $n_0 \leq N$ deux entiers et $P$ un prédicat indexé par $[\![n_0, N]\!]$. Si $P(N)$ est vraie et si, pour tout $n \in [\![n_0, N - 1]\!]$, $P(n + 1)$ entraîne $P(n)$, alors $P(n)$ est vraie pour tout $n \in [\![n_0, N]\!]$. On le déduit de la récurrence finie appliquée à l'assertion $Q(j)$ : « $P(N - j)$ est vraie », pour $j \in [\![0, N - n_0]\!]$. De même, si $P(N)$ est vraie et si $P(n)$ entraîne $P(n - 1)$ pour tout entier relatif $n \leq N$, alors $P(n)$ est vraie pour tout entier relatif $n \leq N$.

Signal dans l'énoncé : le terme connu est le dernier ($u_N$ donné), la relation exprime $u_n$ à partir de $u_{n+1}$, ou l'énoncé impose une récurrence descendante.
1) Poser le prédicat sur l'intervalle : « Pour tout $n \in [\![n_0, N]\!]$, notons $P(n)$ l'assertion : … »
2) Initialiser au rang $N$, et non au rang $n_0$ : « On a …, donc $P(N)$ est vraie. »
3) Ouvrir l'hérédité vers le bas : « Soit $n \in [\![n_0, N - 1]\!]$ tel que $P(n + 1)$ soit vraie. Montrons $P(n)$. » Forme équivalente : « Soit $n \in [\![n_0 + 1, N]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n - 1)$. » Dans les deux formes, les bornes garantissent que les deux rangs mis en jeu restent dans $[\![n_0, N]\!]$.
4) Utiliser $P(n + 1)$ et la relation écrite au rang $n$, puis finir par « donc $P(n)$ est vraie ».
5) Conclure : « Par récurrence descendante, $P(n)$ est vraie pour tout $n \in [\![n_0, N]\!]$. »

Soit $(u_n)$ définie pour $n \in [\![0, 10]\!]$ par $u_{10} = 1$ et $u_n = 2u_{n+1}$ pour tout $n \in [\![0, 9]\!]$. Montrer par récurrence descendante que $u_n = 2^{10-n}$ pour tout $n \in [\![0, 10]\!]$.
Pour tout $n \in [\![0, 10]\!]$, notons $P(n)$ l'assertion « $u_n = 2^{10-n}$ ».
Initialisation au rang $10$. On a $u_{10} = 1 = 2^0 = 2^{10-10}$, donc $P(10)$ est vraie.
Hérédité. Soit $n \in [\![0, 9]\!]$ tel que $P(n + 1)$ soit vraie. Montrons $P(n)$.
Comme $n \in [\![0, 9]\!]$, la relation de définition s'applique au rang $n$ : $u_n = 2u_{n+1}$.
Or $u_{n+1} = 2^{10-(n+1)} = 2^{9-n}$ d'après $P(n + 1)$.
Donc $u_n = 2 \times 2^{9-n} = 2^{10-n}$, et $P(n)$ est vraie.
Conclusion. Par récurrence descendante, $P(n)$ est vraie pour tout $n \in [\![0, 10]\!]$, c'est-à-dire $u_n = 2^{10-n}$ pour tout $n \in [\![0, 10]\!]$.
À retenir : on initialise au seul rang connu, le rang $10$, et l'hérédité suppose la propriété au rang $n + 1$ pour l'établir au rang $n$.

Ligne fautive : « Initialisation : $u_0 = 2^{10-0} = 1024$, donc $P(0)$ est vraie. »
Rien dans l'énoncé ne donne $u_0$ : cette ligne affirme la formule à démontrer au lieu de la vérifier. Le seul terme connu est $u_{10}$, et la relation $u_n = 2u_{n+1}$ transmet l'information du rang $10$ vers les rangs inférieurs.
Version correcte : « Initialisation : $u_{10} = 1 = 2^{10-10}$, donc $P(10)$ est vraie. »

Ligne fautive, après une initialisation correcte au rang $10$ : « Soit $n \in [\![0, 9]\!]$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$. »
Le calcul qui suit peut être juste ($u_{n+1} = \frac{u_n}{2} = 2^{9-n}$), mais cette hérédité ne part que des rangs $n \leq 9$, où rien n'est établi : lancée du rang $10$, elle n'atteint aucun autre rang. On a montré que la formule se transmet vers le haut, alors que l'information connue est en haut et doit descendre.
Version correcte : « Soit $n \in [\![0, 9]\!]$ tel que $P(n + 1)$ soit vraie. Montrons $P(n)$. »

Soient $a$ un entier et $P$ un prédicat indexé par les entiers $n \geq a$. Si $P(a)$ est vraie et si, pour tout $n \geq a$, $P(n)$ entraîne $P(n + 2)$, alors $P(a + 2k)$ est vraie pour tout $k \in \mathbb{N}$ : l'ensemble atteint est formé des entiers $n \geq a$ de même parité que $a$. Pour atteindre tous les entiers $n \geq a$, il suffit de démontrer en outre $P(a + 1)$, qui lance la seconde chaîne. Ce n'est pas une récurrence double (fiche « Récurrence double ») : ici, $P(n + 2)$ se déduit de $P(n)$ seule.

Signal dans l'énoncé : la relation lie le rang $n + 2$ au seul rang $n$ (par exemple $u_{n+2} = u_n + 2$), ou la formule demandée change avec la parité ($u_{2k}$ d'un côté, $u_{2k+1}$ de l'autre).
1) Écrire deux prédicats indexés par $k \in \mathbb{N}$ : « $P(k)$ : $u_{2k} = \dots$ » et « $Q(k)$ : $u_{2k+1} = \dots$ ».
2) Rangs pairs : initialiser $P(0)$ avec $u_0$ ; hérédité « Soit $k \in \mathbb{N}$ tel que $P(k)$ soit vraie. Montrons $P(k + 1)$. », en appliquant la relation au rang $n = 2k$ ; conclure « par récurrence, $P(k)$ est vraie pour tout $k \in \mathbb{N}$ ».
3) Rangs impairs : même rédaction pour $Q$, initialisée avec $u_1$, en appliquant la relation au rang $n = 2k + 1$.
4) Si la question porte sur tous les rangs, conclure par disjonction de cas : « Soit $n \in \mathbb{N}$. Si $n = 2k$ avec $k \in \mathbb{N}$, $P(k)$ donne … ; si $n = 2k + 1$ avec $k \in \mathbb{N}$, $Q(k)$ donne … »

Soit $(u_n)_{n \in \mathbb{N}}$ définie par $u_0 = 1$, $u_1 = 2$ et $u_{n+2} = u_n + 2$ pour tout $n \in \mathbb{N}$. Montrer que pour tout $k \in \mathbb{N}$, $u_{2k} = 2k + 1$ et $u_{2k+1} = 2k + 2$.
Rangs pairs. Pour tout $k \in \mathbb{N}$, notons $P(k)$ l'assertion « $u_{2k} = 2k + 1$ ».
Initialisation. On a $u_0 = 1 = 2 \times 0 + 1$, donc $P(0)$ est vraie.
Hérédité. Soit $k \in \mathbb{N}$ tel que $P(k)$ soit vraie. Montrons $P(k + 1)$, c'est-à-dire $u_{2k+2} = 2k + 3$.
La relation de récurrence appliquée au rang $n = 2k$ donne $u_{2k+2} = u_{2k} + 2$.
Or $u_{2k} = 2k + 1$ d'après $P(k)$, donc $u_{2k+2} = 2k + 3 = 2(k + 1) + 1$ : $P(k + 1)$ est vraie.
Par récurrence, $P(k)$ est vraie pour tout $k \in \mathbb{N}$.
Rangs impairs. Pour tout $k \in \mathbb{N}$, notons $Q(k)$ l'assertion « $u_{2k+1} = 2k + 2$ ».
Initialisation. On a $u_1 = 2 = 2 \times 0 + 2$, donc $Q(0)$ est vraie.
Hérédité. Soit $k \in \mathbb{N}$ tel que $Q(k)$ soit vraie. Montrons $Q(k + 1)$, c'est-à-dire $u_{2k+3} = 2k + 4$.
La relation de récurrence appliquée au rang $n = 2k + 1$ donne $u_{2k+3} = u_{2k+1} + 2$.
Or $u_{2k+1} = 2k + 2$ d'après $Q(k)$, donc $u_{2k+3} = 2k + 4 = 2(k + 1) + 2$ : $Q(k + 1)$ est vraie.
Par récurrence, $Q(k)$ est vraie pour tout $k \in \mathbb{N}$.
Conclusion. Pour tout $k \in \mathbb{N}$, $u_{2k} = 2k + 1$ et $u_{2k+1} = 2k + 2$.
Prolongement. Soit $n \in \mathbb{N}$. Si $n = 2k$ avec $k \in \mathbb{N}$, alors $u_n = 2k + 1 = n + 1$ ; si $n = 2k + 1$ avec $k \in \mathbb{N}$, alors $u_n = 2k + 2 = n + 1$. Les deux récurrences couvrent donc tous les rangs : $u_n = n + 1$ pour tout $n \in \mathbb{N}$.
À retenir : un pas de 2 réclame une initialisation par parité, car la relation $u_{n+2} = u_n + 2$ ne relie jamais un rang pair à un rang impair ; deux récurrences sur $k$ rendent chaque initialisation visible.

Ligne fautive : « $P(0)$ est vraie et, pour tout $n \in \mathbb{N}$, $P(n)$ entraîne $P(n + 2)$ ; donc $P(n)$ est vraie pour tout $n \in \mathbb{N}$. »
Depuis le rang $0$, un pas de $2$ n'atteint que les entiers pairs : les rangs impairs ne sont pas démontrés, et ils peuvent être faux. Avec $u_0 = 1$, $u_1 = 5$ et $u_{n+2} = u_n + 2$, l'assertion $P(n)$ : « $u_n = n + 1$ » est vraie au rang $0$ et passe de chaque rang $n$ au rang $n + 2$, mais $u_1 = 5 \neq 2$.
Version correcte : « $P(0)$ et $P(1)$ sont vraies et, pour tout $n \in \mathbb{N}$, $P(n)$ entraîne $P(n + 2)$ ; donc $P(n)$ est vraie pour tout $n \in \mathbb{N}$. » On peut aussi rédiger deux récurrences sur $k$, l'une pour $u_{2k}$, l'autre pour $u_{2k+1}$.

Soit $P$ un prédicat indexé par $\mathbb{Z}$. Si $P(0)$ est vraie, si $P(n)$ entraîne $P(n + 1)$ pour tout $n \geq 0$ et si $P(n)$ entraîne $P(n - 1)$ pour tout $n \leq 0$, alors $P(n)$ est vraie pour tout $n \in \mathbb{Z}$. La montée atteint $\mathbb{N}$, la descente atteint les entiers négatifs, et tout entier relatif est positif ou négatif. Une hérédité dans un seul sens, lancée d'un seul rang, ne recouvre jamais $\mathbb{Z}$.

Signal dans l'énoncé : la conclusion porte sur tout $n \in \mathbb{Z}$ et l'hypothèse relie deux entiers consécutifs, par exemple $f(x + 1) = f(x) + 1$ pour tout réel $x$.
1) Montée sur $\mathbb{N}$ : « Pour tout $n \in \mathbb{N}$, notons $P(n)$ l'assertion : … » Initialiser au rang $0$ ; hérédité « Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n + 1)$. »
2) Descente sur les entiers négatifs, réécrite comme une montée : « Pour tout $m \in \mathbb{N}$, notons $Q(m)$ l'assertion $P(-m)$. » Initialiser $Q(0)$, qui est $P(0)$ ; hérédité « Soit $m \in \mathbb{N}$ tel que $Q(m)$ soit vraie. Montrons $Q(m + 1)$. », en appliquant l'hypothèse au rang inférieur $-m - 1$ puis en isolant le terme cherché.
3) Recoller par disjonction de cas : « Soit $n \in \mathbb{Z}$. Si $n \geq 0$, $P(n)$ découle de la première récurrence. Si $n < 0$, alors $m = -n$ appartient à $\mathbb{N}$ et $Q(m)$ donne $P(n)$. »
Variante admise pour 2) : « Soit $n \in \mathbb{Z}$ tel que $n \leq 0$ et $P(n)$ soit vraie. Montrons $P(n - 1)$. », conclue par « par récurrence descendante, $P(n)$ est vraie pour tout entier $n \leq 0$ ».