Définir un objet par récurrence

Définir une suite par récurrence, c'est donner un terme initial et une relation de récurrence qui calcule chaque terme à partir du précédent : $u_0 = a$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = f(u_n)$, où $f$ est une fonction donnée. On obtient $u_1 = f(u_0)$, puis $u_2 = f(u_1)$, et de proche en proche chaque terme, sans qu'aucun soit exprimé directement en fonction de $n$. La relation peut faire intervenir le rang, sous la forme $u_{n+1} = g(n, u_n)$, comme $u_{n+1} = (n+1)\,u_n$. La suite peut aussi commencer à un rang $n_0$ : on donne alors $u_{n_0}$ et la relation pour tout $n \ge n_0$.

Définir par récurrence, c'est construire un objet : on écrit « On définit la suite $(u_n)$ par $u_0 = 0$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = 2u_n + 1$ », sans initialisation ni hérédité. Démontrer par récurrence, c'est établir pour tout $n$ une proposition $P(n)$ portant sur un objet déjà défini : on écrit « Montrons par récurrence que, pour tout $n \in \mathbb{N}$, … ». Les deux gestes se répondent : l'initialisation invoque le terme initial, l'hérédité invoque la relation de définition. Ils se mêlent quand la relation n'est pas définie partout, car l'existence de chaque terme devient à son tour une proposition à démontrer par récurrence.

L'article défini de « Soit $(u_n)$ la suite définie par … » affirme qu'une telle suite existe et qu'elle est unique : on ne l'écrit que si les conditions le garantissent. « La suite est bien définie » signifie que chacun de ses termes existe. « Par définition de la suite » justifie l'égalité $u_{n+1} = f(u_n)$ dans un calcul ; « par hypothèse de récurrence » justifie l'usage de $P(n)$, et de lui seul. « On conjecture que » annonce une formule qui n'est pas encore démontrée et qu'aucune ligne ne peut encore utiliser.

Lorsque $f$ n'est définie que sur une partie $D$ de $\mathbb{R}$, le terme $u_{n+1} = f(u_n)$ n'existe que si $u_n \in D$, et la construction s'arrête au premier terme qui sort de $D$. On dit que les conditions $u_0 = a$ et $u_{n+1} = f(u_n)$ définissent une suite, ou que la suite est bien définie, lorsque pour tout $n \in \mathbb{N}$ le terme $u_n$ existe et appartient à $D$. Ce n'est pas automatique : avec $u_0 = 2$ et $u_{n+1} = \frac{1}{u_n - 1}$, on trouve $u_1 = 1$, et $u_2$ n'existe pas. L'existence de tous les termes est donc une propriété à démontrer, en général par récurrence.

Soient $f : D \to \mathbb{R}$ et $I$ une partie de $D$ stable par $f$, c'est-à-dire telle que $f(x) \in I$ pour tout $x \in I$. Si $a \in I$, les conditions $u_0 = a$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = f(u_n)$ définissent une unique suite, dont tous les termes appartiennent à $I$. Exhiber une telle partie, le plus souvent un intervalle repéré en calculant quelques termes et en étudiant $f$, est le moyen usuel de prouver qu'une suite récurrente est bien définie. Le domaine lui-même ne convient pas toujours : pour $f(x) = \ln(1 + x)$, l'intervalle $]-1, +\infty[$ n'est pas stable, alors que $]0, +\infty[$ l'est.

Quand l'utiliser : l'énoncé demande de montrer que la suite est bien définie, ou la relation $u_{n+1} = f(u_n)$ contient un quotient, une racine carrée ou un logarithme. Ce travail précède tout calcul portant sur $u_{n+1}$.
1) Déterminer le domaine $D$ de $f$, c'est-à-dire les valeurs de $u_n$ pour lesquelles $f(u_n)$ a un sens.
2) Au brouillon, calculer quelques termes et étudier $f$ pour trouver une partie $I \subset D$ qui contient $u_0$ et qui est stable par $f$. Le domaine lui-même n'est pas toujours stable : il faut souvent une partie plus petite.
3) Poser la propriété : « Pour $n \in \mathbb{N}$, notons $P(n)$ : $u_n$ est bien défini et $u_n \in I$. »
4) Initialisation : « $u_0 = a$ est donné et $a \in I$, donc $P(0)$ est vraie. »
5) Hérédité : « Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Comme $u_n \in I$ et $I \subset D$, le terme $u_{n+1} = f(u_n)$ est bien défini. » Montrer ensuite, par un calcul sur $u_n$ (signe, inégalités), que $u_{n+1} \in I$, puis écrire « donc $P(n+1)$ est vraie ».
6) Conclusion : « Par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$ : la suite $(u_n)$ est bien définie et tous ses termes appartiennent à $I$. »
Si le calcul des premiers termes en fait sortir un de $D$, la conclusion s'inverse : les conditions ne définissent aucune suite, ce que l'on établit par l'absurde en désignant le premier terme qui n'existe pas.

