Home

MPSI/PCSI

Révisions Maths lycée

Analyse Terminale

Récurrence

Ce cours porte sur une proposition mathématique et la démonstration de sa validité. L'exercice utilise le principe de récurrence pour montrer que si la propriété est vraie pour un certain rang n, alors elle est également vraie pour le rang suivant n+1. L'accent est mis sur l'importance de bien comprendre l'énoncé et de ne pas surinterpréter les informations fournies. L'exercice montre également qu'il faut prouver l'initialisation pour être sûr

Stop, j'en ai marre de parler, j'ai envie de faire des maths, donc c'est parti. On commence avec ça. On vous dit pour tout entier, naturel, n appartient à n, on considère la proposition 9 divise 10 puissance n plus 1. Très bien. Question 1. Soit n est anti-naturel, démontrez que si Pn est vrai, alors Pn plus 1 est vrai. Donc un petit 1 ici. Donc là, on reconnaît un truc de récurrence. On se dit, mais attends, ça ressemble à une récurrence. On me dit, démontrez que si j'ai la propriété vraie à un rang n, alors ça implique la vérité en n plus 1. Bon, on me parle pas spécialement de récurrence, on me dit pas démontrer par récurrence. On me dit pas rien, non. Faut pas que je me préoccupe là pour l'instant de... Faut pas que je me préoccupe de l'initialisation. On me dit juste, voilà une proposition, montrez que si elle est vraie, elle implique la prochaine. En fait, on me dit un peu, montrez l'hérédité. Bah, j'y vais aller. Alors là, c'est aussi, alors, premier conseil. Protype numéro 1. Il faut ne pas surinterpréter les énoncés. Le truc en maths, c'est d'être vraiment, de vous transformer en machine. C'est, on vous donne un nombre d'infos, genre a, b, c, il faut utiliser a, b, c pour répondre à la question. Faut pas partir sur a, b, c, d, que vous avez cru comprendre. Typiquement, là, si vous commencez à faire, bah, on va essayer de le montrer pour n égale 0, vous faites quelque chose qui n'est pas demandé. Et en l'occurrence, si vous faites ça, vous allez rater tout le principe de l'exo. Bon, c'est un truc qui est... Moi, je me rappelle quand j'étais toujours en terminale, qui m'a beaucoup frustré, mais cet apprentissage de bien lire l'énoncé, c'est pas juste bien le lire, c'est bien capter l'ensemble des infos qui y sont données et celles qui y sont pas. Et pas aller en inventer. Donc ici, typiquement, il faut surtout pas, ce qui serait un réflexe, je pense. On se dit, super, je reconnais les références. Réflexe, je lance l'initialisation. Là, c'est pas ça qu'il faut faire. On dit, bon, démontrez que celle est vraie, alors que n plus 1 est vrai. Très bien, c'est parti. Alors, soit n tel que... Bon, soit n, voilà, il est introduit, donc je vais pas le réécrire. Si Pn est vrai, alors que n plus 1 est vrai. On va écrire, donc je fais au brouillon en vert à chaque fois. On a... 9 divise, divise, donc la barre verticale, c'est pour dire divise. 10 puissance n plus 1. On veut. Alors, ce on a, on veut, ça va être un truc que je vais répéter tout le temps. Il faut absolument faire on a, on veut, que ça ait la cadrée. Donc j'écris ce que je veux. Moi, je veux le même entier, mais un rang plus loin, donc n plus 1. Quand on écrit on a, on veut, c'est vachement utile, parce que, au moins, quand on commence à partir de là et à faire plein de calculs, des fois, aller voir ce que c'est la conclusion, ça peut nous aider à conclure la dernière étape. Nous rappeler un peu, nous remettre un peu les pieds sur terre. Donc c'est vachement bien de l'écrire comme ça. En vert, c'est le brouillon. Donc moi, j'ai ce truc-là. Partons de l'expression 10 puissance n plus 1 plus 1. Je vais partir de cette expression et me dire, bon, est-ce que, donc il y a pas mal d'exos comme ça, vous verrez, justement, celui-là est intéressant, parce que ça va ressembler un petit peu à l'arithmétique. Donc pour ceux qui font MathExpert, vous aurez le genre de raisonnement que je vais faire là, en MathExpert, en arithmétique, quand vous aurez fini les complexes, ou peut-être que vous allez commencer par l'arithmétique. On va faire un raisonnement, mais il peut être utile dans pas mal de domaines des maths, donc vous faites MathExpert ou pas, ça va vous aider. L'idée, c'est que je vais essayer de faire apparaître ça, ce que je vais appeler l'hypothèse de récurrence, HR, dans l'expression de ça. Je vais essayer d'utiliser ce que je sais ici pour montrer quelque chose sur la ligne numéro 2. Donc, commençons. J'ai 10 puissance n plus 1 plus 1 égale. Moi, j'ai envie de faire apparaître 10 puissance n plus 1, l'hypothèse de récurrence. Vu que j'ai envie de le faire apparaître, je l'écris. Blam ! Comme ça, j'y vais sans pincettes, je l'écris. J'écris absolument 10 puissance n plus 1, comme ça. Ça va me forcer à trouver la manière de rendre l'égalité juste, mais en tout cas, ça m'aide à forcer l'utilisation de l'hypothèse de récurrence. Donc si j'ai ça, qu'est-ce qui manque ? Quand j'écris ça, moi j'ai 10 puissance n, ce qu'il me faudrait c'est un plus 1, donc il faudrait que je fasse fois 10 pour avoir 10 puissance n plus 1. C'est ça qui va me guider vers écrire ça fois 10. Je vais compléter l'égalité à droite pour essayer de trouver ce truc-là, mais dans une expression où j'ai l'hypothèse de récurrence. Au début, je l'écris de force, je ne réfléchis pas, et je me dis qu'est-ce que je peux bidouiller un peu pour essayer de m'approcher de ce truc-là. Quand je fais fois 10 ici, c'est bien 10 fois 10 puissance n qui va me faire 10 puissance n plus 1. Donc ça, c'est très bien. Mais si je développe tout, j'ai aussi 10 fois 1 qui vaut 10. C'est assez chiant parce que je ne veux pas plus 10, je veux plus 1. Ce n'est pas grave, si j'ai plus 10 et que je veux plus 1, tout ce que j'ai à faire c'est compenser. Si là ça fait plus 10, qu'est-ce que je fais ? J'écris moins 9. Et voilà. Juste cette petite astuce, normalement, vous donne accès à la démonstration. La démonstration c'est quoi ? Comme 10 puissance n plus 1, plus 1. Donc ce que j'ai écrit ici. Ça peut s'écrire comme 10 puissance n plus 1 fois 10, moins 9. Et je sais que 9 divise moins 9. Donc je vais l'écrire ici. 9 divise moins 9. Et par hypothèse de récurrence, 9 divise 10 puissance n plus 1. Donc logiquement, comme 9 divise 10 puissance n plus 1, 9 divise aussi 10 fois 10 puissance n plus 1. Et comme il divise moins 9, il divise en fait le tout. Vu qu'il divise le premier bloc, donc celui-là, on sait que 9 divise ça, donc ça, si vous voulez, ça s'écrit genre 9 fois Q, si j'appelle Q un antiquelconque. Comme 9 divise ça, et 9 divise moins 9, évidemment, ça veut dire que 9 divise le tout. Et donc ma démonstration, c'est ça. C'est juste pour redire, comme j'ai trouvé une écriture de 10 puissance n plus 1, plus 1, le truc que je veux, j'ai trouvé une écriture qui utilise l'écriture de ce que je sais, c'est-à-dire l'hypothèse de récurrence, et qu'il se trouve que le bloc en plus qui compense un peu est trivialement divisible par 9, parce que c'est moins 9. Dans ce cas, je peux conclure tout de suite. Je peux dire ça, qui est bien égal à 10 puissance n plus 1, plus 1. Alors là, vous allez me dire, ça fait un peu brouillon ton truc. Ce qu'on pourrait faire pour une copie parfaite, c'est, excusez-moi, pour une copie parfaite, ça serait dire, c'est un peu la, c'est recopier ce que j'ai écrit en rouge, et dire comme 9 divise 10 puissance n plus 1, par hypothèse de récurrence, et 9 divise moins 9, par bon sens, alors 9 divise 10 fois 10 puissance n plus 1, moins 9, égale ça. Et on pourrait dire que tout ça, en fait, c'est aussi au brouillon. Je vais mettre ça en l'air, hop, au brouillon. Ça, ça serait ma rédaction, un peu, que je balance comme ça, alors ça fait un peu la rédaction de, si vous l'écrivez comme ça direct, vous vous dites, mais d'où ça sort ? La rédaction de prof, vous savez, il sort le truc, on ne comprend pas. Voilà, derrière, vous avez les coulisses qui sont là. C'est pas ça que je voulais faire. Vous avez les coulisses qui sont là, c'est-à-dire, posez toujours ce qu'on a et ce qu'on veut. Là, je vous donne l'astuce qui est vraiment le cœur de cet exercice, qui est en gros cette écriture, c'est de décrire l'expression en fonction de l'hypothèse de récurrence, et boum, ça vous fait les démonstrations. Ok, très bien. Donc ça, c'est la question 1, c'est fini, c'est QFD, on est bon. Petit 2, on vous dit quoi ? Petit 2, montrer, est-ce que la proposition est vraie pour tout antinaturel n ? Et là, on sent qu'il y a une douille, en fait, parce qu'on se dit, mais comment ça ? Ben oui, on vient de montrer l'hérédité, donc forcément, ça veut dire que si elle est vraie à quelque part, vous avez compris que la récurrence, c'était montrer que ça va faire un effet domino, elle est vraie à quelque part, donc elle est vraie après, elle est vraie après, elle est vraie après, elle est vraie à l'infini. Mais le problème des dominos, c'est que quand ils sont posés sur le sol, pour qu'ils commencent à tomber, il faut une pitch net au départ. Et la pitch net au départ, c'est l'initialisation. Donc il faut quand même montrer que c'est vrai quelque part. Et tout l'exercice, en fait, c'est ça. C'est un peu une illustration, donc j'ai fait une vidéo là-dessus dans l'application Studio. Il y a une petite vidéo où je parle de ça avec une propriété qui est un peu plus simple. Il existe des propriétés qui vont se transmettre, mais qui ne sont peut-être jamais vraies, en fait. Donc là, je n'ai pas à démontrer que j'ai une pitch net. Pas encore. Donc si vous voulez, on peut essayer de voir. Est-ce que je ne pourrais pas trouver une pitch net ? On pourrait se dire, vas-y, une pitch net, 10 puissance 0 plus 1, ça fait quoi ? 10 puissance 0, ça fait 1, plus 1, ça fait 2. Bon, ben 9, ça ne divise pas 2. 10 puissance 1 plus 1, ça fait 11. Ok, ça a l'air mal barré. Peut-être après, on pourrait dire que, on pourrait peut-être dire, peut-être qu'en fait, ça appartient de 10 puissance 345, que là, c'est divisé par 9. Alors, il faudra trouver une démonstration qui montre que non, ce n'est jamais vrai. Donc on va faire deux choses. On va faire d'abord la meilleure réponse, qui est la réponse vraiment de l'élève qui a compris ce que je disais tout à l'heure. C'est-à-dire ne pas aller chercher trop loin quand on vous pose une question. On vous dit, la proposition Pn, est-elle vraie pour tout anti-naturel n ? Là, moi, je regarde la question 2. J'ignore complètement la question 1 et je dis, ben, je vais regarder. Pour n égale 0, je vais écrire ça. J'ai P de 0, qui dit, 9 divise 10 puissance 0 plus 1, égale 1 plus 1, égale 2. P de 0 est fausse. Point, c'est fini. Vu que la question me dit, très précis, est-ce que la proposition est vraie pour tout anti-naturel n, c'est-à-dire 0 compris, j'ai que à dire, si je veux vraiment être un peu suxe, je dis, pour n égale 0, c'est faux, donc ce n'est pas bon pour tout anti-naturel n, vu que ce n'est pas bon pour 0. Fini. Vous allez me dire, bon, t'es gentil, c'est un peu de la gruge, mais honnêtement, c'est ça. Enfin, on ne peut pas ne pas vous mettre les points. Ça, c'est la meilleure réponse, parce qu'elle prend ce qu'on vous donne dans l'annoncé, et elle montre ce qu'on vous demande. Elle n'est pas vraie pour tout anti-naturel n, parce qu'elle n'est pas vraie pour n égale 0. C'est bon. C'est la contradiction qu'on peut attendre. Si on veut faire un peu mieux, si on voulait vraiment démontrer que ce n'est jamais vrai pour aucun n, c'est du bonus, si vous voulez. Bonus. Donc en bonus. Ce qu'il faut faire pour 10 puissance n plus 1, c'est penser aux chiffres. Je ne sais plus écrire. Les chiffres de 10 puissance n plus 1. 10 puissance n plus 1, c'est un nombre qui est comme ça, avec un certain nombre de 0, plus 1. La somme des chiffres sera toujours égale à 2. Et c'est bon. Ça, c'est votre démonstration. Comme la somme des chiffres est toujours égale à 2, nous, on sait qu'un nombre est divisible par 3 si la somme des chiffres est divisible par 3. 3 ne divise pas 10 puissance n plus 1, parce que ça fait 2 la somme, donc c'est mort. Donc 9 non plus. Si 3 ne divise pas un nombre, 9 ne divise pas le nombre non plus, vu que 3 divise 9. Ça serait une démonstration bonus, si vous voulez. C'est une démonstration bonus si vous voulez vraiment faire de l'arithmétique et démontrer le truc. Mais la meilleure réponse vraiment, c'est celle-ci, parce qu'elle prend vraiment l'énoncé et elle répond exactement et sans effort. Je suis toujours le partisan du moindre effort. Voilà, parfait. Ce que je vous ai mis ici, c'est un petit bilan. L'idée de cet exercice, à retenir par cœur, c'est que l'initialisation est super importante. Vous avez des propriétés qui se transmettent, mais elles sont toujours fausses. Mais si elles étaient vraies, ça se transmettrait. En fait, la transmission ne dépend pas de la véracité de la propriété. C'est juste qu'il y a le truc où, s'il y avait une piche nette, il y a bien des dominos qui s'enchaîneraient. C'est-à-dire que oui, ce truc faux se transmettrait d'un entier à l'autre, mais en fait il est toujours faux, donc aucun intérêt. Et donc voilà. Cet exercice, c'est ça. C'est vraiment une illustration de l'intérêt, de l'utilité fondamentale de l'initialisation.

Hérédité mais...

RELATED

Recommended videos

Introduction à la récurrence

Concept et rédaction

Pourquoi l'initialisation ?