Raisonnement par récurrence en terminale : cours et exercices

Objectifs du chapitre

Maîtriser les trois étapes incontournables d'une démonstration par récurrence : Initialisation, Hérédité, Conclusion.
Démontrer des formules explicites de sommes et de termes généraux de suites.
Démontrer des inégalités valables pour tout entier naturel $n \ge n_0$ .
Éviter les erreurs de logique classiques (oubli de l'initialisation, circularité).
Démontrer l'inégalité de Bernoulli et des propriétés de divisibilité par récurrence.
Utiliser la récurrence pour étudier une suite définie par $u_{n+1} = f(u_n)$ (encadrement, sens de variation).
Rédiger une récurrence de divisibilité (forme $u_n = 6m$ avec $m$ entier).

Le cours

1. Principe du raisonnement par récurrence

Soit $P(n)$ une propriété dépendant d'un entier naturel $n$ , et $n_0 \in \mathbb{N}$ :
1. Initialisation : On vérifie que la propriété $P(n_0)$ est vraie pour le premier rang $n_0$ .
2. Hérédité : On suppose que pour un entier $k \ge n_0$ fixé quelconque, la propriété $P(k)$ est vraie (c'est l'hypothèse de récurrence). On démontre alors que $P(k+1)$ est vraie sous cette hypothèse.
3. Conclusion : Par le principe de récurrence, la propriété $P(n)$ est vraie pour tout entier $n \ge n_0$ .

2. L'image des dominos et le rôle de chaque étape

On peut se représenter une récurrence comme une file infinie de dominos :

l'initialisation fait tomber le premier domino ;
l'hérédité garantit que si un domino tombe, le suivant tombe aussi.

Les deux étapes sont indispensables :

Sans hérédité, on ne sait rien au-delà des premiers rangs.
Sans initialisation, rien ne démarre. Exemple : la propriété $P(n)$ : « $9$ divise $10^n + 1$ » est héréditaire, car si $10^k + 1 = 9m$ , alors $10^{k+1} + 1 = 10(10^k + 1) - 9 = 9(10m - 1)$ . Pourtant elle n'est vraie pour aucun $n$ : $10^n + 1$ a pour somme des chiffres $2$ , il n'est jamais multiple de $9$ .

3. Inégalité de Bernoulli (démonstration exigible)

Pour tout réel $a > 0$ et tout entier naturel $n$ :
$(1 + a)^n \ge 1 + na$
Conséquence importante : si $q > 1$ , on écrit $q = 1 + a$ avec $a > 0$ , donc $q^n \ge 1 + na$ . Comme $\lim\limits_{n \to +\infty} (1 + na) = +\infty$ , on obtient par comparaison $\lim\limits_{n \to +\infty} q^n = +\infty$ (voir chapitre TA2).

4. Récurrence et suites $u_{n+1} = f(u_n)$

Si $f$ est croissante sur un intervalle $I$ et si tous les termes de la suite sont dans $I$ , alors une récurrence permet de « transporter » une inégalité d'un rang au suivant :
$a \le u_k \le u_{k+1} \le b \implies f(a) \le f(u_k) \le f(u_{k+1}) \le f(b)$
c'est-à-dire $f(a) \le u_{k+1} \le u_{k+2} \le f(b)$ .
On démontre ainsi, en une seule récurrence, que la suite est croissante et bornée.

Attention : si $f$ est décroissante, l'ordre des inégalités s'inverse et la suite n'est en général pas monotone.

5. Conjecturer avec Python, démontrer par récurrence

Un programme peut calculer les premiers termes et suggérer une propriété, mais il ne la démontre pas :

from math import sqrt
u = 0
for n in range(10):
    print(n, u)
    u = sqrt(3*u + 4)

Les valeurs affichées ( $0$ ; $2$ ; $3{,}16$ ; $3{,}73$ ; …) laissent penser que la suite est croissante et majorée par $4$ : c'est la récurrence qui le prouvera (voir méthode ci-dessous).

Méthodes et exemples rédigés

Méthode : Rédiger une récurrence pour une somme

Exemple

Démontrer que pour tout $n \ge 1$ , $S_n = 1 + 2 + \dots + n = \frac{n(n+1)}{2}$ .

Initialisation ( $n = 1$ ) : À gauche, $S_1 = 1$ . À droite, $\frac{1(1+1)}{2} = \frac{2}{2} = 1$ . L'égalité est vraie pour $n = 1$ .
Hérédité : Soit $k \ge 1$ un entier fixé. Supposons que $S_k = \frac{k(k+1)}{2}$ (HR). Montrons que $S_{k+1} = \frac{(k+1)(k+2)}{2}$ .
On a $S_{k+1} = S_k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$ . La propriété est donc héréditaire.
Conclusion : Par récurrence, pour tout $n \ge 1$ , $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ .

Méthode : Démontrer une inégalité par récurrence (Bernoulli)

Exemple

Soit $a > 0$ . Démontrer que pour tout $n \in \mathbb{N}$ , $(1 + a)^n \ge 1 + na$ .

Étape 1 (Énoncé) : Pour $n \in \mathbb{N}$ , on note $P(n)$ : « $(1 + a)^n \ge 1 + na$ ».
Étape 2 (Initialisation, $n = 0$ ) : $(1 + a)^0 = 1$ et $1 + 0 \times a = 1$ . On a bien $1 \ge 1$ , donc $P(0)$ est vraie.
Étape 3 (Hérédité) : Soit $k \in \mathbb{N}$ fixé tel que $(1 + a)^k \ge 1 + ka$ (HR). Comme $1 + a > 0$ , on peut multiplier les deux membres par $1 + a$ sans changer le sens :
$(1 + a)^{k+1} \ge (1 + ka)(1 + a) = 1 + a + ka + ka^2 = 1 + (k+1)a + ka^2$
Or $ka^2 \ge 0$ , donc $(1 + a)^{k+1} \ge 1 + (k+1)a$ : $P(k+1)$ est vraie.
Conclusion : Par récurrence, pour tout $n \in \mathbb{N}$ , $(1 + a)^n \ge 1 + na$ .

Méthode : Encadrer et étudier les variations d'une suite récurrente

Exemple

Soit $(u_n)$ définie par $u_0 = 0$ et $u_{n+1} = \sqrt{3u_n + 4}$ . Démontrer que pour tout $n \in \mathbb{N}$ , $0 \le u_n \le u_{n+1} \le 4$ .

Étape 1 (Fonction associée) : $u_{n+1} = f(u_n)$ avec $f(x) = \sqrt{3x + 4}$ . Sur $[0 ; +\infty[$ , $x \mapsto 3x + 4$ est croissante et positive, et la racine carrée est croissante, donc $f$ est croissante sur $[0 ; +\infty[$ .
Étape 2 (Initialisation) : $u_0 = 0$ et $u_1 = \sqrt{4} = 2$ . On a bien $0 \le 0 \le 2 \le 4$ .
Étape 3 (Hérédité) : Soit $k \in \mathbb{N}$ tel que $0 \le u_k \le u_{k+1} \le 4$ . Comme $f$ est croissante sur $[0 ; +\infty[$ :
$f(0) \le f(u_k) \le f(u_{k+1}) \le f(4)$
soit $2 \le u_{k+1} \le u_{k+2} \le \sqrt{16} = 4$ . Et puisque $0 \le 2$ , on obtient $0 \le u_{k+1} \le u_{k+2} \le 4$ .
Conclusion : Pour tout $n$ , $0 \le u_n \le u_{n+1} \le 4$ : la suite $(u_n)$ est croissante et majorée par $4$ . Elle converge donc (théorème de convergence monotone, chapitre TA2).

Méthode : Démontrer une divisibilité par récurrence

Exemple

Démontrer que pour tout $n \in \mathbb{N}$ , $7^n - 1$ est divisible par $6$ .

Étape 1 (Énoncé) : pour $n \in \mathbb{N}$ , on note $P(n)$ : « il existe un entier $m$ tel que $7^n - 1 = 6m$ ».
Étape 2 (Initialisation, $n = 0$ ) : $7^0 - 1 = 0 = 6 \times 0$ , donc $P(0)$ est vraie.
Étape 3 (Hérédité) : soit $k \in \mathbb{N}$ tel que $7^k - 1 = 6m$ avec $m$ entier (HR), c'est-à-dire $7^k = 6m + 1$ . Alors $7^{k+1} - 1 = 7 \times 7^k - 1 = 7(6m + 1) - 1 = 42m + 6 = 6(7m + 1)$ . Comme $7m + 1$ est un entier, $P(k+1)$ est vraie.
Conclusion : par récurrence, pour tout $n \in \mathbb{N}$ , $6$ divise $7^n - 1$ (contrôle : $7^2 - 1 = 48 = 6 \times 8$ ).

Pièges fréquents

Ne jamais écrire « supposons que pour tout $k$ , $P(k)$ est vraie » : cela reviendrait à supposer ce que l'on veut démontrer ! Il faut écrire « soit $k$ un entier fixé ».
Une propriété peut être héréditaire mais fausse pour tout $n$ si l'initialisation échoue !
Vérifier une propriété sur de nombreux exemples (à la main ou avec Python) n'est pas une démonstration : $n^2 + n + 41$ est premier pour $n = 0, 1, \dots, 39$ , mais pour $n = 40$ on obtient $1681 = 41^2$ .
$P(n)$ est une phrase (vraie ou fausse), pas un nombre : écrire « $P(n)$ : $u_n \le 4$ » et non « $P(n) = u_n$ ».
Dans l'hérédité, avant de multiplier une inégalité par une quantité, vérifier que celle-ci est positive (dans Bernoulli, $1 + a > 0$ ).

Questions de révision

Essaie de répondre de tête avant d'afficher la réponse.

Quelles sont les 3 étapes d'une démonstration par récurrence ?

1. Initialisation, 2. Hérédité, 3. Conclusion.

Dans l'étape d'hérédité, que suppose-t-on et que démontre-t-on ?

On suppose $P(k)$ vraie pour un entier fixé $k \ge n_0$ , et on démontre que $P(k+1)$ est vraie.

Énoncer l'inégalité de Bernoulli.

Pour tout réel $a > 0$ et tout $n \in \mathbb{N}$ : $(1 + a)^n \ge 1 + na$ .

Une propriété héréditaire est-elle forcément vraie ?

Non : il faut aussi l'initialisation. Exemple : « $9$ divise $10^n + 1$ » est héréditaire mais toujours fausse.

Pour montrer par récurrence que

u_n \le u_{n+1}

avec

u_{n+1} = f(u_n)

, quelle propriété de

f

est utile ?

La croissance de $f$ sur un intervalle contenant tous les termes de la suite.

Dans une récurrence de divisibilité, comment exploiter l'hypothèse «

6

divise

7^k - 1

» ?

On l'écrit $7^k = 6m + 1$ avec $m$ entier, puis on remplace dans $7^{k+1} = 7 \times 7^k$ pour factoriser par $6$ .

Exercices corrigés

Exercice 1 Étape d'initialisation

Palier 1 · découverte

On souhaite démontrer par récurrence pour tout $n \ge 2$ la propriété $P(n) : 2^n > n+1$ . Quelle est l'initialisation correcte ?

Pour $n = 2 : 2^2 = 4$ et $2+1 = 3$ . Comme $4 > 3$ , $P(2)$ est vraie.
Pour $n = 0 : 2^0 = 1$ et $0+1 = 1$ , vrai.
Pour $n = 1 : 2^1 = 2$ et $1+1 = 2$ , vrai.
Pour $n = 3 : 2^3 = 8$ et $3+1 = 4$ , vrai.

Un indice

Le premier rang demandé est $n_0 = 2$ .

Voir la correction

Bonne réponse : A. Pour $n = 2 : 2^2 = 4$ et $2+1 = 3$ . Comme $4 > 3$ , $P(2)$ est vraie.

Comme l'inégalité doit être démontrée pour $n \ge 2$ , l'initialisation se fait au premier rang $n = 2$ : $2^2 = 4 > 3$ .

Exercice 2 Étape d'hérédité : ce qu'il faut démontrer

Palier 2 · application

On considère la suite définie par $u_0 = 0$ et $u_{n+1} = 2u_n + 1$ . On veut démontrer par récurrence que, pour tout $n \in \mathbb{N}$ , $P(n) : u_n = 2^n - 1$ .
Dans l'étape d'hérédité, on suppose $P(n)$ vraie pour un entier $n$ fixé. Que doit-on alors démontrer ?

$u_{n+1} = 2^{n+1} - 1$
$u_n = 2^n - 1$ pour tout entier $n$
$u_{n+1} = 2u_n + 1$
$u_0 = 2^0 - 1$

Un indice

L'hérédité consiste à montrer : si $P(n)$ est vraie, alors $P(n+1)$ est vraie.

Voir la correction

Bonne réponse : A. $u_{n+1} = 2^{n+1} - 1$

Hérédité : on suppose $u_n = 2^n - 1$ (hypothèse de récurrence) et on doit montrer $P(n+1) : u_{n+1} = 2^{n+1} - 1$ .
Preuve : $u_{n+1} = 2u_n + 1 = 2(2^n - 1) + 1 = 2^{n+1} - 2 + 1 = 2^{n+1} - 1$ .
Attention : « $u_n = 2^n - 1$ pour tout $n$ » est la conclusion de toute la récurrence, pas ce qu'on démontre dans l'hérédité ; $u_{n+1} = 2u_n + 1$ est la définition de la suite et $u_0 = 2^0 - 1$ est l'initialisation.

Exercice 3 Récurrence sur une somme : 1 + 3 + … + (2n − 1) = n²

Palier 3 · approfondissement

Pour $n \ge 1$ , on pose $S_n = 1 + 3 + 5 + \dots + (2n - 1)$ (somme des $n$ premiers entiers impairs) et on veut prouver par récurrence que $S_n = n^2$ .
En supposant $S_n = n^2$ , que vaut $S_{n+1}$ ?

$S_{n+1} = n^2 + 2n + 1 = (n+1)^2$
$S_{n+1} = n^2 + 2n - 1$
$S_{n+1} = n^2 + 2n + 3$
$S_{n+1} = n^2 + 1$

Un indice

$S_{n+1}$ s'obtient en ajoutant à $S_n$ le $(n+1)$ -ième nombre impair, c'est-à-dire $2(n+1) - 1$ .

Voir la correction

Bonne réponse : A. $S_{n+1} = n^2 + 2n + 1 = (n+1)^2$

Initialisation : $S_1 = 1 = 1^2$ .
Hérédité : supposons $S_n = n^2$ . Le terme suivant de la somme est $2(n+1) - 1 = 2n + 1$ , donc
$S_{n+1} = S_n + (2n + 1) = n^2 + 2n + 1 = (n+1)^2.$
Conclusion : par récurrence, $S_n = n^2$ pour tout $n \ge 1$ .
Erreur fréquente : ajouter $2n - 1$ (le dernier terme de $S_n$ , déjà compté) au lieu de $2n + 1$ .

Exercice 4 Récurrence et divisibilité

Palier 4 · défi

On veut démontrer par récurrence que, pour tout $n \in \mathbb{N}$ , le nombre $4^n + 2$ est divisible par $3$ .
Quelle égalité permet de conclure l'étape d'hérédité à partir de l'hypothèse « $4^n + 2$ est divisible par 3 » ?

$4^{n+1} + 2 = 4(4^n + 2) - 6$
$4^{n+1} + 2 = 4(4^n + 2)$
$4^{n+1} + 2 = (4^n + 2) + 3$
$4^{n+1} + 2 = 4^n + 6$

Un indice

Fais apparaître $4^n + 2$ dans $4^{n+1} + 2 = 4 \times 4^n + 2$ .

Voir la correction

Bonne réponse : A. $4^{n+1} + 2 = 4(4^n + 2) - 6$

Initialisation : $4^0 + 2 = 3$ , divisible par 3.
Hérédité : supposons $4^n + 2 = 3k$ avec $k \in \mathbb{Z}$ . Alors
$4^{n+1} + 2 = 4 \times 4^n + 8 - 6 = 4(4^n + 2) - 6 = 12k - 6 = 3(4k - 2),$
qui est divisible par 3.
Conclusion : pour tout $n \in \mathbb{N}$ , $3$ divise $4^n + 2$ .
Les autres égalités sont fausses (par exemple $4(4^n + 2) = 4^{n+1} + 8 \neq 4^{n+1} + 2$ ).

Objectifs du chapitre

Le cours

1. Principe du raisonnement par récurrence

2. L'image des dominos et le rôle de chaque étape

3. Inégalité de Bernoulli (démonstration exigible)

4. Récurrence et suites un+1=f(un)u_{n+1} = f(u_n)un+1​=f(un​)

5. Conjecturer avec Python, démontrer par récurrence

Méthodes et exemples rédigés

Méthode : Rédiger une récurrence pour une somme

Méthode : Démontrer une inégalité par récurrence (Bernoulli)

Méthode : Encadrer et étudier les variations d'une suite récurrente

Méthode : Démontrer une divisibilité par récurrence

Pièges fréquents

Questions de révision

Exercices corrigés

Exercice 1 Étape d'initialisation

Exercice 2 Étape d'hérédité : ce qu'il faut démontrer

Exercice 3 Récurrence sur une somme : 1 + 3 + … + (2n − 1) = n²

Exercice 4 Récurrence et divisibilité

4. Récurrence et suites $u_{n+1} = f(u_n)$