On considère les conditions $u_0 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \ln(1 + u_n)$. Montrer qu'elles définissent une suite $(u_n)$ dont tous les termes sont strictement positifs.
La fonction $x \mapsto \ln(1 + x)$ est définie sur $]-1, +\infty[$.
Pour $n \in \mathbb{N}$, notons $P(n)$ : « $u_n$ est bien défini et $u_n > 0$ ». Montrons par récurrence que $P(n)$ est vraie pour tout $n \in \mathbb{N}$.
Initialisation : $u_0 = 1$ est donné et $1 > 0$, donc $P(0)$ est vraie.
Hérédité : soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Par hypothèse de récurrence, $u_n$ est bien défini et $u_n > 0$.
En particulier $u_n > -1$, donc $u_{n+1} = \ln(1 + u_n)$ est bien défini.
De plus $1 + u_n > 1$, et la fonction $\ln$ est strictement croissante sur $]0, +\infty[$, donc $\ln(1 + u_n) > \ln 1 = 0$, c'est-à-dire $u_{n+1} > 0$.
Ainsi $P(n+1)$ est vraie.
Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$. Les conditions définissent donc une suite $(u_n)$, et tous ses termes sont strictement positifs.
À retenir : l'existence de $u_{n+1}$ se justifie par une information sur $u_n$, que l'on inscrit dans la propriété de récurrence pour qu'elle se transmette d'un rang au suivant.

Montrer que les conditions $u_0 = 2$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \frac{1}{u_n - 1}$ ne définissent pas de suite réelle.
Supposons par l'absurde qu'il existe une suite réelle $(u_n)$ telle que $u_0 = 2$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \frac{1}{u_n - 1}$.
Pour tout $n \in \mathbb{N}$, l'égalité $u_{n+1} = \frac{1}{u_n - 1}$ entre réels impose que ce quotient existe, donc que $u_n \neq 1$.
Pour $n = 0$ : $u_0 - 1 = 1$, donc $u_1 = \frac{1}{1} = 1$.
Pour $n = 1$ : on doit avoir $u_1 \neq 1$, ce qui contredit $u_1 = 1$.
L'hypothèse est absurde : aucune suite réelle ne vérifie ces conditions, qui ne définissent donc pas de suite.
À retenir : pour établir que des conditions ne définissent pas de suite, on calcule les termes jusqu'au premier qui sort du domaine de la relation, puis l'on conclut par l'absurde.

Ligne fautive, pour $u_0 = 5$ et $u_{n+1} = \sqrt{u_n - 2}$ : « Hérédité : soit $n \in \mathbb{N}$ tel que $u_n$ existe. Alors $u_{n+1} = \sqrt{u_n - 2}$ existe. »
L'existence de $u_n$ ne dit pas que $u_n - 2 \ge 0$. Ici $u_1 = \sqrt{3}$, donc $u_1 - 2 < 0$ et $u_2$ n'existe pas : la prétendue récurrence « démontre » une fausseté, parce que sa propriété ne contenait pas l'appartenance au domaine.
Version correcte : on inscrit cette appartenance dans la propriété, « $u_n$ est bien défini et $u_n \ge 2$ », et l'on n'écrit $u_{n+1}$ qu'après l'avoir établie au rang $n$. Ici elle échoue dès le rang $1$, et l'on conclut : « $u_1 = \sqrt{3} < 2$, donc $u_2$ n'existe pas : ces conditions ne définissent pas de suite. »

Quand l'utiliser : l'énoncé demande de montrer que, pour tout $n$, $m \le u_n \le M$, ou l'on a besoin d'une borne de la suite pour justifier son existence, sa monotonie ou sa convergence.
1) Poser : « Pour $n \in \mathbb{N}$, notons $P(n)$ : $u_n$ est bien défini et $m \le u_n \le M$. » L'existence se retire de $P(n)$ si $f$ est définie partout.
2) Initialisation : calculer $u_0$ et vérifier les deux inégalités.
3) Hérédité : « Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Par hypothèse de récurrence, $m \le u_n \le M$. » Justifier d'abord que $u_{n+1}$ existe.
4) Faire traverser à l'encadrement chaque opération de la relation, une ligne par opération : ajouter un même nombre conserve le sens des inégalités ; multiplier par un nombre positif le conserve, par un nombre négatif le renverse ; appliquer une fonction croissante sur un intervalle contenant les trois membres le conserve, une fonction décroissante le renverse. Chaque ligne cite la règle qu'elle emploie.
5) Raccorder : les bornes obtenues pour $u_{n+1}$ ne sont pas forcément $m$ et $M$ ; on vérifie qu'elles sont comprises entre $m$ et $M$, puis on écrit « donc $m \le u_{n+1} \le M$ : $P(n+1)$ est vraie ».
6) Conclusion : « Par récurrence, pour tout $n \in \mathbb{N}$, $m \le u_n \le M$. »
Raccourci : si $f$ est croissante sur $[m, M]$, avec $m \le f(m)$ et $f(M) \le M$, l'hérédité tient en une ligne justifiée par cette croissance : $m \le f(m) \le f(u_n) \le f(M) \le M$.

