BURHAN.

Raisonnement par récurrence : Cours de Mathématiques 1BAC Sciences Expérimentales, chapitre Notions de logique

Raisonnement par récurrence : notion du chapitre Notions de logique du programme de maths 1BAC Sciences Expérimentales, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 1BAC Sciences Expérimentales et Sciences et Technologies (STE, STM), option française (BIOF).

Notions du cours (10)

Apprendre avec Burhan

Raisonnement par récurrence

Étape 1 sur 4

Une file de dominos

En clair. Imagine une file de dominos. Si le premier tombe, et si chaque domino qui tombe renverse le suivant, alors tous tombent. Aucun n'échappe : le premier tombe, donc le deuxième, donc le troisième, et ainsi de suite. Le raisonnement par récurrence suit ce schéma pour démontrer une propriété de tous les entiers, à partir d'un premier rang.

Devine : Une somme d'impairs

On calcule : 1=11 = 1, 1+3=41 + 3 = 4, 1+3+5=91 + 3 + 5 = 9. Que vaut 1+3+5+71 + 3 + 5 + 7 ?

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

Choix A :1515

Faux.

Recompte : 9+7=169 + 7 = 16.

Choix B :1717

Faux.

Tu as ajouté 88 au lieu de 77 : le quatrième nombre impair est 77, et 9+7=169 + 7 = 16.

Choix C :1616

Juste.

Juste : 9+7=16=429 + 7 = 16 = 4^{2}.

Choix D :2525

Faux.

25=5225 = 5^{2} correspond à cinq termes : il faudrait ajouter 99.

Voir la correction complète

1+3+5+7=161 + 3 + 5 + 7 = 16. Les résultats successifs sont 11, 44, 99, 1616 : ce sont les carrés 121^{2}, 222^{2}, 323^{2}, 424^{2}. On conjecture que 1+3+⋯+(2n−1)=n21 + 3 + \dots + (2n - 1) = n^{2} pour tout entier n≥1n \geq 1. Mais des essais ne prouvent rien : il faut un raisonnement qui vaut pour tous les entiers.

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 tout entier naturel n≥n0n \geq n_0. Si :

  • P(n0)P(n_0) est vraie (initialisation) ;
  • 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.

RemarqueAdmis

Ce résultat est admis. Il traduit une propriété de l'ensemble des entiers naturels : en partant de n0n_0 et en avançant de 11 en 11, on atteint chaque entier n≥n0n \geq n_0.

Le vocabulaire. L'initialisation vérifie la propriété au premier rang : c'est le premier domino qui tombe. L'hérédité montre que, pour un entier nn quelconque, P(n)P(n) vraie entraîne P(n+1)P(n + 1) vraie. Dans l'hérédité, la proposition P(n)P(n) supposée vraie s'appelle l'hypothèse de récurrence. La conclusion cite le principe de récurrence.

Méthoderédiger une récurrence

  1. Annoncer la propriété P(n)P(n) et son premier rang n0n_0.
  2. Initialisation : calcule les deux membres pour n=n0n = n_0 et compare-les.
  3. Hérédité : « Soit n≥n0n \geq n_0 un entier ; supposons P(n)P(n) vraie. Montrons P(n+1)P(n + 1). » Signale l'endroit où sert l'hypothèse de récurrence.
  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é : la somme des impairs

Propriété. Pour n≥1n \geq 1, notons P(n)P(n) : « 1+3+⋯+(2n−1)=n21 + 3 + \dots + (2n - 1) = n^{2} ».

Initialisation. Pour n=1n = 1, le membre de gauche vaut 11, et 12=11^{2} = 1 : P(1)P(1) est vraie.

Hérédité. Soit n≥1n \geq 1 un entier ; supposons P(n)P(n) vraie. Le terme suivant est 2(n+1)−1=2n+12(n + 1) - 1 = 2n + 1. D'après l'hypothèse de récurrence : 1+3+⋯+(2n−1)+(2n+1)=n2+2n+1=(n+1)2.1 + 3 + \dots + (2n - 1) + (2n + 1) = n^{2} + 2n + 1 = (n + 1)^{2}. 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 n≥1n \geq 1.

← Étape précédenteContinuer : Une divisibilité ; un piège →

Étape 3 sur 4

Une divisibilité ; un piège

ExempleExemple guidé : une divisibilité

Propriété. Pour n≥0n \geq 0, notons P(n)P(n) : « 44 divise 5n−15^{n} - 1 ».

