5 modèles de démonstration par récurrence (à recopier au bac)

Pourquoi apprendre des modèles de récurrence ?

Le raisonnement par récurrence est l'un des outils les plus rentables du programme de Première et Terminale spé maths. Il possède une structure imposée que le correcteur du bac connaît par cœur : initialisation, hérédité, conclusion. S'écarter de cette charpente, c'est risquer de perdre des points même quand le calcul est juste. La bonne nouvelle ? La quasi-totalité des récurrences du bac se rangent dans cinq grandes familles. Apprenez les cinq modèles ci-dessous et vous saurez rédiger proprement n'importe quel exercice.

Le squelette commun à toute récurrence

Initialisation : on vérifie la propriété $P (n_{0})$ au premier rang.
Hérédité : on suppose $P (n)$ vraie pour un entier $n \geq n_{0}$ fixé (hypothèse de récurrence), et on démontre $P (n + 1)$ .
Conclusion : par principe de récurrence, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Modèle 1 — Récurrence sur une somme

Énoncé type : démontrer que $k = 1 \sum n k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ pour tout $n \geq 1$ .

Rédaction pas à pas

Notons $P (n)$ : « $k = 1 \sum n k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ ».

Initialisation. Pour $n = 1$ : le membre de gauche vaut $1^{2} = 1$ ; le membre de droite vaut $\frac{1 \times 2 \times 3}{6} = 1$ . Donc $P (1)$ est vraie.

Hérédité. Supposons $P (n)$ vraie pour un entier $n \geq 1$ fixé. Alors :

k = 1 \sum n + 1 k^{2} = = \frac{n ( n + 1 ) ( 2 n + 1 )}{6} k = 1 \sum n k^{2} + (n + 1)^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6} + (n + 1)^{2} .

On met au même dénominateur :

= \frac{( n + 1 ) [ n ( 2 n + 1 ) + 6 ( n + 1 ) ]}{6} = \frac{( n + 1 ) ( 2 n ^{2} + 7 n + 6 )}{6} = \frac{( n + 1 ) ( n + 2 ) ( 2 n + 3 )}{6} .

Or $(n + 2) = (n + 1) + 1$ et $(2 n + 3) = 2 (n + 1) + 1$ : on reconnaît exactement la formule au rang $n + 1$ . Donc $P (n + 1)$ est vraie.

Conclusion. Par récurrence, $P (n)$ est vraie pour tout $n \geq 1$ . $■$

Modèle 2 — Récurrence sur une inégalité

Énoncé type : démontrer que $2^{n} \geq n + 1$ pour tout $n \geq 0$ .

Initialisation. Pour $n = 0$ : $2^{0} = 1 \geq 0 + 1 = 1$ . Vrai.

Hérédité. Supposons $2^{n} \geq n + 1$ . Alors $2^{n + 1} = 2 \times 2^{n} \geq 2 (n + 1) = 2 n + 2$ . Comme $2 n + 2 \geq n + 2$ (car $n \geq 0$ ), on obtient $2^{n + 1} \geq (n + 1) + 1$ .

Conclusion. Par récurrence, $2^{n} \geq n + 1$ pour tout $n \geq 0$ . $■$

Le geste clé : dans une inégalité, on part du membre obtenu après l'hypothèse, puis on minore (ou majore) par étapes jusqu'à retrouver la forme voulue. Chaque inégalité doit être justifiée.

Modèle 3 — Récurrence sur une suite définie par récurrence

Énoncé type : soit $(u_{n})$ définie par $u_{0} = 0$ et $u_{n + 1} = \frac{1}{2} u_{n} + 3$ . Montrer que pour tout $n$ , $0 \leq u_{n} \leq 6$ .

Initialisation. $u_{0} = 0$ , donc $0 \leq u_{0} \leq 6$ . Vrai.

Hérédité. Supposons $0 \leq u_{n} \leq 6$ . Alors $0 \leq \frac{1}{2} u_{n} \leq 3$ , puis $3 \leq \frac{1}{2} u_{n} + 3 \leq 6$ . Donc $0 \leq u_{n + 1} \leq 6$ .

