BURHAN.

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

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

Notions du cours (11)

Apprendre avec Burhan

Raisonnement par récurrence

Étape 1 sur 4

Des dominos

Devine : Des dominos

Une rangée infinie de dominos est numérotée 00, 11, 22, … Que faut-il savoir pour être sûr qu'ils tombent tous ?

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

Choix A :Que chaque domino qui tombe fait tomber le suivant.

Faux.

Si personne ne pousse le premier, aucun ne tombe.

Choix B :Que le domino numéro 00 tombe.

Faux.

Le premier peut tomber sans entraîner le deuxième, s'ils sont trop espacés.

Choix C :Que les dix premiers dominos tombent.

Faux.

Dix chutes ne disent rien du domino numéro 10001000.

Choix D :Que le premier tombe, et que chacun fait tomber le suivant.

Juste.

Juste : le départ et la transmission, il faut les deux.

Voir la correction complète

Il faut un départ et une transmission : le domino 00 tombe, et chaque domino fait tomber le suivant. Alors le 00 fait tomber le 11, qui fait tomber le 22 : la chute gagne toute la rangée. Le raisonnement par récurrence suit ce schéma.

Regarde les sommes des premiers entiers : 1=1×221 = \dfrac{1 \times 2}{2}, puis 1+2=3=2×321 + 2 = 3 = \dfrac{2 \times 3}{2}, puis 1+2+3=6=3×421 + 2 + 3 = 6 = \dfrac{3 \times 4}{2}. Pour passer au rang suivant, on ajoute 44 : 6+4=10=4×526 + 4 = 10 = \dfrac{4 \times 5}{2}. Si la formule vaut à un rang, ajouter le terme suivant la donne au rang suivant. Ce sont les dominos, avec des nombres.

Soit P(n)P(n) une propriété d'un entier nn. L'initialisation vérifie P(n0)P(n_0) : le premier domino tombe. L'hérédité montre que P(n)P(n) entraîne P(n+1)P(n + 1) : chacun pousse le suivant. Pourquoi est-ce vrai ? S'il y avait un premier entier où PP échoue, ce ne serait pas n0n_0, grâce à l'initialisation ; l'entier d'avant vérifierait PP, et l'hérédité rendrait PP vraie au premier échec : c'est impossible. La preuve rend cette idée rigoureuse, par l'absurde. Elle explique pourquoi la méthode marche : tu peux la relire après le premier exemple rédigé.

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 de la variable entière n≥n0n \geq n_0. On suppose :

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

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

Démonstration

Étape 1. Raisonnons par l'absurde (F11) : supposons qu'il existe un entier n≥n0n \geq n_0 tel que P(n)P(n) soit fausse (F08). Parmi les entiers n≥n0n \geq n_0 tels que P(n)P(n) soit fausse, il en existe un plus petit, noté mm (propriété de N\mathbb{N}, admise).

Étape 2. Par l'initialisation, P(n0)P(n_0) est vraie, donc m≠n0m \neq n_0. Comme m≥n0m \geq n_0, on a m≥n0+1m \geq n_0 + 1, donc m−1m - 1 est un entier et m−1≥n0m - 1 \geq n_0.

Étape 3. Comme m−1≥n0m - 1 \geq n_0, m−1<mm - 1 < m et que mm est le plus petit entier n≥n0n \geq n_0 tel que P(n)P(n) soit fausse, P(m−1)P(m - 1) n'est pas fausse, donc elle est vraie (F01). Par l'hérédité appliquée à n=m−1n = m - 1, P(m)P(m) est vraie (F03). Or P(m)P(m) est fausse, par définition de mm : c'est une contradiction. Donc P(n)P(n) est vraie pour tout entier n≥n0n \geq n_0.

Remarquece qui est admis

La preuve utilise une propriété des entiers naturels : dès qu'un entier naturel au moins vérifie une propriété, il en existe un plus petit qui la vérifie. Cette propriété de N\mathbb{N} est admise. Elle et le principe de récurrence expriment au fond la même chose sur N\mathbb{N} : la preuve montre comment déduire le principe de récurrence de cette propriété.

À retenirCe qu'il faut retenir de la preuve