Initialisation. 50−1=0=4×05^{0} - 1 = 0 = 4 \times 0 : P(0)P(0) est vraie.

Hérédité. Soit n≥0n \geq 0 un entier ; supposons P(n)P(n) vraie. D'après l'hypothèse de récurrence, 5n−1=4k5^{n} - 1 = 4k, avec kk entier. Alors 5n=4k+15^{n} = 4k + 1, et 5n+1−1=5(4k+1)−1=20k+4=4(5k+1).5^{n+1} - 1 = 5(4k + 1) - 1 = 20k + 4 = 4(5k + 1). Comme 5k+15k + 1 est entier, 44 divise 5n+1−15^{n+1} - 1 : P(n+1)P(n + 1) est vraie.

Conclusion. D'après le principe de récurrence, 44 divise 5n−15^{n} - 1 pour tout entier naturel nn.

Attentionune hérédité sans initialisation

✗ « Notons Q(n)Q(n) la propriété : 44 divise 5n+15^{n} + 1. Si 5n+1=4k5^{n} + 1 = 4k, alors 5n+1+1=5×4k−4=4(5k−1)5^{n+1} + 1 = 5 \times 4k - 4 = 4(5k - 1). Donc Q(n)Q(n) est vraie pour tout nn. »

✓ Le calcul d'hérédité est juste, mais l'initialisation manque, et elle échoue : 50+1=25^{0} + 1 = 2 n'est pas divisible par 44. En réalité, Q(n)Q(n) n'est vraie pour aucun entier nn. Sans premier domino, rien ne tombe.

Vérifie : Ce que l'on suppose

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 P(n)P(n) est vraie pour tous les entiers n≥n0n \geq n_0.

Faux.

C'est ce qu'il faut démontrer : le supposer serait tourner en rond.

Choix B :Que P(n)P(n) est vraie pour un entier n≥n0n \geq n_0 fixé.

Juste.

Juste : c'est l'hypothèse de récurrence.

Choix C :Que P(n+1)P(n + 1) est vraie pour un entier n≥n0n \geq n_0.

Faux.

C'est la conclusion de l'hérédité, pas son hypothèse.

Choix D :Que P(n0)P(n_0) est fausse, pour aboutir à une contradiction.

Faux.

Ce serait un raisonnement par l'absurde, pas une hérédité.

Voir la correction complète

On fixe un entier n≥n0n \geq n_0, et l'on suppose P(n)P(n) vraie pour cet entier : c'est l'hypothèse de récurrence. On en déduit P(n+1)P(n + 1). Supposer P(n)P(n) pour tous les entiers reviendrait à supposer le résultat.

← Étape précédenteContinuer : À toi, le coin devoir →

Étape 4 sur 4

À toi, le coin devoir

À toi : Une inégalité

Montre par récurrence que, pour tout entier naturel nn, 2n≥n+12^{n} \geq n + 1. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Initialisation : calcule 202^{0} et 0+10 + 1.

Encore bloqué ? Indice 2

Hérédité : 2n+1=2×2n2^{n+1} = 2 \times 2^{n} ; utilise l'hypothèse de récurrence 2n≥n+12^{n} \geq n + 1.

Encore bloqué ? Indice 3

Point délicat : tu obtiens 2n+1≥2n+22^{n+1} \geq 2n + 2 ; compare 2n+22n + 2 à n+2n + 2 pour conclure.

Voir la solution complète

Notons P(n)P(n) : « 2n≥n+12^{n} \geq n + 1 ».

Initialisation. 20=12^{0} = 1 et 0+1=10 + 1 = 1 : P(0)P(0) est vraie.

Hérédité. Soit n≥0n \geq 0 un entier ; supposons P(n)P(n) vraie. D'après l'hypothèse de récurrence, 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 : P(n+1)P(n + 1) est vraie.

Conclusion. D'après le principe de récurrence, 2n≥n+12^{n} \geq n + 1 pour tout entier naturel nn.

RemarqueCoin devoir : une récurrence rédigée

En devoir, une récurrence se lit en trois parties titrées : « Initialisation », « Hérédité », « Conclusion ». Dans l'hérédité, signale où tu utilises l'hypothèse : « d'après l'hypothèse de récurrence ». Termine par : « D'après le principe de récurrence, la propriété est vraie pour tout entier n≥n0n \geq n_0. » Ce schéma te resservira jusqu'à l'examen de 2BAC SE.

← É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-experimentales · mathematiques)