Conclusion. Par récurrence, $0 \leq u_{n} \leq 6$ pour tout $n$ . $■$

Modèle 4 — Récurrence pour la monotonie d'une suite

Énoncé type : avec la même suite, montrer que $(u_{n})$ est croissante, c'est-à-dire $u_{n} \leq u_{n + 1}$ pour tout $n$ .

Initialisation. $u_{0} = 0$ et $u_{1} = 3$ , donc $u_{0} \leq u_{1}$ . Vrai.

Hérédité. Supposons $u_{n} \leq u_{n + 1}$ . La fonction $x \mapsto \frac{1}{2} x + 3$ est croissante, donc $\frac{1}{2} u_{n} + 3 \leq \frac{1}{2} u_{n + 1} + 3$ , c'est-à-dire $u_{n + 1} \leq u_{n + 2}$ .

Conclusion. Par récurrence, $(u_{n})$ est croissante. $■$

Modèle 5 — Récurrence sur une propriété de divisibilité

Énoncé type : montrer que $7^{n} - 1$ est divisible par $6$ pour tout $n \geq 0$ .

Initialisation. Pour $n = 0$ : $7^{0} - 1 = 0 = 6 \times 0$ . Divisible par $6$ .

Hérédité. Supposons qu'il existe un entier $m$ tel que $7^{n} - 1 = 6 m$ . Alors :

7^{n + 1} - 1 = 7 \times 7^{n} - 1 = 7 (6 m + 1) - 1 = 42 m + 6 = 6 (7 m + 1) .

C'est un multiple de $6$ , donc $P (n + 1)$ est vraie.

Conclusion. Par récurrence, $6 ∣ 7^{n} - 1$ pour tout $n \geq 0$ . $■$

Les pièges qui coûtent des points

Oublier l'initialisation : sans elle, la récurrence ne démarre pas. Une hérédité seule ne prouve rien.
Mélanger « pour tout $n$ » et « il existe $n$ » : dans l'hérédité, $n$ est un entier fixé, pas tous les entiers.
Utiliser ce qu'on veut prouver : on suppose $P (n)$ , jamais $P (n + 1)$ .
Conclure sur le mauvais rang : si l'initialisation est faite à $n_{0} = 1$ , la conclusion porte sur $n \geq 1$ , pas $n \geq 0$ .

À retenir. Toute récurrence se résume à trois mots : initialisation, hérédité, conclusion. Repérez d'abord à quel modèle (somme, inégalité, suite, monotonie, divisibilité) l'énoncé appartient, recopiez la trame correspondante, et soignez la phrase de conclusion : « Par principe de récurrence,

P (n)

est vraie pour tout

n \geq n_{0}

. »

Comment reconnaître le bon modèle en un coup d'œil

Au brouillon, posez-vous une seule question : « que dois-je démontrer pour tout $n$ ? » La forme de la propriété vous oriente immédiatement vers l'un des cinq modèles.

Une égalité avec un symbole somme $\sum$ ou un produit : modèle 1.
Une inégalité ( $\leq$ , $\geq$ ) : modèle 2, on minore ou on majore par étapes.
Un encadrement d'une suite définie par $u_{n + 1} = f (u_{n})$ : modèle 3.
Une monotonie (« la suite est croissante ») : modèle 4, on compare $u_{n}$ et $u_{n + 1}$ .
Un multiple ou « divisible par » : modèle 5, on factorise un facteur commun.

Soigner la phrase d'hérédité

La rédaction de l'hérédité fait gagner ou perdre les points clés. Commencez toujours par : « Supposons $P (n)$ vraie pour un entier $n \geq n_{0}$ fixé. » Le mot fixé est crucial : il rappelle que $n$ n'est pas « tous les entiers », mais un entier particulier dont on suppose la propriété. Terminez par : « donc $P (n + 1)$ est vraie », qui referme proprement le raisonnement. Entre les deux, faites toujours apparaître l'hypothèse de récurrence de façon visible — par exemple en soulignant le terme remplacé, comme dans le modèle 1.

Pour aller plus loin : la méthode complète de la récurrence et nos conseils pour rédiger une démonstration.