Tle 🧮 Algèbre Étape 11 / 11 du parcours

Le raisonnement par récurrence

Le raisonnement par récurrence en Terminale : initialisation, hérédité, conclusion, illustrés par des dominos animés et des exemples rédigés pas à pas.

📚 Avant de commencer, il faut savoir : Suites arithmétiques et géométriques

Si le premier domino tombe et que chacun fait tomber le suivant, tous tombent.

$1 = 1$ , $1 + 3 = 4$ , $1 + 3 + 5 = 9$ , $1 + 3 + 5 + 7 = 16$ : toujours un carré ! Mais vérifier un million de cas ne prouve rien pour tous les entiers.

Le raisonnement par récurrence le prouve en deux étapes, comme une rangée de dominos.

Le principe des dominos

Imagine une rangée infinie de dominos numérotés 1, 2, 3… Pour être sûr qu’ils tomberont tous, deux choses suffisent :

le premier domino tombe ;
chaque domino, s’il tombe, fait tomber le suivant.

Alors le domino 1 fait tomber le 2, qui fait tomber le 3, et ainsi de suite, sans fin. Remplace « le domino $n$ tombe » par « la propriété $P(n)$ est vraie » : tu as le raisonnement par récurrence.

Principe de récurrence

Soit $P(n)$ une propriété qui dépend d’un entier naturel $n$ , et $n_0$ un entier. Si :

Initialisation : $P(n_0)$ est vraie ;
Hérédité : pour tout entier $n \geqslant n_0$ , si $P(n)$ est vraie, alors $P(n+1)$ est vraie ;

alors conclusion : $P(n)$ est vraie pour tout entier $n \geqslant n_0$ .

Un peu d’histoire

Les mathématiciens ont utilisé ce raisonnement bien avant de lui donner un nom. En 1575, l’Italien Francesco Maurolico s’en sert pour prouver que la somme des premiers nombres impairs est un carré, exactement l’exemple 1 de cette leçon ! Vers 1654, Blaise Pascal l’écrit très clairement dans son Traité du triangle arithmétique, avec ses deux « lemmes » qui ressemblent à notre initialisation et à notre hérédité. Le nom « induction mathématique » apparaît en 1838 sous la plume de l’Anglais Augustus De Morgan. Et en 1889, l’Italien Giuseppe Peano place ce principe parmi les axiomes qui définissent les nombres entiers eux-mêmes.

Dans l’hérédité, on suppose que $P(n)$ est vraie pour un certain $n$ (c’est l’hypothèse de récurrence) et on démontre $P(n+1)$ . On ne suppose pas que la propriété est vraie partout : on montre seulement que la vérité se transmet d’un rang au suivant.

Pourquoi c’est vrai ?— facultatif, à sauter en première lecture

Pourquoi le principe de récurrence est-il valable ? Raisonnons par l’absurde : supposons l’initialisation et l’hérédité vraies, mais que $P(n)$ soit fausse pour au moins un entier $n \geqslant n_0$ .

Parmi ces entiers « mauvais », il y en a un plus petit, notons-le $m$ (tout ensemble non vide d’entiers naturels a un plus petit élément). Comme $P(n_0)$ est vraie, $m > n_0$ , donc $m - 1 \geqslant n_0$ . Et $m - 1$ n’est pas mauvais, puisque $m$ est le plus petit : $P(m-1)$ est vraie. Par hérédité, $P(m)$ est vraie… contradiction ! Il n’y a donc aucun entier mauvais.

Choisis un scénario puis pousse le premier domino. Dans le premier cas, toute la chaîne tombe. Dans les deux autres, il manque une des deux conditions… et la preuve s’effondre.

Exemple 1 : la somme des nombres impairs

Démontrer que 1 + 3 + 5 + … + (2n − 1) = n² pour tout n ⩾ 1

Notons $P(n)$ : « $1 + 3 + \dots + (2n - 1) = n^2$ ».

Initialisation. Pour $n = 1$ : le membre de gauche vaut $1$ et $1^2 = 1$ . Donc $P(1)$ est vraie.

Hérédité. Soit $n \geqslant 1$ tel que $P(n)$ est vraie. Alors :

\underbrace{1 + 3 + \dots + (2n-1)}_{= n^2 \text{ par hypothèse}} + (2n+1) = n^2 + 2n + 1 = (n+1)^2

C’est exactement $P(n+1)$ , car le $(n+1)$ -ième nombre impair est $2(n+1) - 1 = 2n + 1$ .

Conclusion. $P(1)$ est vraie et la propriété est héréditaire : $P(n)$ est vraie pour tout $n \geqslant 1$ .

Exemple 2 : majorer une suite

La récurrence sert énormément pour étudier les suites définies par $u_{n+1} = f(u_n)$ .