On considère les conditions $u_0 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \sqrt{u_n + 2}$. Montrer qu'elles définissent une suite $(u_n)$ et que, pour tout $n \in \mathbb{N}$, $1 \le u_n \le 2$.
Pour tout $n \in \mathbb{N}$, le terme $u_{n+1} = \sqrt{u_n + 2}$ existe si et seulement si $u_n$ existe et vérifie $u_n + 2 \ge 0$.
Pour $n \in \mathbb{N}$, notons $P(n)$ : « $u_n$ est bien défini et $1 \le u_n \le 2$ ». Montrons par récurrence que $P(n)$ est vraie pour tout $n \in \mathbb{N}$.
Initialisation : $u_0 = 1$ et $1 \le 1 \le 2$, donc $P(0)$ est vraie.
Hérédité : soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Par hypothèse de récurrence, $u_n$ est bien défini et $1 \le u_n \le 2$.
En ajoutant $2$ à chaque membre, $3 \le u_n + 2 \le 4$. En particulier $u_n + 2 \ge 0$, donc $u_{n+1} = \sqrt{u_n + 2}$ est bien défini.
Les trois membres de cet encadrement sont positifs et la fonction racine carrée est croissante sur $[0, +\infty[$, donc $\sqrt{3} \le \sqrt{u_n + 2} \le \sqrt{4}$, c'est-à-dire $\sqrt{3} \le u_{n+1} \le 2$.
Or $1 \le 3$, donc, par croissance de la racine carrée, $1 \le \sqrt{3}$. Il vient $1 \le u_{n+1} \le 2$, et $P(n+1)$ est vraie.
Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$. Les conditions définissent donc une suite $(u_n)$ et, pour tout $n \in \mathbb{N}$, $1 \le u_n \le 2$.
À retenir : dans l'hérédité, on fait traverser à l'encadrement chaque opération de la relation en justifiant le sens des inégalités, puis on raccorde les bornes obtenues aux bornes annoncées.

Ligne fautive, pour $u_{n+1} = 1 + \frac{1}{u_n}$ : « Comme $1 \le u_n \le 2$, on a $1 + \frac{1}{1} \le 1 + \frac{1}{u_n} \le 1 + \frac{1}{2}$, donc $2 \le u_{n+1} \le \frac{3}{2}$. »
La fonction inverse est décroissante sur $]0, +\infty[$ : elle renverse les inégalités. L'encadrement écrit est d'ailleurs impossible, puisque $2 > \frac{3}{2}$.
Version correcte : « Comme $1 \le u_n \le 2$ et que ces nombres sont strictement positifs, la décroissance de la fonction inverse sur $]0, +\infty[$ donne $\frac{1}{2} \le \frac{1}{u_n} \le 1$, donc $\frac{3}{2} \le u_{n+1} \le 2$, et en particulier $1 \le u_{n+1} \le 2$. »

Une formule explicite donne chaque terme directement en fonction de $n$, comme $u_n = \frac{1}{n+1}$. Une définition récursive ne donne que le premier terme et le passage d'un terme au suivant, comme $u_0 = 1$ et $u_{n+1} = \frac{u_n}{1 + u_n}$, qui définit la même suite. Passer de la formule explicite à la relation est un calcul : on exprime $u_{n+1}$ à l'aide de $u_n$. Passer de la définition récursive à une formule explicite demande une preuve : on conjecture la formule, puis on la démontre par récurrence ou par unicité. Beaucoup de suites récurrentes s'étudient d'ailleurs sans formule explicite, directement sur la relation.

Quand l'utiliser : l'énoncé demande d'exprimer $u_n$ en fonction de $n$, ou les premiers termes d'une suite récurrente présentent une régularité visible.
1) Au brouillon, calculer $u_1$, $u_2$, $u_3$, davantage si besoin, et les écrire sous une forme qui laisse voir la régularité.
2) Sur la copie, annoncer la conjecture comme telle : « Le calcul des premiers termes conduit à conjecturer que, pour tout $n \in \mathbb{N}$, $u_n = \varphi(n)$. Montrons-le par récurrence. »
3) Poser : « Pour $n \in \mathbb{N}$, notons $P(n)$ : $u_n = \varphi(n)$ », en y ajoutant l'existence de $u_n$ si la relation n'est pas définie partout.
4) Initialisation : calculer séparément $u_0$, qui est donné, et $\varphi(0)$, puis constater l'égalité.
5) Hérédité : « Soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. » Partir de $u_{n+1}$, écrire $u_{n+1} = f(u_n)$ par définition de la suite, remplacer $u_n$ par $\varphi(n)$ par hypothèse de récurrence, puis calculer jusqu'à obtenir $\varphi(n+1)$.
6) Conclusion : « Par récurrence, pour tout $n \in \mathbb{N}$, $u_n = \varphi(n)$. » La formule ne sert qu'à partir de cette ligne.
Si l'hérédité n'aboutit pas, la conjecture est peut-être fausse : on revient au calcul des premiers termes.

