Compétences
Des thèmes transversaux pour vous aider à réussir vos épreuves de mathématiques.
1 / 5
Récurrence
Initialisation, hérédité, conclusion : le schéma qui revient dans les suites et au Bac.
Récurrence
Pour montrer qu’une propriété $P(n)$ est vraie pour tout entier $n \geq n_0$, on procède comme avec des dominos : on fait tomber le premier, puis on montre que si l’un tombe, le suivant tombe aussi.
Initialisation
Le premier domino tombe.
$P(n_0)$ est vraie.
Hérédité
Un domino entraîne le suivant.
$P(k) \Rightarrow P(k+1)$.
Conclusion
Toute la file tombe.
$P(n)$ pour tout $n \geq n_0$.
Propriété
On énonce clairement $P(n)$, avec le rang de départ $n_0$.
Initialisation
On calcule (ou on vérifie) $P(n_0)$. Une phrase ne suffit pas : il faut un vrai contrôle.
Hérédité
On suppose $P(k)$ vraie pour un entier $k \geq n_0$ (hypothèse de récurrence), puis on démontre $P(k+1)$.
Conclusion
« D’après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \geq n_0$. »
Étape 1 : énoncer clairement $P(n)$ et fixer le rang de départ $n_0$.
Étape 2 : vérifier $P(n_0)$ par un vrai calcul, pas juste une affirmation.
Étape 3 : supposer $P(k)$, puis démontrer $P(k+1)$.
La conclusion n’est pas un quatrième calcul : c’est le moment où l’on invoque le principe de récurrence. Les deux étapes précédentes sont toutes les deux indispensables.
Ce que donnent l’initialisation et l’hérédité
L’initialisation montre que $P(n_0)$ est vraie : le premier domino tombe.
L’hérédité montre que, pour tout entier $k \geq n_0$, si $P(k)$ est vraie alors $P(k+1)$ l’est aussi : chaque domino entraîne le suivant.
Ce qu’on écrit
« L’initialisation et l’hérédité sont établies. D’après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \geq n_0$. »
Pourquoi ça marche
$P(n_0)$ est vraie ; l’hérédité donne $P(n_0+1)$ ; puis $P(n_0+2)$ ; et ainsi de suite. On « remplit » ainsi tous les entiers à partir de $n_0$. Sans initialisation, l’hérédité ne démarre pas ; sans hérédité, on ne passe pas d’un rang au suivant.
Montrer que pour tout entier $n \geq 1$,
$1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.
1. Propriété
Pour $n \geq 1$, on pose $P(n)$ : « $1+2+\cdots+n = \dfrac{n(n+1)}{2}$ ».
2. Initialisation
Pour $n=1$ : à gauche, $1$. À droite, $\dfrac{1\times 2}{2}=1$. Donc $P(1)$ est vraie.
3. Hérédité
Soit $k \geq 1$. On suppose $P(k)$ : $1+\cdots+k = \dfrac{k(k+1)}{2}$.
Alors
$1+\cdots+k+(k+1) = \dfrac{k(k+1)}{2} + (k+1) = (k+1)\left(\dfrac{k}{2}+1\right) = (k+1)\dfrac{k+2}{2} = \dfrac{(k+1)(k+2)}{2}$.
C’est exactement $P(k+1)$.
4. Conclusion
D’après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \geq 1$.
Vidéo à venir
Rédaction complète de la somme des $n$ premiers entiers, au tableau.
Soit $(u_n)$ définie par $u_0 = 1$ et $u_{n+1} = 2u_n + 1$. Montrer que pour tout $n \geq 0$,
$u_n = 2^{n+1} - 1$.
Init. $u_0 = 1$ et $2^{1}-1 = 1$. OK.
Hérédité. On suppose $u_k = 2^{k+1}-1$. Alors
$u_{k+1} = 2u_k + 1 = 2(2^{k+1}-1)+1 = 2^{k+2} - 2 + 1 = 2^{k+2} - 1$.
C’est la formule au rang $k+1$. On conclut par récurrence.
Astuce : on « injecte » l’hypothèse de récurrence dans la relation $u_{k+1}=\ldots$, on ne recommence pas le calcul depuis $u_0$.
Oublier l’initialisation. L’hérédité toute seule ne prouve rien : une file de dominos qui ne commence pas ne tombe pas.
Confondre $n$ et $k$. L’hypothèse porte sur un entier fixé $k$, pas « pour tout $n$ » au milieu de l’hérédité.
Conclure trop tôt. On n’écrit la phrase magique qu’après avoir réellement montré $P(k+1)$.
Mauvais rang de départ. Si $P(n)$ commence à $n=2$, on initialise à $2$, pas à $0$.