Rédiger une récurrence : méthode (MPSI)
Rédiger une récurrence
- Énoncé. Écrire explicitement : « Pour tout $n\geq n_0$, notons $P(n)$ l'assertion : … ». L'assertion $P(n)$ porte sur un entier $n$ fixé ; elle ne contient pas « pour tout $n$ ».
- Initialisation. Vérifier $P(n_0)$ par un calcul explicite.
- Hérédité. Écrire « Soit $n\geq n_0$ tel que $P(n)$ soit vraie. Montrons $P(n+1)$. » puis utiliser $P(n)$ en le signalant.
- Conclusion. « Par récurrence, $P(n)$ est vraie pour tout $n\geq n_0$. »
Somme des carrés
Pour $n\in\mathbb{N}^*$, notons $P(n)$ : $\displaystyle\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$.
Initialisation. Pour $n=1$ : $\sum_{k=1}^{1}k^2=1$ et $\dfrac{1\times 2\times 3}{6}=1$. Donc $P(1)$ est vraie.
Hérédité. Soit $n\geq 1$ tel que $P(n)$ soit vraie. Alors $$\begin{aligned}\sum_{k=1}^{n+1}k^2&=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\frac{(n+1)\big(n(2n+1)+6(n+1)\big)}{6}\\&=\frac{(n+1)(2n^2+7n+6)}{6}=\frac{(n+1)(n+2)(2n+3)}{6}.\end{aligned}$$ C'est exactement $P(n+1)$, puisque $2(n+1)+1=2n+3$.
Conclusion. Par récurrence, $P(n)$ est vraie pour tout $n\geq 1$.
L'hérédité doit valoir pour tous les $n\geq n_0$
Fausse preuve classique : « dans tout groupe de $n\geq 1$ chevaux, tous ont la même couleur ». L'initialisation $n=1$ est vraie. Pour l'hérédité, on retire d'un groupe de $n+1$ chevaux le premier, puis le dernier : deux groupes de $n$ chevaux unicolores, qui « se chevauchent », donc tout le groupe serait unicolore.
L'erreur : pour $n=1$, les deux groupes d'un cheval n'ont aucun cheval en commun. L'implication $P(1)\Rightarrow P(2)$ n'est pas démontrée, et toute la chaîne s'effondre. Il faut toujours vérifier que l'argument d'hérédité fonctionne dès $n=n_0$.
S’entraîner
- Deux raisonnements par contraposée
- Irrationalités par l'absurde
- Deux équations fonctionnelles par analyse-synthèse
- Comparer $2^n$ et $n^2$
- Suites récurrentes d'ordre 2