On considère les conditions $u_0 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \frac{u_n}{1 + u_n}$. Montrer qu'elles définissent une suite $(u_n)$ et exprimer $u_n$ en fonction de $n$.
On a $u_1 = \frac{1}{1 + 1} = \frac{1}{2}$, puis $u_2 = \frac{1/2}{1 + 1/2} = \frac{1}{3}$ et $u_3 = \frac{1/3}{1 + 1/3} = \frac{1}{4}$.
Ces valeurs conduisent à conjecturer que, pour tout $n \in \mathbb{N}$, $u_n = \frac{1}{n+1}$. Montrons-le par récurrence, en même temps que l'existence des termes.
Pour $n \in \mathbb{N}$, notons $P(n)$ : « $u_n$ est bien défini et $u_n = \frac{1}{n+1}$ ».
Initialisation : $u_0 = 1$ et $\frac{1}{0 + 1} = 1$, donc $P(0)$ est vraie.
Hérédité : soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Par hypothèse de récurrence, $u_n$ est bien défini et $u_n = \frac{1}{n+1}$.
En particulier $u_n > 0$, donc $1 + u_n > 0$ et $u_{n+1} = \frac{u_n}{1 + u_n}$ est bien défini.
Par définition de la suite, puis par hypothèse de récurrence, $u_{n+1} = \frac{u_n}{1 + u_n} = \frac{\frac{1}{n+1}}{1 + \frac{1}{n+1}}$.
En multipliant le numérateur et le dénominateur par $n + 1$, qui est non nul, $u_{n+1} = \frac{1}{(n+1) + 1} = \frac{1}{n+2}$.
Ainsi $P(n+1)$ est vraie.
Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$. Les conditions définissent donc une suite $(u_n)$ et, pour tout $n \in \mathbb{N}$, $u_n = \frac{1}{n+1}$.
À retenir : la formule est annoncée comme une conjecture, puis une seule récurrence établit l'existence et la valeur de chaque terme, en partant de la relation de définition et en appliquant l'hypothèse de récurrence.

