Home

2BAC SM Maroc

Maths SM&SP

Analyse

Récurrence

La démonstration par récurrence est une technique de preuve mathématique utilisée pour prouver qu'une propriété est vraie pour une séquence infinie de nombres. Dans cet exemple, nous devons montrer par récurrence que la suite Un est strictement décroissante. 

Pour commencer, nous définissons la propriété P2n, qui est vraie pour le rang n. Dans ce cas, nous devons montrer que Un+1 est plus petit que Un. Nous voulons prouver que P2n est vrai pour tous les rangs naturels n. 

Nous commençons par l'initialisation en calculant U1 et U0 pour n=0. Dans cet exemple, U1 est égal à -2 et U0 est égal à 2, ce qui est correct. 

Ensuite, nous passons à l'hérédité. Nous supposons que l'hypothèse de récurrence, c'est-à-dire que Un+1 est plus petit que Un, est vraie pour le rang n. Nous voulons montrer que Pn+1 est vrai. 

Nous utilisons la relation de récurrence Un+1 = 2Un - 6 pour montrer que Un+2 est plus petit que Un+1. Pour simplifier cette démonstration, nous définissons la fonction f(x) = 2x - 6, qui est une fonction affine strictement croissante. 

Puisque Un+1 est plus petit que Un, nous composons cette relation par la fonction f. Ainsi, nous obtenons Un+2 qui est également plus petit que Un+1. 

En conclu

La démonstration par récurrence, alors ça c'est quelque chose qu'il faut savoir maîtriser sur le bout des doigts, au moins sur la rédaction, parce que sinon c'est des points bêtement perdus, et ici je vais vous donner quelques petites astuces pour essayer d'avoir le maximum d'outils pour prouver l'hérédité, qui est évidemment la partie la plus compliquée de cette démonstration par récurrence. On va prendre un exemple, donc ici on a une suite, on a U0 qui est défini par U0 égale 2, et Un plus 1 égale 2 Un moins 6. Donc ce qu'on nous demande c'est de montrer par récurrence que la suite est strictement décroissante. Donc dans la démonstration par récurrence, premier point, on définit P2n, la propriété qui est vraie au rang n. Là pour montrer qu'elle est décroissante strictement, je sais que ce que je vais devoir montrer c'est que Un plus 1 est plus petit qu'Un. Et ce que je dis c'est que je veux montrer que P2n est vraie pour tout n antinaturel. Alors attention, on ne met pas le pour tout n dans la propriété de récurrence, dans P2n. Pourquoi ? Parce que P2n c'est la propriété qui est vraie au rang n seulement. Alors si dedans on met pour tout n, ça n'a plus de sens. Donc c'est une propriété qui est au rang n, et on veut montrer que c'est vrai pour tout rang. Petite erreur des fois qu'on peut voir. Alors on commence par l'initialisation, ça souvent c'est très facile. Faites attention quand même à ne pas se tromper, ici on veut montrer que c'est pour tout n antinaturel. Donc on peut commencer à U0 pour n égale 0, donc on va calculer U1 et U0. Mais faites attention, des fois la propriété n'est vraie qu'à partir du rang 1, etc. Donc il faut quand même faire attention, même si ce n'est pas très compliqué, de ne pas se tromper sur le premier rang. Donc là ici je fais calcul, ça fait U1 égale moins 2, à comparer avec U0 égale 2, c'est bon. L'initialisation est bonne. Ensuite pour l'hérédité. Moi ce que je vous invite à faire très fortement, c'est d'écrire vraiment, l'avoir sous les yeux. Parce que ça aide ce qu'on suppose, c'est à dire que l'hypothèse de récurrence, ma propriété est vraie au rang n. Et ce qu'on veut montrer, que Pn plus 1 est vrai. Et l'explicité, c'est hyper important, parce que quand on le voit sous les yeux, c'est beaucoup plus facile à montrer. Alors là l'exemple n'est pas très compliqué, mais je vous montre comment il faut faire pour que ce soit plus simple pour les hérédités compliquées. Alors là je montre ce que je sais, c'est à dire ce que j'ai supposé, c'est que Un plus 1 est plus petit que Un. Et ce que je veux montrer, c'est que Un plus 2 est plus petit qu'Un plus 1. Donc forcément, vu que c'est une démonstration par récurrence, c'est de l'un en un lien. Il faut que grâce à l'hypothèse de récurrence, je montre celui-là. Si je ne me sers pas de l'hypothèse de récurrence, c'est que je n'avais pas besoin de montrer le résultat par récurrence. Parce que c'est ça la puissance de la démonstration par récurrence, c'est que je me sers d'une hypothèse au rang inférieur. Donc là, évidemment, je pars de là. J'ai Un plus 1 inférieur à Un. Et je vois qu'à partir de ça, il faut que j'aboutisse à Un plus 2. Evidemment, Un plus 2, comment je le construis ? C'est avec l'hypothèse de récurrence. La relation de récurrence, pardon. Un plus 2, ça fait 2 Un plus 1 moins 6. Alors là, c'est là où j'ai l'idée de poser la fonction f qui, à x, associe 2x moins 6. Moi, ce que j'aimerais savoir, c'est le sens de variation de cette fonction. F, c'est une fonction affine qui est de coefficient directeur qui est positive. Donc elle est strictement croissante. Et donc, les relations sur les antécédents vont, par cette fonction, une relation d'infériorité va toujours être vraie si je compose par f. Moi, ce que je sais, c'est qu'Un plus 1 est plus petit qu'Un. Je compose par f, et comme Un plus 2, c'est égal à f de Un plus 1, et Un plus 1, c'est égal à f de Un, avec le f que j'ai posé, je peux composer par f, qui est strictement croissante. Et donc, je me retrouve avec Un plus 2, qui est plus petit qu'Un plus 1. Il y a un plus 1 qui manque ici. Donc là, j'ai démontré l'hérédité rigoureusement. Donc, d'après le principe de récurrence, j'ai bien montré que, pour toute n, anti-naturel, Un plus 1 supérieur à Un, c'est-à-dire ma suite est strictement décroissante. Alors, c'est toujours bien, un petit point de rigueur, Un avec des parenthèses, c'est bien l'objet suite. Donc on peut dire que cet objet est strictement décroissant. Alors que si, des fois on le voit, mais ce n'est pas idéal, si on enlève les parenthèses, il y a un peu confusion. Est-ce que Un, c'est la valeur de la suite au rang n ? Dans ce cas-là, c'est un réel. Ou est-ce que c'est l'objet suite ? Et évidemment, on ne peut pas dire qu'un réel est décroissant. Pour les fonctions, c'est quelque chose où il n'y a pas d'ambiguïté. Il ne faut surtout pas dire que f de x est strictement décroissante. Ça, non. F de x, c'est un réel. C'est f qui est strictement décroissante. Pour Un, c'est pareil. Un tout court, c'est le réel. Et Un, c'est l'objet suite. Chaque fois que vous parlez de la suite, c'est mieux de mettre des parenthèses. Voilà pour cette méthode sur la démonstration par référence.

Récurrence et croissance

RELATED

Recommended videos

Introduction à la récurrence

Concept et rédaction

Pourquoi l'initialisation ?