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$.
Vidéo à venir
Les 4 étapes de la récurrence, en version commentée.
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$. »
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$.