On suppose qu'un entier met PP en défaut, et l'on prend le plus petit, mm. L'initialisation empêche m=n0m = n_0 ; le choix du plus petit rend P(m−1)P(m - 1) vraie ; l'hérédité rend alors P(m)P(m) vraie. C'est une contradiction. Les deux hypothèses servent : ni l'initialisation, ni l'hérédité ne suffit seule.

Vérifie : À quoi sert l'initialisation ?

Dans la preuve, mm est le plus petit entier n≥n0n \geq n_0 tel que P(n)P(n) soit fausse. À quoi sert l'initialisation ?

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

Choix A :À montrer que m≠n0m \neq n_0, donc que m−1≥n0m - 1 \geq n_0.

Juste.

Juste : comme P(n0)P(n_0) est vraie, mm dépasse n0n_0, et m−1m - 1 reste dans le domaine.

Choix B :À montrer que l'entier mm existe.

Faux.

L'existence de mm vient de la propriété admise de N\mathbb{N}.

Choix C :À montrer que P(m−1)P(m - 1) entraîne P(m)P(m).

Faux.

C'est le rôle de l'hérédité, appliquée à n=m−1n = m - 1.

Choix D :À rien : l'hérédité suffit.

Faux.

Sans P(n0)P(n_0), l'entier mm pourrait valoir n0n_0, et m−1m - 1 sortirait du domaine.

Voir la correction complète

L'initialisation donne P(n0)P(n_0) vraie, donc m≠n0m \neq n_0. Comme m≥n0m \geq n_0, on obtient m≥n0+1m \geq n_0 + 1, soit m−1≥n0m - 1 \geq n_0. L'hérédité peut alors s'appliquer à n=m−1n = m - 1.

ExempleContre-exemple : une hérédité sans initialisation

Soit P(n)P(n) : « 99 divise 10n+110^{n} + 1 ». L'hérédité est vraie : si 10n+1=9a10^{n} + 1 = 9a avec aa entier, alors 10n+1+1=10(10n+1)−9=9(10a−1)10^{n + 1} + 1 = 10(10^{n} + 1) - 9 = 9(10a - 1).

Mais P(0)P(0) est fausse : 100+1=210^{0} + 1 = 2. Et P(1)P(1) aussi : 1111 n'est pas multiple de 99. Sans initialisation, l'hérédité seule ne prouve rien.

← Étape précédenteContinuer : Rédiger une récurrence →

Étape 3 sur 4

Rédiger une récurrence

Méthoderédiger une récurrence

  1. Énoncer la propriété P(n)P(n) et le rang de départ n0n_0.
  2. Initialisation : vérifier P(n0)P(n_0) par un calcul.
  3. Hérédité : « Soit n≥n0n \geq n_0 un entier tel que P(n)P(n) soit vraie ; montrons que P(n+1)P(n + 1) est vraie. » Utilise P(n)P(n) au bon moment.
  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

Énoncé. Pour tout entier n≥1n \geq 1, P(n)P(n) : « 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \dfrac{n(n + 1)}{2} ».

Initialisation. Pour n=1n = 1 : le membre de gauche vaut 11, et 1×22=1\dfrac{1 \times 2}{2} = 1. Donc P(1)P(1) est vraie.

Hérédité. Soit n≥1n \geq 1 un entier tel que P(n)P(n) soit vraie. D'après l'hypothèse de récurrence, 1+2+⋯+n+(n+1)=n(n+1)2+(n+1)=(n+1)(n+2)2.1 + 2 + \dots + n + (n + 1) = \dfrac{n(n + 1)}{2} + (n + 1) = \dfrac{(n + 1)(n + 2)}{2}. 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 entier n≥1n \geq 1.

ExempleExemple guidé : une inégalité à partir du rang 3

Énoncé. Pour tout entier n≥3n \geq 3, P(n)P(n) : « 2n≥2n+12^{n} \geq 2n + 1 ». Pour n=2n = 2, elle est fausse : 4<54 < 5.

Initialisation. 23=82^{3} = 8 et 2×3+1=72 \times 3 + 1 = 7 : P(3)P(3) est vraie.