Ligne fautive : « On a $u_1 = \frac{1}{2}$, $u_2 = \frac{1}{3}$ et $u_3 = \frac{1}{4}$, donc $u_n = \frac{1}{n+1}$ et la suite converge vers $0$. »
Quelques valeurs suggèrent une formule, elles ne la démontrent pas. Pour $u_0 = 1$ et $u_{n+1} = u_n + n + 1$, les termes $1$, $2$, $4$ suggèrent $u_n = 2^n$, alors que $u_3 = 7$.
Version correcte : « Les premiers termes conduisent à conjecturer que, pour tout $n \in \mathbb{N}$, $u_n = \frac{1}{n+1}$. Montrons-le par récurrence. » La formule, puis la limite, ne s'écrivent qu'après la conclusion de cette récurrence.

Ligne fautive, pour $u_0 = 1$ et $u_{n+1} = \sqrt{u_n + 2}$ : « $u_0 = 1$, $u_1 = \sqrt{3}$ et $u_2 = \sqrt{2 + \sqrt{3}}$ vérifient $u_0 \le u_1 \le u_2$, donc la suite est croissante. »
Une vérification sur un nombre fini de rangs, même grand, ne dit rien des rangs suivants. La suite définie par $u_0 = 41$ et $u_{n+1} = u_n + 2n$ vérifie $u_n = n^2 - n + 41$ : ses termes sont des nombres premiers pour tous les $n$ de $0$ à $40$, mais $u_{41} = 41^2$.
Version correcte : poser $P(n)$ : « $u_n \le u_{n+1}$ », vérifier $P(0)$, qui s'écrit $1 \le \sqrt{3}$, puis rédiger l'hérédité : « Soit $n \in \mathbb{N}$ tel que $u_n \le u_{n+1}$. Alors $u_n + 2 \le u_{n+1} + 2$ ; ces deux nombres sont positifs, puisque tous les termes sont supérieurs à $1$ d'après l'encadrement déjà établi, et la racine carrée est croissante sur $[0, +\infty[$, donc $\sqrt{u_n + 2} \le \sqrt{u_{n+1} + 2}$, c'est-à-dire $u_{n+1} \le u_{n+2}$. » On conclut ensuite par récurrence.

Théorème. Soient $E$ un ensemble, $a \in E$ et $f : E \to E$ une application. Il existe une unique suite $(u_n)_{n \in \mathbb{N}}$ d'éléments de $E$ telle que $u_0 = a$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = f(u_n)$. L'unicité se démontre par une récurrence immédiate. Pour l'existence, on montre par récurrence sur $N$ qu'il existe une unique famille $(x_0, \dots, x_N)$ d'éléments de $E$ telle que $x_0 = a$ et $x_{k+1} = f(x_k)$ pour tout $k < N$ ; par unicité, la famille de rang $N + 1$ prolonge celle de rang $N$, et l'on définit $u_n$ comme le terme d'indice $n$ de la famille de rang $n$. Le théorème s'étend aux relations $u_{n+1} = g(n, u_n)$, aux relations d'ordre $p$ munies de $p$ termes initiaux et à celles qui portent sur tous les termes précédents, pourvu que la relation soit définie sur tout $E$ et à valeurs dans $E$ : c'est exactement ce que fournit une partie stable.

Soient $E$ un ensemble, $a \in E$ et $f : E \to E$. Montrer que deux suites $(u_n)$ et $(v_n)$ d'éléments de $E$ qui vérifient $u_0 = v_0 = a$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = f(u_n)$ et $v_{n+1} = f(v_n)$ sont égales.
Soient $(u_n)$ et $(v_n)$ deux suites d'éléments de $E$ vérifiant ces conditions.
Pour $n \in \mathbb{N}$, notons $P(n)$ : « $u_n = v_n$ ». Montrons par récurrence que $P(n)$ est vraie pour tout $n \in \mathbb{N}$.
Initialisation : $u_0 = a$ et $v_0 = a$, donc $u_0 = v_0$ : $P(0)$ est vraie.
Hérédité : soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$.
Par définition des deux suites, $u_{n+1} = f(u_n)$ et $v_{n+1} = f(v_n)$.
Par hypothèse de récurrence, $u_n = v_n$ ; comme $f$ associe à chaque élément de $E$ une unique image, $f(u_n) = f(v_n)$.
Ainsi $u_{n+1} = v_{n+1}$ : $P(n+1)$ est vraie.
Conclusion : par récurrence, $u_n = v_n$ pour tout $n \in \mathbb{N}$, donc les suites $(u_n)$ et $(v_n)$ sont égales. Il existe au plus une suite vérifiant ces conditions.
À retenir : pour prouver une unicité, on se donne deux objets qui vérifient les mêmes conditions et l'on montre par récurrence qu'ils coïncident rang par rang.

Quand l'utiliser : on dispose, pour une suite définie par $u_0 = a$ et $u_{n+1} = f(u_n)$, d'une formule candidate $\varphi(n)$ donnée par l'énoncé ou conjecturée, et la relation se vérifie sur cette formule par un calcul direct.
1) Introduire la candidate : « Pour $n \in \mathbb{N}$, posons $v_n = \varphi(n)$. »
2) Vérifier la condition initiale : « $v_0 = \varphi(0) = a$. »
3) Vérifier la relation à un rang quelconque : « Soit $n \in \mathbb{N}$. On a $f(v_n) = \dots = v_{n+1}$. » Aucune hypothèse de récurrence n'intervient : l'égalité s'obtient pour tout $n$ par le seul calcul.
4) Conclure : « Les suites $(u_n)$ et $(v_n)$ ont le même premier terme et vérifient la même relation de récurrence ; par unicité d'une telle suite, $u_n = v_n$ pour tout $n \in \mathbb{N}$. »
Pour une relation d'ordre $p$, on vérifie les $p$ conditions initiales. La méthode repose sur le théorème d'existence et d'unicité, dont l'unicité se démontre elle-même par récurrence : elle ne supprime pas la récurrence, elle la fait une fois pour toutes.

