Raisonnement par récurrence
En bref : Le raisonnement par récurrence démontre qu’une propriété dépendant d’un entier n est vraie pour tout n : elle l’est au premier rang, et chaque rang vrai entraîne le suivant.
TerminaleSuites
Définition : Raisonnement par récurrence
Le raisonnement par récurrence fonctionne comme une rangée de dominos : si le premier tombe et si chaque domino qui tombe fait tomber le suivant, alors tous tombent.
Pour une propriété \(P(n)\), il se déroule en trois temps. L’initialisation vérifie \(P\) au premier rang \(n_0\). L’hérédité démontre que, pour un entier \(n\ge n_0\) quelconque, \(P(n)\) vraie entraîne \(P(n+1)\) vraie. La conclusion affirme alors \(P(n)\) pour tout \(n\ge n_0\).
Comment le reconnaître
- L’énoncé demande de « démontrer que, pour tout entier \(n\), … » une formule ou une inégalité.
- Une suite est définie par récurrence et l’on veut une formule explicite ou un encadrement.
- L’égalité à prouver contient \(n\) et semble vraie sur les premiers rangs, mais sans preuve générale.
- Il faut montrer qu’un nombre est divisible par un autre pour toutes les valeurs de \(n\).
La méthode
- Énoncer clairement la propriété \(P(n)\) à démontrer.
- Initialisation : calculer les deux membres au premier rang et constater qu’ils coïncident.
- Hérédité : supposer \(P(n)\) vraie pour un \(n\) fixé, puis démontrer \(P(n+1)\) en utilisant cette hypothèse.
- Conclure en citant le principe : \(P(n)\) est vraie pour tout entier \(n\ge n_0\).
Raisonnement par récurrence : exemple corrigé
Énoncé
Soit la suite définie par \(u_0=1\) et \(u_{n+1}=2u_n+1\). Démontrer par récurrence que, pour tout entier \(n\), \(u_n=2^{n+1}-1\).
Corrigé
Initialisation : pour \(n=0\), \(u_0=1\) et \(2^{1}-1=1\) : la propriété est vraie.
Hérédité : supposons \(u_n=2^{n+1}-1\) pour un entier \(n\). Alors \(u_{n+1}=2(2^{n+1}-1)+1=2^{n+2}-2+1=2^{n+2}-1\), ce qui est la propriété au rang \(n+1\).
Conclusion : la propriété est vraie pour tout entier \(n\).
À toi de jouer
Question 1
Pour montrer que \(4^n-1\) est divisible par \(3\), que vérifie l’initialisation ?
Voir la réponse
Au rang \(0\), \(4^0-1=0\), qui est bien un multiple de \(3\).
Question 2
Que suppose-t-on exactement au début de l’hérédité ?
Voir la réponse
Que \(P(n)\) est vraie pour un entier \(n\) fixé quelconque ; on n’en suppose pas la vérité pour tous les \(n\).
Ne pas confondre Raisonnement par récurrence et Suite définie par récurrence
Une suite définie par récurrence est un objet : une suite où chaque terme se calcule à partir du précédent. Le raisonnement par récurrence est une méthode de preuve. On l’emploie souvent pour démontrer une propriété d’une telle suite, mais elle s’applique aussi à des sommes ou des divisibilités.
Pour aller plus loin
Cours
Exercices et QCM
Mots voisins
Tout le glossaire : A–Z · Terminale · Suites
