Le raisonnement par récurrence

Bonjour,

J’ai vu que ce sujet avait été traité plusieurs fois malheureusement mon niveau est bien plus faible que la majorité des sujets donc ça ne m’aide pas vraiment, je me permet donc de poser ma question.

J’ai décidé de passer mon Bac S en candidat libre (c’est un sacré défis). J’en suis à réviser le début du programme, j’avoue ramer un peu sur le raisonnement par récurrence. J’ai bien compris le principe. La première étape (l’initilisation) ne me pose pas de problème et la dernière (conclusion) encore moins évidemment, en revanche l’étape de l’hérédité est très flou pour moi.

Voici l’exercice :

Démontrer par récurrence que pour tout entier $n \geq 1$, $1 + ... + n = \dfrac{n(n+1)}{2}$

Soit $P(n) = 1 + ... + n = \dfrac{n(n+1)}{2}$

Initialisation

Vérifions que $P(n)$ est vraie :

$P(1) : 1 = \dfrac{1x(1+1)}{2}$ donc $P(1)$ est vraie.

Hérédité

Soit un entier $n \geq 1$. Supposons $P(n)$ vraie et montrons que $P(n+1)$ est vraie.

$1 + ... + n + n + 1 = \dfrac{n(n+1)}{2} + n + 1$

(Cette partie est assimilée, maintenant vient la partie que je n’arrive pas à comprendre)

$= (n + 1)[\dfrac{n}{2}+1]$

Je vais m’arrêter là pour l’explication de l’exercice. Je bloque exactement à ce moment, je n’arrive pas à comprendre d’où vient le $+ 1$ qui est entre les crochets. Ca doit être une question idiote mais mon cerveau n’assimile pas cette information.

Merci pour votre aide, désolé pour le dérangement si la question est nulle, j’espère que vous serez compréhensif et pas jugeant vis à vis de mon objectif (Bac S en candidat libre).

Je te remercie pour ta réponse. Je comprends qu’en fait c’est juste une histoire de factorisation. Faut que je m’entraîne un maximum (surtout qu’apparemment le raisonnement par récurrence c’est un exercice qui tombe souvent lors du Bac).

Comme on le dit souvent: "il n’y a pas de questions idiotes."
Chacun d’entre nous a des facilités/difficultés.

Ton objectif est ambitieux et tu ne dois pas avoir peur de poser des questions afin de pouvoir atteindre ton but

Sache que non seulement il n’y a pas de question idiote mais qu’en plus ça nous aide à comprendre où un non-initié pourrait avoir des problèmes.

Il y a par exemple un tutoriel sur le raisonnement par récurrence, on aimerait avoir plus de tutoriel comme celui-ci.

Les questions sont considérées comme idiote quand le professeur ne sait pas y répondre, ainsi il cache son incompétence ou qu’il ne veut pas expliquer pour cacher sa fainéantise d’expliquer.

Merci pour vos messages bienveillants. Je ne baisse pas les bras, je continue à m’entraîner. J’espère ne pas bloquer autant de temps sur les autres notions à apprendre, il ne me reste pas énormément de temps pour me remettre à niveau.

Hello les gars,

Je reviens pour une mauvaise nouvelle, "J’ai toujours pas compris". Vraiment, c’est incompréhensible, chaque exemple que je regarde à chaque fois ils rajoutent des chiffres sans donner la moindre explication.

Voici l’exemple du livre sans aucun modification :

Soit la suite définie pour tout entier $n$ par $un = 5^n+1$. Montrez que la proposition $Pn : un$ est un multiple de $4$ est héréditaire. Supposons que $Pn$ soit vraie pour un certain entier $n$. Cela signifie qu’il existe un entier $k$ tel que $5^n + 1 = 4k$. Montront que $Pn+1$ est vraie.

On a $5^{n+1} + 1 = 5 * (5^n + 1) - 5 + 1 = 5 * (5^n + 1) - 4$.

Or $Pn$ est vraie, donc on a $5^{n+1} + 1 = 5 * 4k - 4$

