Raisonnement par récurrence. Comprendre les bases et savoir le rédiger.
Ce que nous allons voir :
Tu vas comprendre rapidement à quoi sert le raisonnement par récurrence et comment il fonctionne.
Le raisonnement par récurrence sert à démontrer qu’une propriété qui dépend d’un entier naturel n (souvent une égalité ou une inégalité) est vraie pour tous les entiers naturels ou pour une partie des entiers naturels.
Le principe est celui des dominos expliqué dans cette vidéo.
Le raisonnement par récurrence se fait en 3 étapes:
-Initialisation,
-Hérédité,
-Conclusion.
Il faut commencer par démontrer que la propriété P(n) est vraie au premier rang, c’est à dire s’assurer que le premier domino va tomber. Il s’agit de la première étape, l’initialisation.
La deuxième étape consiste à démontrer que si la propriété est vraie à un certain rang n, alors elle sera aussi vraie au rang suivant n+1. C’est à dire que si un domino tombe, alors il fait tomber le domino suivant. Il s’agit ici de démontrer une implication mathématique “Si… Alors”. C’est l’étape la plus importante et la plus délicate du raisonnement par récurrence.
La dernière étape est la conclusion. En effet, si la propriété P(n) est vraie au premier rang et qu’elle est héréditaire, alors elle est vraie pour tous les entiers naturels supérieurs ou égaux au premier rang.
De manière imagée, si on s’assure que le premier domino va tomber (Initialisation) et que si un domino tombe, alors il fait tomber le domino suivant (hérédité), alors on est sûr que tous les dominos vont tomber jusqu’à l’infini (c’est la conclusion).
Ce que nous allons voir :
Je vais t’apprendre à rédiger parfaitement un raisonnement par récurrence.
Ici je te donne un squelette de rédaction du raisonnement par récurrence qu’il faudra utiliser dans tous les exercices où tu dois faire une démonstration par récurrence.
Il y’a des choses à réécrire à l’identique et d’autres à changer en fonction de l’exercice.
Ce qui change est clairement identifié par 4 étiquettes :
-La vérification dans l’étape de initialisation.
-L’hypothèse de récurrence notée HR dans l’étape de l’hérédité.
-L’objectif dans l’étape de l’hérédité.
-La démonstration pou montrer l’implication (Si P(n) est vraie à un certain rang n, alors P(n) est vraie au rang suivant n+1)
Tout le reste forme le squelette, rédigé de manière toujours identique, et qui doit être complété par ces quatre étiquettes.
