BURHAN.

Raisonnement par récurrence : Cours de Mathématiques 1BAC Sciences Économiques et Gestion, chapitre Notions de logique

Raisonnement par récurrence : notion du chapitre Notions de logique du programme de maths 1BAC SEG, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 1BAC Sciences Économiques et Gestion, option française (BIOF).

Notions du cours (8)

Apprendre avec Burhan

Le raisonnement par récurrence

Étape 1 sur 4

De proche en proche

En clair. Pense à une longue rangée de dominos. Le premier bascule. Chacun, en basculant, pousse son voisin. Résultat : toute la rangée finit par terre.

Devine : Tous les dominos

Lesquelles de ces informations garantissent que tous les dominos de la file tombent ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Le dixième tombe, et chaque domino qui tombe renverse le suivant.

Faux.

Les neuf premiers peuvent rester debout.

Choix B :Le premier domino de la file tombe.

Faux.

Rien ne dit que sa chute renverse le deuxième.

Choix C :Le premier tombe, et chaque domino qui tombe renverse le suivant.

Juste.

Juste : il faut un départ, et une transmission d'un domino au suivant.

Choix D :Chaque domino qui tombe renverse le suivant.

Faux.

Si aucun domino ne tombe, aucun n'en renverse un autre.

Voir la correction complète

Il faut deux choses : un départ, le premier domino qui tombe, et une transmission, chaque domino qui tombe renverse le suivant. Avec le dixième comme départ, seuls les dominos à partir du dixième sont sûrs de tomber. Sans départ, la transmission ne sert à rien.

Continuer : Le principe de récurrence →

Étape 2 sur 4

Le principe de récurrence

ThéorèmePrincipe de récurrence

Soit n0n_0 un entier naturel et P(n)P(n) une fonction propositionnelle définie pour les entiers naturels n≥n0n \geq n_0. Si

  • P(n0)P(n_0) est vraie (initialisation),
  • et, pour tout entier naturel n≥n0n \geq n_0, l'implication P(n)⇒P(n+1)P(n) \Rightarrow P(n + 1) est vraie (hérédité),

alors P(n)P(n) est vraie pour tout entier naturel n≥n0n \geq n_0.

RemarqueUn principe de départ

Ce résultat est admis.

En clair. L'initialisation, c'est le premier domino qui tombe. L'hérédité, c'est chaque domino qui renverse le suivant. Le principe affirme alors que tous les dominos tombent : P(n)P(n) est vraie pour chaque entier à partir de n0n_0.

Méthoderédiger une démonstration par récurrence

  1. Énonce la propriété P(n)P(n) et l'entier de départ n0n_0.
  2. Initialisation : vérifie par un calcul que P(n0)P(n_0) est vraie.
  3. Hérédité : « Soit n≥n0n \geq n_0 un entier tel que P(n)P(n) est vraie. Montrons que P(n+1)P(n + 1) est vraie. » Sers-toi de P(n)P(n) dans le calcul.
  4. Conclusion : « D'après le principe de récurrence, P(n)P(n) est vraie pour tout entier n≥n0n \geq n_0. »

ExempleExemple guidé : une somme d'entiers

Montrons que, pour tout entier n≥1n \geq 1, 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \dfrac{n(n + 1)}{2}. On note P(n)P(n) cette égalité.

  • Initialisation : pour n=1n = 1, le premier membre vaut 11, et 1×22=1\dfrac{1 \times 2}{2} = 1.
  • Hérédité : soit n≥1n \geq 1 tel que P(n)P(n) est vraie. Alors 1+2+⋯+n+(n+1)=n(n+1)2+(n+1)=n(n+1)+2(n+1)2=(n+1)(n+2)2,1 + 2 + \dots + n + (n + 1) = \dfrac{n(n + 1)}{2} + (n + 1) = \dfrac{n(n + 1) + 2(n + 1)}{2} = \dfrac{(n + 1)(n + 2)}{2}, en réduisant au même dénominateur, puis en mettant n+1n + 1 en facteur. C'est P(n+1)P(n + 1).
  • Conclusion : d'après le principe de récurrence, P(n)P(n) est vraie pour tout n≥1n \geq 1.

← Étape précédenteContinuer : Une inégalité, puis un piège →

Étape 3 sur 4

Une inégalité, puis un piège

ExempleExemple guidé : une inégalité

Montrons que, pour tout entier naturel nn, 2n≥n+12^{n} \geq n + 1.

  • Initialisation : pour n=0n = 0, 20=12^{0} = 1 et 0+1=10 + 1 = 1 : on a bien 1≥11 \geq 1.
  • Hérédité : soit nn un entier naturel tel que 2n≥n+12^{n} \geq n + 1. Alors 2n+1=2×2n≥2(n+1)=2n+22^{n + 1} = 2 \times 2^{n} \geq 2(n + 1) = 2n + 2. Or 2n+2≥n+22n + 2 \geq n + 2, car n≥0n \geq 0. Donc 2n+1≥(n+1)+12^{n + 1} \geq (n + 1) + 1.
  • Conclusion : d'après le principe de récurrence, l'inégalité est vraie pour tout entier naturel nn.

Attentionune hérédité seule ne prouve rien

