Raisonnement par récurrence et suites

Ce que tu sais déjà. Tu sais définir une suite de façon explicite ou par récurrence, calculer ses premiers termes et étudier son sens de variation (Première — Suites : générer, représenter, variations), et tu connais les suites arithmétiques et géométriques, leurs sommes (Première — Suites arithmétiques et géométriques). En Terminale, on apprend à démontrer une propriété pour tous les entiers naturels, pas seulement à la vérifier sur quelques termes.

1. Suites majorées, minorées, bornées

Définitions. Soit $(u_n)$ une suite de nombres réels.

• $(u_n)$ est majorée s’il existe un réel $M$ tel que, pour tout entier naturel $n$, $u_n \leqslant M$. On dit que $M$ est un majorant de la suite.
• $(u_n)$ est minorée s’il existe un réel $m$ tel que, pour tout $n$, $u_n \geqslant m$ ($m$ est un minorant).
• $(u_n)$ est bornée si elle est à la fois majorée et minorée.

Remarque. Un majorant n’est pas unique : si $M$ majore la suite, $M + 1$ aussi. Et l’ordre des quantificateurs compte : « il existe $M$ tel que pour tout $n$ » — le même $M$ doit convenir pour tous les termes.

Exemples.

• $u_n = 3 - \dfrac{2}{n + 1}$ : pour tout $n$, $0 < \dfrac{2}{n+1} \leqslant 2$, donc $1 \leqslant u_n < 3$. La suite est bornée (minorée par $1$, majorée par $3$).
• $v_n = n^2$ est minorée par $0$ mais pas majorée : pour n’importe quel réel $M$, on trouve un entier $n > \sqrt{|M|}$, et alors $v_n > M$.
• $w_n = (-1)^n \times n$ n’est ni majorée ni minorée ($w_{2k} = 2k$ et $w_{2k+1} = -(2k+1)$).

Propriété (utile). Une suite croissante est minorée par son premier terme ; une suite décroissante est majorée par son premier terme.

→ S’entraîner : Exercice 1

2. Le principe de récurrence

Vérifier une propriété pour $n = 0, 1, 2, \dots, 100$ ne prouve rien pour $n = 101$. Pour démontrer qu’une propriété $\mathcal{P}(n)$ est vraie pour tout entier $n \geqslant n_0$, on utilise l’image des dominos : si le premier tombe, et si chaque domino qui tombe fait tomber le suivant, alors tous tombent.

Axiome (principe de récurrence). Soit $\mathcal{P}(n)$ une propriété qui dépend d’un entier naturel $n$, et $n_0$ un entier naturel. Si :

1. Initialisation : $\mathcal{P}(n_0)$ est vraie ;
2. Hérédité : pour tout entier $k \geqslant n_0$, si $\mathcal{P}(k)$ est vraie, alors $\mathcal{P}(k + 1)$ est vraie ;

alors $\mathcal{P}(n)$ est vraie pour tout entier $n \geqslant n_0$.

Attention. Dans l’hérédité, on ne suppose pas que $\mathcal{P}(k)$ est vraie pour tout $k$ (ce serait ce qu’on veut démontrer !) : on fixe un entier $k$, on suppose $\mathcal{P}(k)$ (c’est l’hypothèse de récurrence) et on en déduit $\mathcal{P}(k + 1)$.

Exemple (formule explicite). Soit $(u_n)$ définie par $u_0 = 0$ et $u_{n+1} = 2u_n + 1$. Les premiers termes sont $0, 1, 3, 7, 15$ : on conjecture que $u_n = 2^n - 1$.

Pour tout $n \in \mathbb{N}$, notons $\mathcal{P}(n)$ : « $u_n = 2^n - 1$ ».

• Initialisation. $u_0 = 0$ et $2^0 - 1 = 0$ : $\mathcal{P}(0)$ est vraie.
• Hérédité. Soit $k \in \mathbb{N}$ tel que $u_k = 2^k - 1$. But : $u_{k+1} = 2^{k+1} - 1$. Or $u_{k+1} = 2u_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$. Donc $\mathcal{P}(k+1)$ est vraie.
• Conclusion. Pour tout $n \in \mathbb{N}$, $u_n = 2^n - 1$.

→ S’entraîner : Exercice 2

3. Sommes et divisibilité

La récurrence est l’outil naturel pour les formules de sommes : pour passer de $\mathcal{P}(k)$ à $\mathcal{P}(k + 1)$, on ajoute le terme suivant.

Exemple (somme des impairs). Pour tout $n \geqslant 1$, $\mathcal{P}(n)$ : « $1 + 3 + 5 + \dots + (2n - 1) = n^2$ ».

• Initialisation. Pour $n = 1$ : la somme vaut $1$ et $1^2 = 1$.
• Hérédité. Supposons $1 + 3 + \dots + (2k - 1) = k^2$ pour un entier $k \geqslant 1$. Alors $1 + 3 + \dots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2$ : c’est $\mathcal{P}(k + 1)$ (le dernier impair est bien $2(k+1) - 1 = 2k + 1$).
• Conclusion. La propriété est vraie pour tout $n \geqslant 1$.

Divisibilité. « $a$ est divisible par $d$ » signifie qu’il existe un entier $m$ tel que $a = d \times m$. Dans l’hérédité, on écrit l’hypothèse sous cette forme, puis on fait apparaître $d$ en facteur.

