Table des matières
Au lycée et plus précisément en Terminale, on apprend le fameux « raisonnement par récurrence » pour démontrer des propriétés (ou proposition) avec du n (où n est un entier naturel).
Ce raisonnement se fait en 3 étapes et à la fin la propriété est vraie, mais on ne comprend pas tout à fait ce qu’on a prouvé et pourquoi les 3 étapes font que ça marche. C’est ce qu’on va voir dans cet article!
Si vous préférez regarder une vidéo expliquant tout cela plutôt que de lire l'article, j'ai fait une vidéo expliquant le raisonnement par récurrence simple ainsi que des exemples
Quand peut-on utiliser le raisonnement par récurrence?
En mathématiques on cherche souvent à montrer des propriétés (c'est à dire montrer qu'elles sont vraies).
Il existe beaucoup de raisonnements différents pour montrer des propriétés, et le raisonnement par récurrence en est un.
Le raisonnement par récurrence s’applique à des situations où l’on cherche à démontrer la véracité d’une propriété P(n) pour tout entier naturel n.
Le raisonnement par récurrence est souvent utilisé avec les suites.
Par exemple, on peut montrer par récurrence que le terme général d'une suite est supérieur ou égal à un certain entier naturel p.
Ou par exemple, pour montrer que cette propriété est vraie pour tout entier naturel:
En revanche, l' utilisation du raisonnement par récurrence n'est pas possible lorsque la variable de la propriété n'est pas un entier naturel.
Par exemple on ne peut pas utiliser le raisonnement par récurrence pour montrer la propriété : "la fonction f définie sur R par f(x)=3x+9 est croissante"
Comment fonctionne le raisonnement par récurrence simple exactement?
Alors, pour comprendre le raisonnement par récurrence, on va faire une analogie avec des dominos.
Vous savez, les trucs qu’on alignent pour qu’ils tombent en réaction en chaine de façon ultra satisfaisante.
On veut montrer qu'une propriété est vraie et cette propriété va dépendre d’un entier naturel qu'on appelle n généralement.
On note la propriété P(n) en général.
Cette proposition, on va l’associer à un tas infini de dominos, qui sont numérotés avec des entiers naturels du coup.
On continue l’analogie en disant que si notre propriété est vraie pour un certain n, ça veut dire que le domino n° n est tombé.
Par exemple si la propriété est vraie quand n vaut 12, ça veut dire que le domino n°12 est tombé.
Nickel on tout les éléments, maintenant on va voir comment ça marche.
Dans le raisonnement par récurrence, il y a 3 étapes: l' initialisation, l' hérédité et la conclusion.
Nous allons détailler les 3 en commençant par l' hérédité :
L' hérédité:
Alors la version domino de l’ hérédité c’est de voir si les dominos sont bien alignés.
Ça veut dire que si on fait tomber n’importe lequel domino, le suivant tombera aussi, puis le suivant etc...
Donc en gros on va supposer que la propriété est vraie pour un certain n entier naturel, donc ça veut dire on suppose que le domino n° n tombe.
Cette hypothèse qu’on fait, on l’appelle Hypothèse de Récurrence.
Et du coup on va vérifier si la propriété est encore vraie pour l'entier naturel suivant, donc n+1 (on vérifie du coup que le domino d’après, le numéro n+1 tombe aussi).
Une fois que c’est vérifié c’est bien, on a montré que dès que la propriété est vraie pour un entier naturel n, elle sera vraie pour tous ceux d’après, du coup on dit que la propriété est héréditaire.
Comme les dominos, si ils sont bien alignés, t’en fait tomber un et ils vont tous tomber.
Le soucis c’est qu’ils ont beau être alignés, si il y en a aucun qui tombe, bah il ne se passe rien du tout.
Donc si on montre qu’une proposition est héréditaire, bah faut aussi montrer qu’elle est vraie à un moment sinon ça ne sera jamais vrai.
C’est là qu’intervient l’initialisation
Initialisation
L’ initialisation, c’est très simple, on va vérifier que la proposition est vraie pour la plus petite valeur de n possible.
Donc en gros, on vérifie que le premier domino tombe bien.
Et du coup à la fin on conclu en disant que la proposition est vraie pour la plus petite valeur de n puis héréditaire donc elle est toujours vraie.
En gros on fait tomber le premier domino et comme ils sont bien alignés ils vont tous tomber.
C’est pareil pour la propriété, l’hérédité nous dit que si elle est vraie pour un certain entier naturel n (donc si le « domino de cette valeur » tombe), elle est vraie pour l'entier naturel suivant d’après, puis celle d’après etc…
Et donc grâce à l’hérédité, tous les autres dominos tombent, c’est à dire la propriété est vraie pour toutes les valeurs de n possible.
Pour résumer la méthode d'un raisonnement par récurrence pour démontrer que la propriété P(n) est vraie pour tout entier naturel n ou pour tout entier naturel n supérieur ou égal à une certaine valeur :
On effectue l'initialisation, c'est à dire qu'on montre que cette propriété est vraie pour la plus petite valeur de n possible
On effectue l'hérédité, c'est à dire qu'on suppose que la proposition est vraie pour un certain entier naturel n et le but est de montrer qu'elle est vraie pour l'entier suivant n+1.
On conclut en disant que la propriété est vraie pour la plus petite valeur de n possible et qu'elle est qu'on a montré l' hérédité (donc elle est héréditaire), donc la propriété est vraie pour tout entier naturel
Donc avec ce raisonnement, on montre que notre propriété est vraie pour tout entier naturel. Vous ne trouvez pas ça joli? :)
Le raisonnement par récurrence double
On a vu qu'une propriété que l’on démontre par récurrence est une propriété dont la véracité se “propage” d’un entier naturel au suivant (grâce à l'hérédité).
Le principe du raisonnement par récurrence double est de propager la véracité d'une propriété d'un certain entier naturel n, et du suivant n+1 pour montrer que la propriété est vraie pour n+2 et donc pour tous les entiers naturels n
Cette fois-ci, notre hypothèse de récurrence est que la propriété est vraie au rang n et n+1 et le but de l'hérédité est de montrer qu'elle l'est encore au rang n+2.
Dans une récurrence double il faut faire une double initialisation, c'est à dire qu'il faut vérifier que les deux premiers rangs de la proposition sont vrais.
Pour résumer la méthode d'un raisonnement par récurrence double pour démontrer que la propriété P(n) est vraie pour tout entier naturel n ou pour tout entier naturel n supérieur ou égal à une certaine valeur :
On effectue l'initialisation, c'est à dire qu'on montre que cette propriété est vraie pour les deux plus petites valeurs de n possible
On effectue l'hérédité, c'est à dire qu'on suppose que la proposition est vraie pour un certain entier naturel n et on suppose qu'elle est aussi vraie pour le suivant, c'est à dire n+1. Le but alors est de montrer qu'elle est vraie pour l'entier suivant n+2.
On conclut en disant que la propriété est vraie pour les deux plus petites valeurs de n possibles et qu'elle est qu'on a montré l' hérédité (donc elle est héréditaire), donc la propriété est vraie pour tout entier naturel
Par exemple on pourrait montrer par récurrence double la propriété suivante :
Soit la suite définie par
et
Démontrer par récurrence que la suite vérifie :
Le raisonnement par récurrence forte
Comment pour la récurrence double, la récurrence forte ne va pas simplement utiliser lors de l' hérédité le fait que si elle est vraie au rang n alors elle est vraie au rang n+1.
Dans le raisonnement par récurrence forte, dans l' hérédité, on va supposer que la propriété est vraie pour tout entier naturel inférieur ou égal à n, et on va montrer qu'elle est vraie au rang n+1.
En faisant ce principe de récurrence, on montre que la propriété est vraie pour tout entier naturel n.
Pour résumer la méthode d'un raisonnement par récurrence forte, pour démontrer que la propriété P(n) est vraie pour tout entier naturel n ou pour tout entier naturel n supérieur ou égal à une certaine valeur :
On effectue l'initialisation, c'est à dire qu'on montre que cette propriété est vraie pour la plus petite valeur de n possible
On effectue l'hérédité, c'est à dire qu'on suppose que la proposition est vraie pour tout entier naturel inférieur ou égal à n et le but est de montrer qu'elle est vraie pour l'entier suivant n+1.
On conclut en disant que la propriété est vraie pour la plus petite valeur de n possible et qu'elle est qu'on a montré l' hérédité (donc elle est héréditaire), donc la propriété est vraie pour tout entier naturel
On utilise le raisonnement par récurrence forte souvent lorsque l'on a des suites définies avec des sommes. Par exemple :
Soit la suite définie par
et
Montrer par récurrence que pour tout entier naturel n supérieur ou égal à 1,