✗ « Si 4n+14^{n} + 1 est un multiple de 33, alors 4n+1+1=4(4n+1)−34^{n + 1} + 1 = 4(4^{n} + 1) - 3 en est un aussi. Donc 4n+14^{n} + 1 est un multiple de 33 pour tout nn. »

✓ L'hérédité est juste, mais l'initialisation manque, et elle échoue : 40+1=24^{0} + 1 = 2 et 41+1=54^{1} + 1 = 5 ne sont pas des multiples de 33. En fait, aucun nombre 4n+14^{n} + 1 n'en est un. Sans initialisation, une hérédité ne prouve rien.

Vérifie : Ce que l'on suppose

On veut montrer par récurrence que, pour tout entier n≥1n \geq 1, 1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \dots + (2n - 1) = n^{2}. Dans l'hérédité, que suppose-t-on ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Que l'égalité est vraie pour un entier n≥1n \geq 1 fixé.

Juste.

Juste : on suppose P(n)P(n) pour un nn donné, puis on démontre P(n+1)P(n + 1).

Choix B :Que l'égalité est vraie pour tout entier n≥1n \geq 1.

Faux.

C'est ce que l'on veut démontrer : on ne peut pas le supposer.

Choix C :Que l'égalité est vraie au rang n+1n + 1.

Faux.

C'est le but de l'hérédité, pas sa supposition.

Choix D :Que l'égalité est vraie au rang 11 seulement.

Faux.

C'est l'initialisation, vérifiée à part.

Voir la correction complète

Dans l'hérédité, on fixe un entier n≥1n \geq 1, et l'on suppose l'égalité vraie pour ce nn. On démontre alors l'égalité au rang n+1n + 1 : 1+3+⋯+(2n−1)+(2n+1)=n2+2n+1=(n+1)21 + 3 + \dots + (2n - 1) + (2n + 1) = n^{2} + 2n + 1 = (n + 1)^{2}. Supposer l'égalité pour tout nn reviendrait à supposer ce que l'on veut démontrer.

← Étape précédenteContinuer : Une situation, à toi, le coin devoir →

Étape 4 sur 4

Une situation, à toi, le coin devoir

Exempleun capital qui grandit d'année en année

Données fictives : un capital de 50005000 DH gagne 200200 DH de plus par an. On note P(n)P(n) : « après nn années, le capital vaut 5000+200n5000 + 200n DH ». Montrons P(n)P(n) pour tout entier naturel nn.

  • Initialisation : après 00 année, le capital vaut 5000=5000+200×05000 = 5000 + 200 \times 0 DH.
  • Hérédité : si, après nn années, il vaut 5000+200n5000 + 200n DH, alors un an plus tard il vaut 5000+200n+200=5000+200(n+1)5000 + 200n + 200 = 5000 + 200(n + 1) DH. C'est P(n+1)P(n + 1).
  • Conclusion : le principe de récurrence donne P(n)P(n) pour tout entier naturel nn. Après 1212 années, le capital vaut 5000+2400=74005000 + 2400 = 7400 DH.

À toi : Une récurrence à rédiger

Montre par récurrence que, pour tout entier naturel nn, 3n≥1+2n3^{n} \geq 1 + 2n. Rédige ta réponse sur ton cahier, puis dévoile la correction.

Besoin d'aide ? Indice 1

Suis la méthode : initialisation pour n=0n = 0, puis hérédité.

Encore bloqué ? Indice 2

Dans l'hérédité, écris 3n+1=3×3n3^{n + 1} = 3 \times 3^{n}, et utilise l'hypothèse 3n≥1+2n3^{n} \geq 1 + 2n.

Encore bloqué ? Indice 3

Point délicat : il reste à comparer 3+6n3 + 6n et 3+2n3 + 2n ; étudie le signe de leur différence.

Voir la solution complète

On note P(n)P(n) : « 3n≥1+2n3^{n} \geq 1 + 2n ».

  • Initialisation : pour n=0n = 0, 30=13^{0} = 1 et 1+2×0=11 + 2 \times 0 = 1 : P(0)P(0) est vraie.
  • Hérédité : soit nn un entier naturel tel que P(n)P(n) est vraie. Alors 3n+1=3×3n≥3(1+2n)=3+6n3^{n + 1} = 3 \times 3^{n} \geq 3(1 + 2n) = 3 + 6n. Or 3+6n≥3+2n=1+2(n+1)3 + 6n \geq 3 + 2n = 1 + 2(n + 1), car 4n≥04n \geq 0. Donc P(n+1)P(n + 1) est vraie.
  • Conclusion : d'après le principe de récurrence, P(n)P(n) est vraie pour tout entier naturel nn.

RemarqueCoin devoir : rédiger une récurrence

En devoir, une récurrence se rédige en trois parties titrées. Écris : « Initialisation : pour n=0n = 0, on vérifie le calcul. » Puis : « Hérédité : soit nn un entier naturel tel que P(n)P(n) est vraie ; montrons que P(n+1)P(n + 1) est vraie. » Enfin : « Conclusion : d'après le principe de récurrence, P(n)P(n) est vraie pour tout entier naturel nn. » Montre bien où tu utilises P(n)P(n).

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Notions de logique » (1bac · sciences-economiques-et-gestion · mathematiques)