On vient de démontrer que $Pn+1$ est vraie. La proposition $Pn$ est donc bien héréditaire.

Remarque : Quelques calculs permettent de constater que les premiers termes ne sont pas des multiples de $4 : u0 = 2$, $u1 = 6$, $u2 = 26$, $u3 = 126$… La proposition $Pn : un$ est un multiple de $4$ est donc héréditaire sans pour autant être vraie pour tout entier $n$. En revanche, on peut penser que, pour tout entier $n$, il existe un entier $k$ tel que $un = 4k + 2$.

Pour vous, il doit vous paraitre très clair, pour moi c’est un casse-tête depuis hier. Je ne comprends pas pourquoi à cette étape On a $5^{n+1} + 1 = 5 * (5^n + 1) - 5 + 1 = 5 * (5^n + 1) - 4$, ils vont faire $-5$.

C’est un exemple parmi tant d’autres, j’ai une liste d’exercice énorme que je peux faire pour m’entrainer, je vais réussir à répondre aux premières questions (généralement les plus simples) mais au bout d’un moment je ne vais plus savoir et en regarder la correction je vais vraiment être en incompréhension et généralement c’est : "Mais comment ils peuvent rajouter ce chiffre ?"

Bref si quelqu’un peut m’expliquer ou connait un cours ultra bien expliqué (même si j’ai écumé les internets) ça sera très sympa.

PS : Je me rassure en voyant les commentaires de vidéos Youtube que même des étudiants de Terminal bloque sur ce principe en mathématique, ça doit être mon côté sadique.

Merci infiniment de votre aide !

Pas de panique : le raisonnement pas récurrence, ce n’est pas facile et il faut un peu de temps pour s’y habituer.

Je reprends tes notations. Soit $n$ un entier, et supposons que $u_n$ est un multiple de 4. Que doit-on montrer ? On doit montrer que $u_{n+1}$ est un multiple de 4. Que peut-on utiliser ? Pas grand-chose, finalement : la seule chose que l’on ait, c’est l’hypothèse de récurrence.

Une stratégie souvent efficace consiste à écrire (au moins au brouillon) explicitement ce à quoi tu veux arriver. Ici, il faut montrer que $u_{n+1}$ est un multiple de 4, donc que l’on peut écrire $u_{n+1} = 4\times k'$, où $k'$ est un entier naturel. Allons-y : d’après la définition de la suite $(u_n)_{n\in\mathbb N}$, $u_{n+1}=5^{n+1}+1$. Comme je le disais, il n’y a pas trop le choix : on va utiliser l’hypothèse de récurrence. On a donc besoin de faire apparaître, d’une manière ou d’une autre, le terme $u_n = 4^n+1$. Je propose de le rédiger comme suit : $u_{n+1} = 5^{n+1}+1 = 5\times 5^n +1 = 5(5^n+1)-4$ Et c’est là que tout s’est joué : j’ai fait apparaître de force $5^n+1$ (pour utiliser l’h.r.), mais pour retomber sur $u_{n+1}$, je dois soustraire $4$. Ensuite, on a presque fini : $u_{n+1} = 5\times u_n-4$, mais $4$ divise $u_n$ donc $u_n=4k$ pour un certain entier $k$. D’où $u_{n+1} = 5\times4k-4 = 4(5k-1)$. En posant $k'=5k-1$, l’hérédité arrive.

Précision importante — On est typiquement dans le cas où la propriété est héréditaire, mais pas initialisée. Donc en réalité, l’assertion est fausse (d’ailleurs, cela se voit en testant pour des petites valeurs de $n$). Il peut être intéressant de démontrer l’hérédité pour s’entraîner, mais en aucun cas on ne peut conclure à la vérité de $P(n)$ pour $n$ entier quelconque.

En détaillant encore plus :

$u_{n+1} = 5^{n+1} + 1 = 5 \times 5^n + 1 = 5 \times 5^n + (5 - 5) + 1 = 5 \times (5^n + 1) - 5 + 1 = 5 \times (5^n + 1) - 4$