Exemple. Pour tout $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$.

• Initialisation. $4^0 - 1 = 0 = 3 \times 0$.
• Hérédité. Supposons $4^k - 1 = 3m$ avec $m$ entier, c’est-à-dire $4^k = 3m + 1$. Alors $4^{k+1} - 1 = 4 \times 4^k - 1 = 4(3m + 1) - 1 = 12m + 3 = 3(4m + 1)$, et $4m + 1$ est entier.
• Conclusion. $4^n - 1$ est divisible par $3$ pour tout $n$.

Piège : ne jamais oublier l’initialisation. La propriété « $4^n + 1$ est divisible par $3$ » est héréditaire : si $4^k + 1 = 3m$, alors $4^k = 3m - 1$ et $4^{k+1} + 1 = 4(3m - 1) + 1 = 12m - 3 = 3(4m - 1)$. Et pourtant elle est fausse pour tout $n$ : $4^0 + 1 = 2$, $4^1 + 1 = 5$, $4^2 + 1 = 17$… (d’après l’exemple précédent, $4^n + 1 = (4^n - 1) + 2$ laisse toujours un reste $2$ dans la division par $3$). Aucun domino ne tombe au départ.

→ S’entraîner : Exercice 3 · Exercice 4 · Exercice 5

4. Démontrer une inégalité

Pour une inégalité, l’hérédité consiste souvent à multiplier ou ajouter membre à membre, en contrôlant les signes.

Propriété (inégalité de Bernoulli). Pour tout réel $a > 0$ et tout entier naturel $n$ :

$$(1 + a)^n \geqslant 1 + na.$$

Exemple (initialisation à un rang $n_0 > 0$). Pour tout entier $n \geqslant 3$, $2^n \geqslant 2n + 1$.

• Initialisation. $2^3 = 8$ et $2 \times 3 + 1 = 7$ : vrai. (C’est faux pour $n = 2$ : $4 < 5$.)
• Hérédité. Si $2^k \geqslant 2k + 1$ avec $k \geqslant 3$, alors $2^{k+1} = 2 \times 2^k \geqslant 4k + 2$. Il suffit que $4k + 2 \geqslant 2(k + 1) + 1 = 2k + 3$, c’est-à-dire $2k \geqslant 1$ : vrai. Donc $2^{k+1} \geqslant 2(k+1) + 1$.
• Conclusion. Vrai pour tout $n \geqslant 3$.

→ S’entraîner : Exercice 6

5. Suites définies par une fonction : bornes et variations

Pour une suite définie par $u_{n+1} = f(u_n)$, on démontre souvent en une seule récurrence un encadrement et le sens de variation, en utilisant les variations de $f$.

Propriété clé. Si $f$ est croissante sur un intervalle $I$, alors pour tous $a \leqslant b$ dans $I$, $f(a) \leqslant f(b)$ : on peut « appliquer $f$ » à une inégalité sans en changer le sens.

Exemple. $u_0 = 0$ et $u_{n+1} = \sqrt{3u_n + 4}$. La fonction $f : x \mapsto \sqrt{3x + 4}$ est croissante sur $\left[-\dfrac43\,;\,+\infty\right[$ (composée de $x \mapsto 3x + 4$ croissante et de la racine carrée croissante), et $f(4) = \sqrt{16} = 4$.

Pour tout $n$, $\mathcal{P}(n)$ : « $0 \leqslant u_n \leqslant u_{n+1} \leqslant 4$ ».

• Initialisation. $u_0 = 0$, $u_1 = \sqrt4 = 2$ : $0 \leqslant 0 \leqslant 2 \leqslant 4$.
• Hérédité. Si $0 \leqslant u_k \leqslant u_{k+1} \leqslant 4$, comme $f$ est croissante sur $[0\,;\,4]$ : $f(0) \leqslant f(u_k) \leqslant f(u_{k+1}) \leqslant f(4)$, soit $2 \leqslant u_{k+1} \leqslant u_{k+2} \leqslant 4$, et a fortiori $0 \leqslant u_{k+1} \leqslant u_{k+2} \leqslant 4$.
• Conclusion. La suite est croissante et bornée par $0$ et $4$.

Conjecturer avant de démontrer. Un programme permet de calculer les termes et de conjecturer ; seule la récurrence démontre.

from math import sqrt

u = 0
for n in range(8):
    print(n, round(u, 4))
    u = sqrt(3 * u + 4)
# 0 0 / 1 2.0 / 2 3.1623 / 3 3.6724 / 4 3.8752 ...

→ S’entraîner : Exercice 7 · Exercice 8

À retenir.

• Majorée : un même $M$ tel que $u_n \leqslant M$ pour tout $n$ ; bornée = majorée et minorée.
• Récurrence : initialisation + hérédité (on suppose $\mathcal{P}(k)$ pour un $k$ fixé, on montre $\mathcal{P}(k+1)$) ⟹ $\mathcal{P}(n)$ pour tout $n \geqslant n_0$.
• L’hypothèse de récurrence doit servir dans l’hérédité ; sans initialisation, rien n’est prouvé.
• Bernoulli : $(1 + a)^n \geqslant 1 + na$ pour $a > 0$.
• Pour $u_{n+1} = f(u_n)$ avec $f$ croissante : on applique $f$ à l’encadrement $u_k \leqslant u_{k+1} \leqslant \ell$.