Le médicament ne dépasse jamais 200 mg

Un patient prend 100 mg d’un médicament par jour et en élimine la moitié en 24 h : $u_1 = 100$ et $u_{n+1} = 0{,}5\,u_n + 100$ . Montrons que $u_n \leqslant 200$ pour tout $n \geqslant 1$ .

Initialisation. $u_1 = 100 \leqslant 200$ : vrai.

Hérédité. Supposons $u_n \leqslant 200$ . En multipliant par $0{,}5$ (positif, le sens ne change pas) : $0{,}5\,u_n \leqslant 100$ . En ajoutant 100 : $u_{n+1} \leqslant 200$ .

Conclusion. Pour tout $n \geqslant 1$ , $u_n \leqslant 200$ : la dose ne dépassera jamais 200 mg.

On montrerait de même que la suite est croissante ( $u_n \leqslant u_{n+1}$ ) : croissante et majorée, elle converge.

Exemple 3 : l’inégalité de Bernoulli

Pour tout réel a > 0 et tout entier n : (1 + a)ⁿ ⩾ 1 + na

Initialisation. Pour $n = 0$ : $(1 + a)^0 = 1$ et $1 + 0 \times a = 1$ . On a bien $1 \geqslant 1$ .

Hérédité. Supposons $(1+a)^n \geqslant 1 + na$ . On multiplie par $1 + a$ , qui est positif :

(1+a)^{n+1} \geqslant (1 + na)(1 + a) = 1 + (n+1)a + na^2 \geqslant 1 + (n+1)a

car $na^2 \geqslant 0$ . C’est $P(n+1)$ .

Conclusion. L’inégalité est vraie pour tout $n \in \mathbb{N}$ .

Cette inégalité explique pourquoi $q^n$ tend vers $+\infty$ quand $q > 1$ : en posant $q = 1 + a$ , on a $q^n \geqslant 1 + na$ , qui tend vers $+\infty$ .

Les pièges

Ne jamais oublier l’initialisation

Considère $P(n)$ : « $10^n + 1$ est divisible par 9 ». L’hérédité marche ! Si $10^n + 1 = 9k$ , alors

10^{n+1} + 1 = 10 \times 10^n + 1 = 10(9k - 1) + 1 = 90k - 9 = 9(10k - 1).

Pourtant, $10^0 + 1 = 2$ , $10^1 + 1 = 11$ … ne sont pas divisibles par 9. La propriété est fausse pour tout $n$ : l’hérédité seule ne prouve rien, c’est le scénario « personne ne pousse le premier domino ».

Bien rédiger

Écris clairement $P(n)$ avant de commencer.
Dans l’hérédité, repère l’endroit où tu utilises l’hypothèse de récurrence : c’est le cœur de la preuve.
Vérifie que ton initialisation est au bon rang $n_0$ : 0, 1 ou un autre selon l’énoncé.

À quoi ça sert dans la vraie vie ?

Informatique : pour prouver qu’un programme avec une boucle est correct, on montre qu’une propriété (un « invariant ») est vraie avant la boucle et reste vraie après chaque tour. C’est une récurrence, utilisée pour certifier les logiciels des avions ou du métro automatique.
Jeux et algorithmes : aux tours de Hanoï, on démontre par récurrence qu’il faut $2^n - 1$ déplacements pour $n$ disques. Avec 64 disques, cela fait environ $1{,}8 \times 10^{19}$ coups : des milliards de siècles à un coup par seconde.
Finance : la formule $C_n = C_0 \times 1{,}03^n$ d’un placement à 3 % se démontre par récurrence. 2 000 € deviennent environ 3 612 € au bout de 20 ans.
Réseaux : dans un groupe de $n$ personnes qui se saluent toutes, il y a $\frac{n(n-1)}{2}$ poignées de main (récurrence : la $(n+1)$ -ième personne en ajoute $n$ ). Pour 30 élèves, cela fait 435 poignées de main.

🎯 Quiz : vérifie ce que tu as compris

Dans une récurrence, l’étape « on suppose P(n) vraie et on démontre P(n+1) » s’appelle :
On veut prouver une propriété pour tout n ⩾ 3. À quel rang fait-on l’initialisation ?
La propriété « 10ⁿ + 1 est divisible par 9 » est héréditaire. Est-elle vraie pour tout n ?
D’après 1 + 3 + 5 + … + (2n − 1) = n², combien vaut la somme des 25 premiers nombres impairs ?
Aux tours de Hanoï, il faut 2ⁿ − 1 déplacements pour n disques. Combien en faut-il pour 10 disques ?
Dans une classe de 20 élèves, chacun serre la main de tous les autres une fois. Combien de poignées de main en tout ?