Soit $(u_n)$ la suite définie par $u_0 = 0$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = 2u_n + 1$. En utilisant l'unicité d'une suite définie par récurrence, montrer que $u_n = 2^n - 1$ pour tout $n \in \mathbb{N}$.
La fonction $x \mapsto 2x + 1$ est définie sur $\mathbb{R}$ et à valeurs réelles : il existe une unique suite réelle de premier terme $0$ qui vérifie cette relation, et c'est $(u_n)$.
Pour $n \in \mathbb{N}$, posons $v_n = 2^n - 1$.
Condition initiale : $v_0 = 2^0 - 1 = 1 - 1 = 0$.
Relation de récurrence : soit $n \in \mathbb{N}$. On a $2v_n + 1 = 2(2^n - 1) + 1 = 2^{n+1} - 2 + 1 = 2^{n+1} - 1 = v_{n+1}$.
L'entier $n$ étant quelconque, $v_{n+1} = 2v_n + 1$ pour tout $n \in \mathbb{N}$.
Les suites $(u_n)$ et $(v_n)$ ont donc le même premier terme $0$ et vérifient la même relation de récurrence.
Par unicité d'une telle suite, $(v_n) = (u_n)$, c'est-à-dire $u_n = 2^n - 1$ pour tout $n \in \mathbb{N}$.
À retenir : une formule qui vérifie la condition initiale et la relation de récurrence, chacune par un calcul direct, est par unicité celle de la suite, sans qu'aucune hypothèse de récurrence intervienne.

