Raisonnement par récurrence (S)

bonjour le raisonnement par récurrence est l'une des bêtes noires du programme je vais vous montrer à travers trois exemples que si vous adoptez une certaine présentation les choses seront déjà beaucoup plus facile mais voyons d'abord le sens et l'objectif d'un raisonnement par récurrence le raisonnement par récurrence à deux spécificités il permet de démontrer des propriétés c'est-à-dire de montrer qu'elles sont vraies mais ne permet pas du tout de comprendre comment elles ont été construites et deuxième spécificité il ne marche que sur des entiers naturels alors pour le comprendre prenons l'exemple des dominos dans la récurrence il y a deux étapes l'initialisation qui correspond à la chute du premier domino et ensuite l'hérédité si un domino tombe il fait tomber le suivant avec des entiers naturels même principe il s'agit de démontrer que la propriété est vrai pour un rond petit c'est à dire trouver le premier entier pour lequel la propriété marche puis ensuite il faut réaliser l'hérédité c'est à dire qu'on suppose que la propriété est vrai pour un entier donné quelconque et alors on doit montrer qu'elle est automatiquement vraie pour le suivant et alors d'après le principe de récurrence la propriété sera vraie pour tous ces entiers premier exemple nous allons démontrer par récurrence une propriété que nous avons déjà construite ensemble la somme des entiers de 1 à n vaut n + 1 xn sur 2 pour une rédaction rapide commencez toujours par nommer la propriété PN ici et précisez bien que les n appartiennent aux entiers naturels l'initialisation consiste à vérifier la propriété sur un entier aussi petit possible ici 1 la somme des entiers de 1 à 1 en fait il y a que 1 et ensuite en remplaçant de l'autre côté N par 1 on obtient également un donc l'égalité vérifiée et P1 est vrai à présent deuxième étape l'hérédité l'étape la plus difficile et c'est pour cela que je vous conseille d'avoir une préparation très stéréotypée toujours rédigée avec la même phrase par exemple celle-ci ou celle de votre professeur ensuite sur votre brouillon vous écrivez pk et pk+1 pour pk+1 on fait la somme des entiers de 1 à 4 + 1 et vous remplacez ici les cas par cas plus un vous avez ainsi votre point de départ votre objectif est le but c'est de passer de l'un à l'autre pour avancer on observe les différences on constate qu'on a un terme supplémentaire ici k+1 on va le rajouter à gauche et à droite donc sur notre manque de gauche on atteint notre objectif on se concentre sur le membre de droite on voit ici que tout est sur deux donc on met au même dénominateur et ensuite on factorise par k+1 il n'y a pas de difficulté particulière on peut donc conclure le calcul pk plus un vrai et l'hérédité pk implique pk pour terminer votre démonstration vous faites la synthèse des deux étapes précédentes P1 vrai et la propriété se transmet vous citez le principe de récurrence et pour conclure trois remarques tout d'abord n'oubliez aucune étape de la conclusion en particulier n'oubliez pas de citer le principe de récurrence deuxième remarque dans une somme de ce type k+1 est un terme l'entouré de parenthèses et donc logique et vous permettra de voir par exemple des factorisation enfin dans la phrase d'introduction de votre hérédité notez bien qu'il faut indiquer un entier fixé ou donner ou quelconque mais surtout pas à écrire pour tout entier sinon vous supposez déjà à votre conclusion et cela n'a aucun sens deuxième exemple somme des carrés de 1 à n égal à cette expression on commence par nommer cette propriété puis ensuite on initialise c'est à dire qu'on teste pour n = 1 il y a aucun problème ça marche donc on conclut Q un vrai ensuite l'hérédité on commence par notre phrase et ensuite on écrit notre point de départ notre objectif faire très attention quand vous écrivez pk+1 aucune difficulté pour la somme mais ici k+1 k+2 mais deux fois 4 + 1 + 1 si vous oubliez les parenthèses vous n'aurez pas de cas plus 3 l'objectif est finalement de passer de la à la je suis passé assez rapidement sur la préparation qui est toujours la même pour me concentrer avec vous sur le passage le plus difficile alors on observe d'abord les différences on voit qu'il y a qu'à plus d'un carré comme terme supplémentaire ici donc on l'ajoute à gauche et à droite on constate que sur le membre de gauche on atteint notre objectif on se concentre alors sur la droite on voit qu'ici on a une fraction sur 6 donc on met au même dénominateur ensuite dans notre objectif on a une forme factorisée avec k+1 facteur et on a k+1 ici et là on peut donc factoriser par cas plus un on constate ensuite qu'il nous reste plus qu'à démontrer que ces deux expressions sont égales puisqu'on a déjà le cas plus un et le sur 6 et pour cela le plus simple consiste à développer chacune de ces expressions on obtient alors deux cas carrés plus cette cas plus 6 pour l'une comme pour l'autre d'où l'égalité chercher ainsi qk+1 est vrai nous avons donc démontré que Siku est vrai que k+1 est aussi vrai on a donc démontré que la propriété se transmet nous avions aussi démontré que Q1 était vrai donc d'après le principe de récurrence pour tout être supérieur à 1 d'autres propriétés dernier exemple démontrer que pour tout and supérieur ou égal à 4 2N supérieur ou égal à n carré on a affaire à une inégalité uniquement vrai à partir de 4 on commence par nommer cette propriété puis on la teste pour 4 2 puissance 4 16 n au carré 16 on veut supérieur ou égal on a égal donc la propriété est vrai ensuite l'hérédité on commence par notre phrase habituelle puis ensuite on inscrit notre point de départ et notre objectif on observe nos deux inégalités passer de deux puissances k à 2 puissance k+1 n'est pas forcément évident on peut penser à une identité remarquable pour passer de CaC carré à cas plus un carré on peut se dire qu'en ajoutant deux cas plus un on va former qu'à plus un carré malheureusement deux exposants cas plus deux cas plus un n'a pas de lien évident avec deux puissances k+1 en fait cette idée était une très bonne idée mais c'est une impasse il ne faut donc pas hésiter à revenir en arrière et observer à nouveau le manque de gauche et pour passer de 2 puissance cas à deux cas plus un il suffit de multiplier par deux et ça c'est l'idée qui permet d'avancer puisqu'on obtient deux exposants cas plus un supérieur à 2k² à gauche les deux membres sont identiques à droite on aimerait bien que deux caca carré soit égal à 4 + 1² mais ce n'est pas le cas et c'est pas si grave pourquoi et bien tout simplement parce que si on démontre que deux cacarés supérieurs à k+1² on aura ce qu'il faut en effet on a déjà deux cas plus un supérieur à deux cas carrés si on démontre que deux kc² supérieur à 4 + 1² on aura automatiquement l'inégalité chercher on doit donc démontrer que deux cas carrés supérieurs à 4 + 1 carré on passe tout à gauche on fonctionne par équivalence ensuite on développe cette identité remarquable et on simplifie il faut reconnaître un polynôme de degré 2 dont on cherche le signe on va donc calculer son delta qui vaut 8 il est positif donc on a deux racines on applique les formules de cours et on calcule les valeurs approchées qui vont nous servir pour le tableau de signe ici on ne perd pas le fil on cherche le signe de ce polynôme le plus sûr pour cela c'est de faire une allure au brouillon à supérieur à 0 puisqu'il est égal à 1 donc on a une courbe en U en place les racines et on en déduit le tableau de signe d'après le tableau de signe le polynôme est supérieur à 0 à partir de 2,4 et donc positif à partir de 3 puisqu'on travaille sur des entiers autrement dit pour tout cas supérieur à 3 qk positif soit k carré - 2K - 1 positif et donc par équivalence on a l'inégalité chercher couplée à la première inégalité on a ainsi atteint notre objectif on a donc pk plus un vrai la propriété se transmet nous avons vu que P4 est vrai donc d'après le principe de récurrence la propriété est vrai pour tout n supérieur à 4 maintenant quelques remarques d'abord en termes de méthode nous avons vu que pour avancer sur les inégalités on peut utiliser des intermédiaires pour montrer que a supérieur AC si on a déjà un supérieur à B il suffit de montrer que B supérieur AC d'autre part autre inégalité un supérieur à B est équivalence qui est beaucoup plus classique à a moins B positif enfin dernière remarque ici il est écrit deux cacarré supérieur à cas plus un carré mais ce n'est pas une affirmation puisque on a un enchaînement d'équivalence en fait ce que ça signifie c'est que si l'une des propriétés est vrai elles sont toutes vraies