Raisonnement et démonstration par récurrence - Cours Terminale spécialité maths - suite

Alors, dans cette vidéo, on va expliquer comment démontrer une propriété par récurrence. Alors, la première chose à savoir, c'est qu'on utilise la démonstration par récurrence que si la propriété qu'on veut démontrer dépend d'un entier. Et souvent, dans les exercices, cet entier est noté n. Par exemple, si on vous demande de démontrer que 7 divise 2 puissance 3n-1, et bien, cette propriété, elle dépend d'un entier n. Donc là, vous pouvez envisager de faire une démonstration par récurrence. Mais si on vous demande de démontrer que 7 divise 371, cette propriété, elle ne dépend pas d'un entier, donc c'est même pas la peine ici d'envisager, dans ce deuxième cas, de faire un raisonnement par récurrence. Donc, retenez bien qu'on ne peut faire un raisonnement par récurrence que si la propriété qu'on veut démontrer dépend d'un entier n, comme par exemple cette première propriété. Alors maintenant, pour expliquer comment faire concrètement une démonstration par récurrence, et bien, on va tout simplement traiter un exercice, ce qui rendra les choses beaucoup plus concrètes. Alors, on va traiter l'exercice suivant. On va démontrer par récurrence que pour tout entier n supérieur ou égal à 1, la somme de 1 jusqu'à n, elle est égale à n, n plus 1 sur 2. Alors, avant de continuer, je fais remarquer au passage que cette propriété qu'on va démontrer, elle dépend bien d'un entier n, et donc, il est naturel de penser à faire un raisonnement par récurrence. Alors, la première chose à faire avant d'attaquer la démonstration par récurrence, c'est que la propriété qu'on veut démontrer, c'est-à-dire celle-ci, qui est ici, cette propriété, on va l'appeler P, indices n. Et donc, je commence toujours ma rédaction sur ma copie de la manière suivante, soit Pn, deux points, la propriété que je veux montrer, c'est-à-dire celle-ci que j'ai réécrite ici. Alors, une fois qu'on a écrit ceci, la démonstration par récurrence, elle se déroule toujours en trois étapes. Premièrement, l'initialisation, on verra ce que c'est. Deuxièmement, l'hérédité, et enfin, la conclusion. Alors, l'initialisation, c'est quoi ? C'est le fait de vérifier que cette propriété qu'on veut démontrer, qu'on a appelée Pn, elle est vraie pour une certaine valeur de n, la plus petite possible. Et comme on veut démontrer cette propriété pour n supérieur ou égal à 1, la plus petite valeur possible pour n, c'est 1. Donc en fait, on va vérifier que cette propriété est vraie au rang 1. C'est-à-dire qu'on va remplacer ici partout n par 1, et voir si c'est vrai. Et donc j'écris, vérifions que P1 est vrai. Et je répète, pour savoir si P1 est vrai, je vais tout simplement remplacer n par 1 partout ici, et regarder si c'est vrai, c'est-à-dire si la partie gauche est bien égale à la partie droite. Alors si je remplace n par 1, ici ça me fait la somme de 1 jusqu'à n, c'est-à-dire la somme de 1 à 1, c'est-à-dire qu'il n'y a qu'un seul terme, c'est 1. Et la partie droite, elle est égale à quoi ? Elle est égale, je remplace n par 1, ça fait 1 fois 1 plus 1, c'est-à-dire 2, sur 2. Et si on simplifie par 2, ça c'est P1 qui affirme ça, et ça c'est vrai, parce que la partie droite, si je simplifie par 2, il reste 1. Donc j'obtiens bien 1 égale 1. Donc on peut écrire, donc P1 est vrai. Et ça termine la première étape, l'initialisation. Alors maintenant, pour expliquer l'hérédité et le principe de récurrence, je vais faire une analogie avec des dominos. Alors voilà, j'ai représenté ici des dominos. Le premier domino correspond à la propriété au rang 0, mais moi elle ne commence qu'à partir du rang 1. Le deuxième domino correspond à la propriété au rang 1, le troisième au rang 2, etc. Et moi j'ai démontré que la propriété était vraie au rang 1, et donc je fais un petit point ici pour indiquer que cette propriété-là, eh bien j'ai démontré qu'elle était vraie au rang 1. Alors comment j'ai fait ? Je répète, j'ai tout simplement remplacé n par 1 pour voir si c'est vrai. Je pourrais recommencer et remplacer n par 2 pour voir si cette égalité est encore vraie au rang 2. Et ça me permettra de démontrer que P2 est vraie. Et pareil, je pourrais recommencer et remplacer n par 3. Mais vous comprenez bien qu'on ne peut pas remplacer n par toutes les valeurs possibles. Donc il va falloir procéder autrement. Et l'analogie qu'on va faire, c'est que si la propriété est vraie par exemple au rang 1, eh bien ça va faire tomber ce domino. Et donc la question qu'on va se poser, c'est que, est-ce que ce domino en tombant, il va faire tomber le prochain domino ? Et donc la question plus générale qu'on va se poser, c'est qu'on va supposer que la propriété est vraie au rang n, c'est-à-dire on va supposer Pn vraie, et donc on va supposer que ce domino va tomber, et on va se poser la question, est-ce qu'il va entraîner la chute du prochain domino ? Autrement dit, est-ce que ça va entraîner que Pn plus 1 est vrai ? Et si c'est le cas, on dira que la propriété est héréditaire. Ça veut dire que si Pn est vrai, eh bien elle est encore vraie au rang d'après. Ça veut dire que cette propriété, elle se transmet et donc elle est héréditaire. Et quel est l'intérêt de savoir qu'une propriété est héréditaire ? Je rappelle que héréditaire, ça veut dire que la propriété se transmet au rang d'après. Eh bien comme P1 est vrai, ce domino-là va tomber. Et donc si la propriété est héréditaire, eh bien il va entraîner la chute du domino suivant. Et lui-même, ce domino, comme il va tomber, il va entraîner la chute du domino suivant. Et ainsi de suite. Et donc si on a initialisé, c'est-à-dire si on a vérifié que la propriété est vraie au rang 1, et que la propriété est héréditaire, c'est-à-dire qu'elle se transmet de proche en proche, eh bien tous les dominos vont tomber. Et donc ça prouvera que cette propriété, elle est vraie à partir de ce domino-là, c'est-à-dire à partir du rang 1. Donc si on récapitule ce qu'on vient de dire, qu'est-ce qu'il faut faire ? Il faut montrer que si la propriété est vraie au rang n, elle est encore vraie au rang d'après. Et maintenant, il n'y a plus qu'à l'écrire sur sa copie. Et donc on écrit, on rédige toujours de la même façon, on écrit soit 1 entier, j'insiste bien 1, je l'ai souligné, soit 1 entier n supérieur ou égal à 1. Pourquoi supérieur ou égal à 1 ? Parce que cette propriété, on la démontre à partir du rang 1. Supposons Pn vrai, et montrons que ça implique que Pn plus 1 est encore vrai. Voilà comment commence la rédaction de l'hérédité. Ça veut dire quoi, ce qu'on a écrit ? Ça veut dire qu'on a supposé que ceci est vrai au rang n, et on va montrer que ceci est encore vrai au rang n plus 1. Et donc, j'insiste bien, nous ce qu'on veut montrer, c'est que Pn plus 1 est vrai. Et pour bien comprendre ce qu'il faut montrer, on écrit systématiquement sur son brouillon Pn plus 1. Donc ici je vais faire une petite bulle qui correspond à mon brouillon, et je vais écrire Pn plus 1. C'est quoi Pn plus 1 ? Et bien je remplace tout simplement n par n plus 1. Donc ça me donne quoi Pn plus 1 ? C'est la somme de 1 jusqu'à n plus 1. Et d'après cette affirmation, elle est égale à quoi ? Je remplace n par n plus 1, ça me fait n plus 1. Si je remplace n ici par n plus 1, ça me fait donc n plus 2 sur 2. Et donc, je répète encore une fois parce que c'est fondamental, on suppose que Pn est vrai, c'est-à-dire on suppose que ceci est vrai, et il faut montrer que ceci, que Pn, entraîne Pn plus 1. Il faut donc montrer à partir de ceci que cela est vrai. Et donc comment je vais faire ? Comme il faut montrer ceci et que ceci c'est une égalité, et bien je vais partir de la partie gauche, que je vais transformer en utilisant ceci, que j'ai supposé vrai, qu'on appelle l'hypothèse de récurrence, je vais donc transformer ceci en utilisant cela, l'hypothèse de récurrence, pour obtenir la partie droite. Et au lieu d'écrire la somme de 1 jusqu'à n plus 1, comme je veux faire apparaître cela, qu'est-ce que je vais écrire ? Je vais écrire la somme de 1 jusqu'à n plus n plus 1. Pourquoi ? Parce que ceci, c'est cela. Et donc ceci, comme j'ai supposé que cela était vrai, et bien la somme de 1 jusqu'à n, je peux la remplacer par ceci. Et donc ça me donne quoi ? Ça me donne n, n plus 1 sur 2, plus ce dernier terme, n plus 1. Et donc il faut bien comprendre que j'ai remplacé la somme de 1 jusqu'à n par ceci. Et pourquoi j'ai le droit de le faire ? Parce que justement j'ai supposé que Pn est vrai, c'est-à-dire que ceci est vrai, c'est-à-dire que cela égale cela. Et donc j'ai pu remplacer cette somme-là, c'est-à-dire la somme de 1 à n, par ceci. C'est parce que j'ai supposé Pn vrai que j'ai pu remplacer cela par cela. Et maintenant on a presque fini, il ne faut pas perdre de vue qu'on doit démontrer ceci, c'est-à-dire qu'on doit partir de la partie gauche pour obtenir la partie droite. On est bien parti de la partie gauche, on a obtenu ceci, et maintenant il faut arriver à cela. Et vous voyez qu'ici on a n plus 1 en facteur. Ça tombe bien, ici on a n plus 1, ici on a encore n plus 1, on peut rajouter des parenthèses, ça ne change rien. Et donc je vais mettre ici n plus 1 en facteur pour faire ressembler, pour arriver à ceci. Alors je mets n plus 1 en facteur, et qu'est-ce qu'il me reste ? Et bien si je mets n plus 1 en facteur ici, il me reste n sur 2, plus 1. Et maintenant il n'y a plus qu'à arranger. Alors si ici on met au même déminateur, c'est-à-dire qu'on met tout sur 2, qu'est-ce qu'il reste ? Le premier bloc je n'y touche pas, ça fait n plus 1, et ici ça me fait n plus 2 sur 2. Autrement dit, exactement n plus 1 en facteur de n plus 2 le tout sur 2, c'est-à-dire exactement la partie droite. Donc on est bien parti de la partie gauche pour obtenir la partie droite. Donc on a bien démontré que Pn plus 1 est vrai, ce qui termine l'hérédité. Et donc je n'oublie pas d'écrire sur ma copie, donc Pn plus 1 est vrai. Alors je récapitule l'hérédité parce que c'est la partie la plus difficile. Je répète ce que c'est que l'hérédité, c'est qu'on suppose que Pn est vrai, et on va montrer que ça implique que Pn plus 1 est encore vrai. C'est ce qu'on a écrit ici au début de la rédaction. Et donc pour réussir cette hérédité, la première chose à faire c'est d'écrire sur son brouillon ce que c'est que Pn plus 1, c'est ce que j'ai fait ici. Et si vous ne le faites pas, ce sera beaucoup plus difficile. Parce que regardez, comme j'ai écrit ceci, ça m'a donné l'idée de comment commencer. C'est en ayant écrit ça sur mon brouillon que j'ai eu l'idée qu'il fallait que je transforme cette somme de 1 jusqu'à n plus 1. C'est pour ça que j'ai écrit cette somme de 1 jusqu'à n plus 1, et je l'ai transformée jusqu'à obtenir la partie droite. Et je répète, si vous n'écrivez pas Pn plus 1 sur votre brouillon, vous aurez sans doute des difficultés pour savoir comment commencer l'hérédité. Alors une fois qu'on a fait l'initialisation et l'hérédité, il n'y a plus qu'à conclure. Et on rédige toujours de la même façon. Alors je récapitule ce qu'on a fait, on a démontré que ce domino tombe, c'est ce qu'on a fait à l'initialisation, et on a démontré lors de l'hérédité que si un domino tombe, il entraîne la chute du suivant. Donc concrètement, ça veut dire que comme ce domino va tomber, d'après l'hérédité, il va entraîner la chute du suivant. Et comme celui-là va tomber, là encore d'après l'hérédité, il va entraîner la chute du suivant, et ainsi de suite. Et donc tous les dominos vont tomber à partir du rang 1. C'est pour ça que cette propriété Pn, on leur a donc démontré à partir du rang 1, c'est ce qu'il fallait faire, et donc maintenant il n'y a plus qu'à le rédiger sur sa copie. Et donc on écrit que P1 est vrai, c'est l'initialisation, et que Pn est héréditaire à partir du rang 1, c'est ce qu'on a fait dans l'hérédité. Et donc on en déduit par récurrence que cette propriété Pn, elle est vraie pour tout entier n supérieur ou égal à 1. Donc on a bien démontré cette propriété pour tout entier n supérieur ou égal à 1. Voilà qui termine cette démonstration par récurrence. Alors avant de terminer, j'aimerais insister sur une erreur qu'on rencontre de temps en temps et qui est grave. Il y a certains élèves qui dans l'hérédité écrivent « supposons que Pn est vrai quel que soit n ». Mais si vous supposez que Pn est vrai quel que soit n, et bien il n'y a plus rien à démontrer. Nous on n'a pas supposé que Pn est vrai quel que soit n, on a supposé que Pn est vrai pour un certain entier n, et on a montré que ça entraînait que Pn plus 1 est vrai. Donc surtout, n'écrivez pas « supposons que Pn est vrai quel que soit n » parce que c'est complètement faux. Dernier point, toutes les récurrences se rédigent exactement de la même façon. Elles se rédigent exactement comme je l'ai fait pour traiter cet exercice. Donc c'est extrêmement important que vous connaissiez par cœur cette façon de rédiger. Donc voilà, maintenant il ne vous reste plus qu'à vous entraîner en faisant des exercices.