Ligne fautive, pour $u_0 = 0$ et $u_{n+1} = 2u_n + 1$ : « La suite $w_n = 2^{n+1} - 1$ vérifie $w_{n+1} = 2w_n + 1$ pour tout $n$, donc $u_n = 2^{n+1} - 1$. »
La relation seule admet une solution pour chaque valeur du premier terme ; l'unicité ne vaut qu'une fois ce premier terme fixé. Ici $w_0 = 1$ alors que $u_0 = 0$, et en effet $u_1 = 1$ tandis que $w_1 = 3$.
Version correcte : « La suite $v_n = 2^n - 1$ vérifie $v_0 = 0 = u_0$ et, pour tout $n \in \mathbb{N}$, $v_{n+1} = 2v_n + 1$ ; par unicité, $u_n = v_n$ pour tout $n \in \mathbb{N}$. »

Une relation de récurrence peut faire intervenir plusieurs termes précédents. Une suite récurrente d'ordre 2 est définie par $u_0 = a$, $u_1 = b$ et, pour tout $n \in \mathbb{N}$, $u_{n+2} = g(u_n, u_{n+1})$ : il faut deux termes initiaux, car le premier terme que la relation calcule est $u_2$. Plus généralement, une relation qui fait intervenir les $p$ termes précédents demande $p$ termes initiaux. Une relation qui utilise tous les termes précédents, comme $u_{n+1} = u_0 + u_1 + \dots + u_n$, ne demande que $u_0$. Les propriétés de ces suites se démontrent souvent par récurrence double ou par récurrence forte (fiches correspondantes).

Ligne fautive : « Soit $(u_n)$ la suite définie par $u_0 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+2} = u_{n+1} + u_n$. »
Rien ne fixe $u_1$ : pour chaque réel $b$, la suite de premiers termes $1$ et $b$ vérifie ces conditions. Il en existe donc une infinité, et l'article défini de « la suite » affirme une unicité fausse.
Version correcte : « Soit $(u_n)$ la suite définie par $u_0 = 1$, $u_1 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+2} = u_{n+1} + u_n$. » Avant d'écrire une définition, on compte les termes précédents qu'appelle la relation : il faut autant de termes initiaux.

Ligne fautive : « $u_0 = 0$, $u_1 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = u_n + u_{n-1}$. »
Pour $n = 0$, la relation fait intervenir $u_{-1}$, qui n'existe pas : la phrase écrite n'a pas de sens à ce rang.
Version correcte : « pour tout entier $n \ge 1$, $u_{n+1} = u_n + u_{n-1}$ », ou, en décalant les indices, « pour tout $n \in \mathbb{N}$, $u_{n+2} = u_{n+1} + u_n$ ». On choisit le premier rang de la relation pour que le plus petit indice qu'elle appelle soit celui d'un terme initial.