Hérédité. Soit n≥3n \geq 3 un entier tel que P(n)P(n) soit vraie. Alors, d'après l'hypothèse de récurrence et comme 2>02 > 0, 2n+1=2×2n≥2(2n+1)=4n+22^{n + 1} = 2 \times 2^{n} \geq 2(2n + 1) = 4n + 2. Or 4n+2≥2n+34n + 2 \geq 2n + 3, car 2n≥12n \geq 1. Donc 2n+1≥2(n+1)+12^{n + 1} \geq 2(n + 1) + 1 : 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 entier n≥3n \geq 3.

← Étape précédenteContinuer : Pièges et rédaction →

Étape 4 sur 4

Pièges et rédaction

Attentionl'hypothèse de récurrence porte sur un seul entier

✗ « Hérédité : supposons que P(n)P(n) est vraie pour tout entier nn. »

✓ « Soit n≥n0n \geq n_0 un entier tel que P(n)P(n) soit vraie. » On suppose P(n)P(n) pour un entier nn fixé. Supposer « pour tout nn », c'est supposer ce qu'on veut démontrer. Et l'initialisation reste obligatoire, comme le montre le contre-exemple de 10n+110^{n} + 1.

Vérifie : Le bon découpage

On veut montrer par récurrence que 33 divise 4n−14^{n} - 1 pour tout n∈Nn \in \mathbb{N}. Dans l'hérédité, quelle égalité fait apparaître 4n−14^{n} - 1 ?

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

Choix A :4n+1−1=(4n−1)+44^{n + 1} - 1 = (4^{n} - 1) + 4

Faux.

Le membre de droite vaut 4n+34^{n} + 3, et non 4n+1−14^{n + 1} - 1.

Choix B :4n+1−1=4(4n−1)+34^{n + 1} - 1 = 4(4^{n} - 1) + 3

Juste.

Juste : 4×4n−4+3=4n+1−14 \times 4^{n} - 4 + 3 = 4^{n + 1} - 1.

Choix C :4n+1−1=4×4n−44^{n + 1} - 1 = 4 \times 4^{n} - 4

Faux.

Le membre de droite vaut 4n+1−44^{n + 1} - 4 : il manque 33.

Choix D :4n+1−1=(4n−1)24^{n + 1} - 1 = (4^{n} - 1)^{2}

Faux.

Pour n=1n = 1 : 42−1=154^{2} - 1 = 15, mais (4−1)2=9(4 - 1)^{2} = 9.

Voir la correction complète

4(4n−1)+3=4n+1−4+3=4n+1−14(4^{n} - 1) + 3 = 4^{n + 1} - 4 + 3 = 4^{n + 1} - 1. Si 4n−1=3a4^{n} - 1 = 3a, avec aa entier, alors 4n+1−1=12a+3=3(4a+1)4^{n + 1} - 1 = 12a + 3 = 3(4a + 1). Avec l'initialisation 40−1=0=3×04^{0} - 1 = 0 = 3 \times 0, la récurrence est complète.

À toi : Rédige une récurrence

Rédige la preuve par récurrence de : pour tout entier n≥1n \geq 1, 1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \dots + (2n - 1) = n^{2}. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Écris P(n)P(n), puis vérifie l'initialisation pour n=1n = 1.

Encore bloqué ? Indice 2

Dans l'hérédité, le terme suivant de la somme est 2(n+1)−1=2n+12(n + 1) - 1 = 2n + 1.

Encore bloqué ? Indice 3

Point délicat : remplace la somme jusqu'à 2n−12n - 1 par n2n^{2}, grâce à P(n)P(n).

Voir la solution complète

Soit 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. Donc P(1)P(1) est vraie.

Hérédité. Soit n≥1n \geq 1 un entier tel que P(n)P(n) soit vraie. Alors 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}, d'après l'hypothèse de récurrence. 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 entier n≥1n \geq 1.

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

En devoir, une récurrence se reconnaît à sa forme. Écris les trois titres : Initialisation, Hérédité, Conclusion. Dans l'hérédité, signale l'endroit où tu utilises P(n)P(n) : « d'après l'hypothèse de récurrence ». Termine par la phrase « D'après le principe de récurrence, P(n)P(n) est vraie pour tout entier n≥n0n \geq n_0 ». Cette forme te servira jusqu'à l'examen de 2BAC SM.

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