Le raisonnement par récurrence

🀄 Manipule : déclenche l'effet domino

Pose la première pièce, vérifie que chaque pièce pousse la suivante, puis lance la cascade infinie.

13 dominos numérotés de 0 à 12 attendent debout. Commence par l'initialisation : fais tomber P(0).

🧱 Le problème : prouver une infinité de cas

Considère la formule : $1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2}$ . Elle marche pour $n = 1$ (le membre de gauche vaut 1, celui de droite aussi). Elle marche pour $n = 2$ , pour $n = 100$ , pour $n = 1 0^{6}$ …

Mais comment prouver qu'elle est vraie pour TOUS les entiers, c'est-à-dire pour une infinité de valeurs ? Tu ne peux pas les vérifier une par une : tu n'auras jamais fini.

L'idée géniale : au lieu de prouver une infinité de cas, on prouve seulement deux choses — et l'infini s'écroule tout seul, comme une rangée de dominos.

🀄 L'effet domino en deux étapes

Imagine une rangée infinie de dominos debout, numérotés $0, 1, 2, 3, \dots$ Tu veux qu'ils tombent tous. Il te suffit de garantir deux choses :

① Initialisation : tu fais tomber le premier domino, celui d'indice 0 (ou le premier rang concerné).
② Hérédité : tu garantis que chaque domino qui tombe pousse le suivant. Autrement dit, si $P (n)$ est vraie, alors $P (n + 1)$ est vraie aussi.

Si ces deux conditions sont réunies, la conclusion est imparable : le domino 0 tombe (par ①), donc il pousse le 1 (par ②), qui pousse le 2, qui pousse le 3… la cascade ne s'arrête jamais. Tous les dominos tombent.

📐 La rédaction type (à connaître par cœur)

On note $P (n)$ la propriété à démontrer. La rédaction suit toujours le même squelette en trois temps :

Initialisation. On vérifie que $P (n_{0})$ est vraie pour le premier rang $n_{0}$ .

Hérédité. On suppose $P (n)$ vraie pour un entier $n \geq n_{0}$ quelconque (c'est l'hypothèse de récurrence), et on démontre qu'alors $P (n + 1)$ est vraie.

Conclusion. Par principe de récurrence, $P (n)$ est vraie pour tout entier $n \geq n_{0}$ .

✍️ Exemple entièrement rédigé

Démontrons par récurrence que pour tout entier $n \geq 1$ : $1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2}$ On note $P (n)$ cette égalité.

Initialisation. Pour $n = 1$ : le membre de gauche vaut $1$ , et le membre de droite vaut $\frac{1 \times 2}{2} = 1$ . Les deux sont égaux, donc $P (1)$ est vraie.

Hérédité. Supposons $P (n)$ vraie pour un entier $n \geq 1$ fixé, c'est-à-dire : $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2} (hypoth \overset{e}{ˋ} se de r \overset{e}{ˊ} currence)$ Montrons alors $P (n + 1)$ . On ajoute $(n + 1)$ aux deux membres :

$1 + 2 + \dots + n + (n + 1) = \frac{n ( n + 1 )}{2} + (n + 1)$

$= (n + 1) (\frac{n}{2} + 1) = (n + 1) \cdot \frac{n + 2}{2} = \frac{( n + 1 ) ( n + 2 )}{2}$

Or $\frac{( n + 1 ) ( n + 2 )}{2}$ est exactement la formule au rang $n + 1$ (remplace $n$ par $n + 1$ dans $\frac{n ( n + 1 )}{2}$ ). Donc $P (n + 1)$ est vraie. L'hérédité est établie.

Conclusion. $P (1)$ est vraie et la propriété est héréditaire : par principe de récurrence, pour tout entier $n \geq 1$ , $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ . $■$

⚠️ Pourquoi les DEUX conditions sont indispensables

Beaucoup d'élèves oublient une étape. Or chacune est vitale : il suffit qu'une seule manque pour que la preuve s'effondre. Teste-le dans la visualisation ci-dessus.

Sans initialisation : l'hérédité dit « si un domino tombe, le suivant tombe ». Mais si aucun domino ne tombe jamais en premier, la chaîne reste debout pour l'éternité. Exemple piège : la propriété « $2^{n} > n^{2}$ » est héréditaire à partir d'un certain rang… mais fausse pour $n = 2, 3, 4$ . Sans vérifier le bon point de départ, on « démontre » du faux.
Sans hérédité : un seul maillon cassé suffit à arrêter la cascade. Si le domino $5$ ne pousse pas le $6$ , tous les dominos après $5$ restent debout, même si les premiers sont tombés. L'initialisation seule ne prouve qu'un cas.

Le faux classique : « tous les chevaux sont de la même couleur ». La preuve a une initialisation correcte et une hérédité qui semble marcher, mais elle échoue secrètement au passage de $n = 1$ à $n = 2$ . Moralité : l'hérédité doit être vraie pour tous les rangs, sans exception cachée.

🎯 Les pièges classiques au bac

Oublier d'utiliser l'hypothèse de récurrence : si tu ne te sers jamais de « $P (n)$ vraie » dans l'hérédité, c'est qu'il y a une erreur — la récurrence n'apporte rien.
Mauvais rang d'initialisation : pour une inégalité comme $2^{n} \geq n + 1$ , vérifie bien à partir de quel $n_{0}$ elle démarre.
Confondre « pour un $n$ fixé » et « pour tout $n$ » : dans l'hérédité, $n$ est un entier quelconque mais fixé, pas une variable libre.
Conclusion bâclée : le correcteur attend explicitement la phrase « par principe de récurrence, $P (n)$ est vraie pour tout $n \geq n_{0}$ ».
Hérédité « dans le mauvais sens » : on part de $P (n)$ pour aller vers $P (n + 1)$ , jamais l'inverse.

🎓 Le lien avec ton programme bac

Le raisonnement par récurrence est un attendu majeur de 1BAC SM (filière Sciences Maths). On l'utilise constamment :

Suites : démontrer qu'une suite est croissante, majorée, ou qu'elle vérifie une formule explicite $u_{n} = f (n)$ .
Inégalités : prouver $2^{n} \geq n^{2}$ , l'inégalité de Bernoulli $(1 + a)^{n} \geq 1 + na$ , etc.
Divisibilité : montrer que $n^{3} - n$ est divisible par $6$ , que $4^{n} - 1$ est divisible par $3$ …
Sommes : établir $k = 1 \sum n k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ et autres formules.
Calcul matriciel / probabilités : expression de $A^{n}$ , ou d'un état probabiliste après $n$ étapes.

C'est aussi un grand classique de l'épreuve écrite : presque chaque année, au moins une question commence par « Démontrer par récurrence que… ». Maîtriser le squelette de rédaction te garantit des points faciles.

← L'Atlas des concepts L'Atlas s'enrichit chaque semaine

Disponible dans 0 jour

Le raisonnement par récurrence

🀄 Manipule : déclenche l'effet domino

🧱 Le problème : prouver une infinité de cas

🀄 L'effet domino en deux étapes

📐 La rédaction type (à connaître par cœur)

✍️ Exemple entièrement rédigé

⚠️ Pourquoi les DEUX conditions sont indispensables

🎯 Les pièges classiques au bac

🎓 Le lien avec ton programme bac