QCM : Raisonnement par récurrence (Terminale)
Le raisonnement par récurrence permet de démontrer qu'une propriété est vraie pour tous les entiers naturels à partir d'un certain rang, alors qu'on ne peut pas vérifier une infinité de cas un par un. On s'en sert pour les suites définies par récurrence, pour les inégalités et pour les formules de sommes.
Dans une démonstration par récurrence, que démontre-t-on exactement lors de l'étape d'hérédité ?
L'hérédité est une implication $P(n)\Rightarrow P(n+1)$ valable pour tout $n\geq n_0$. Elle n'affirme pas que $P(n)$ est vraie : c'est la conclusion, obtenue en combinant hérédité et initialisation. Le piège principal consiste à confondre l'hérédité avec la conclusion. Le sens inverse $P(n+1)\Rightarrow P(n)$ ne fait pas avancer les dominos.
Quelle phrase commence correctement l'hérédité d'une récurrence sur $n\in\mathbb{N}$ ?
On fixe un entier $n$ et on suppose $P(n)$ vraie pour ce seul entier : c'est l'hypothèse de récurrence. Supposer $P(n)$ « pour tout $n$ » revient à supposer ce qu'on veut démontrer : c'est l'erreur la plus fréquente. Partir de $P(n+1)$ démontre l'implication dans le mauvais sens, et vérifier quelques cas ne prouve rien.
Soit $(u_n)$ définie par $u_0=2$ et $u_{n+1}=3u_n-2$. On veut démontrer par récurrence que $u_n=3^n+1$ pour tout $n\in\mathbb{N}$. Dans l'hérédité, quel est le but à atteindre ?
Le but est $P(n+1)$ : on remplace $n$ par $n+1$ partout, ce qui donne $u_{n+1}=3^{n+1}+1$. On l'obtient par $u_{n+1}=3(3^n+1)-2=3^{n+1}+1$. Le piège principal est d'ajouter $1$ à toute l'expression au lieu de remplacer $n$ par $n+1$ dans l'exposant. La réponse « pour tout $n$ » est la conclusion, pas le but de l'hérédité.
Dans la démonstration de l'inégalité de Bernoulli $(1+a)^n\geq 1+na$ pour $a\geq 0$, on multiplie l'hypothèse de récurrence par $1+a$. Pourquoi le sens de l'inégalité est-il conservé ?
Multiplier une inégalité par un nombre positif conserve son sens : ici le facteur est $1+a$, strictement positif car $a\geq 0$. L'argument $na^2\geq 0$ sert à une autre étape, pour comparer $(1+na)(1+a)=1+(n+1)a+na^2$ à $1+(n+1)a$. Le piège consiste à confondre les deux justifications de la démonstration.
On démontre par récurrence que $\sum_{k=1}^{n}(2k-1)=n^2$ pour tout $n\geq 1$. Quel terme ajoute-t-on à la somme pour passer du rang $n$ au rang $n+1$ ?
Le terme ajouté est le terme général pris en $k=n+1$ : $2(n+1)-1=2n+1$. On obtient alors $n^2+2n+1=(n+1)^2$. L'erreur classique est d'écrire $2n-1$, qui est le dernier terme de la somme au rang $n$, déjà compté. La réponse $n+1$ vient de la somme des entiers, qui n'est pas celle étudiée ici.
On veut démontrer par récurrence que $2^n\geq n^2$ pour tout entier $n\geq n_0$. Quel est le plus petit rang $n_0$ qui convient ?
On a $2^3=8<9=3^2$ : la propriété est fausse en $n=3$, donc aucun $n_0\leq 3$ ne convient. En $n=4$, $2^4=16=4^2$, et l'hérédité fonctionne pour $n\geq 4$ car $(n-1)^2-2>0$. Le piège est de choisir $0$ parce que la propriété est vraie pour $n=0,1,2$ : elle ne l'est pas pour tous les entiers à partir de $0$.
On note $P(n)$ : « $10^n+1$ est divisible par $9$ ». On démontre que, pour tout $n\in\mathbb{N}$, $P(n)\Rightarrow P(n+1)$. Que peut-on en conclure ?
Sans initialisation, l'hérédité ne prouve rien : aucun domino ne tombe. Ici $10^0+1=2$ n'est pas divisible par $9$, et pour $n\geq 1$ la somme des chiffres de $10^n+1$ vaut $2$, donc $P(n)$ est toujours fausse. Le piège est de croire qu'une hérédité réussie suffit à valider la propriété.
Soit $(u_n)$ définie par $u_0=4$ et $u_{n+1}=f(u_n)$ avec $f(x)=0{,}5x+1$. La fonction $f$ est croissante sur $\mathbb{R}$. Quelle affirmation est juste ?
On calcule $u_1=0{,}5\times 4+1=3\leq u_0$. Si $u_{n+1}\leq u_n$, comme $f$ est croissante, $f(u_{n+1})\leq f(u_n)$, soit $u_{n+2}\leq u_{n+1}$. La suite est donc décroissante. Le piège principal est de croire que $f$ croissante entraîne $(u_n)$ croissante : c'est la comparaison de $u_0$ et $u_1$ qui décide.
On démontre par récurrence que $S_n=\sum_{k=1}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}$. Dans l'hérédité, après utilisation de l'hypothèse de récurrence, que vaut $S_{n+1}$ ?
On écrit $S_{n+1}=S_n+(n+1)^2$, puis on remplace $S_n$ par $\dfrac{n(n+1)(2n+1)}{6}$ grâce à l'hypothèse de récurrence. Ajouter $n^2$ revient à recompter le dernier terme du rang $n$. Le dernier choix utilise la formule au rang $n+1$, c'est-à-dire le but, avant de l'avoir démontré : on suppose ce qu'on veut prouver.
Dans une hérédité, on dispose de l'hypothèse $u_n\leq 4$. Qu'en déduit-on pour $-2u_n+1$ ?
En multipliant $u_n\leq 4$ par $-2<0$, on renverse l'inégalité : $-2u_n\geq -8$. En ajoutant $1$ : $-2u_n+1\geq -7$. Le piège principal est d'oublier de changer le sens de l'inégalité, ce qui donne $-2u_n+1\leq -7$. Les valeurs $9$ viennent d'une erreur de signe sur $-2\times 4$.