Pour un réel ou un complexe $a$, on définit $a^n$ pour tout $n \in \mathbb{N}$ par $a^0 = 1$ et, pour tout $n \in \mathbb{N}$, $a^{n+1} = a \cdot a^n$. On en tire $a^1 = a \cdot 1 = a$, $a^2 = a \cdot a$, et $0^0 = 1$. Si $a \neq 0$, on pose ensuite $a^{-n} = \frac{1}{a^n}$ pour $n \in \mathbb{N}^*$. La même définition vaut pour tout produit associatif muni d'un élément neutre : $A^0 = I_p$ et $A^{n+1} = A A^n$ pour une matrice carrée $A$ de taille $p$, $f^0 = \mathrm{id}_E$ et $f^{n+1} = f \circ f^n$ pour une application $f : E \to E$.

Les écritures à points de suspension, comme $n! = 1 \times 2 \times \dots \times n$ ou $a_0 + a_1 + \dots + a_n$, sont des abréviations : leur définition exacte est récursive, et c'est elle que l'on invoque dans une preuve. Chaque objet est donné par sa valeur au premier rang et par le passage d'un rang au suivant. Les règles de calcul qui les concernent se démontrent par récurrence à partir de ces deux lignes.

Pour tous réels $a$, $b$ et tous entiers naturels $m$, $n$ : $a^{m+n} = a^m a^n$, $(a^m)^n = a^{mn}$ et $(ab)^n = a^n b^n$. Chacune se démontre par récurrence à partir de la définition récursive et des règles du produit : la première par récurrence sur $m$ à $n$ fixé, la deuxième par récurrence sur $n$ à $m$ fixé, en s'appuyant sur la première. Ces deux règles n'utilisent que l'associativité du produit et son élément neutre : elles valent aussi pour les matrices carrées et pour les itérées d'une application. La troisième repose en plus sur la commutativité : pour deux matrices $A$ et $B$ qui ne commutent pas, $(AB)^2 = ABAB$ diffère en général de $A^2 B^2$.

Quand l'utiliser : l'énoncé rappelle la définition $a^0 = 1$ et $a^{n+1} = a \cdot a^n$, ou celle d'une factorielle, d'une somme ou d'une itérée, et demande d'en déduire une règle de calcul.
1) Recenser les outils permis : les deux lignes de la définition, les règles du produit ambiant (associativité, élément neutre, et commutativité seulement si le produit est commutatif), les règles déjà démontrées et, dans l'hérédité, l'hypothèse de récurrence. La règle à démontrer est interdite avant la conclusion, comme tout argument par points de suspension.
2) Choisir la variable de récurrence pour que l'hérédité n'ait pas à réordonner le produit. La définition $a^{k+1} = a \cdot a^k$ ajoute son facteur à gauche : pour $a^{m+n} = a^m a^n$, la récurrence porte donc sur $m$, l'exposant du facteur de gauche. Fixer les autres variables avant de poser la propriété : « Soit $n \in \mathbb{N}$. Pour $m \in \mathbb{N}$, notons $P(m)$ : $a^{m+n} = a^m a^n$. »
3) Initialisation : faire apparaître $a^0 = 1$ dans le membre qui le contient.
4) Hérédité : « Soit $m \in \mathbb{N}$ tel que $P(m)$ soit vraie. Montrons $P(m+1)$. » Écrire l'exposant du rang $m + 1$ sous la forme $(\ldots) + 1$ pour appliquer la définition, puis appliquer l'hypothèse de récurrence, regrouper les facteurs par associativité, et reconnaître enfin la définition au rang $m + 1$. Chaque égalité porte sa justification.
5) Conclusion : « Par récurrence, $P(m)$ est vraie pour tout $m \in \mathbb{N}$. L'entier $n$ étant quelconque, l'égalité vaut pour tous $m, n \in \mathbb{N}$. »