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 4Des dominos
Devine : Des dominos

Une rangée infinie de dominos est numérotée , , , … 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 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 .
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 tombe, et chaque domino fait tomber le suivant. Alors le fait tomber le , qui fait tomber le : la chute gagne toute la rangée. Le raisonnement par récurrence suit ce schéma.
Regarde les sommes des premiers entiers : , puis , puis . Pour passer au rang suivant, on ajoute : . Si la formule vaut à un rang, ajouter le terme suivant la donne au rang suivant. Ce sont les dominos, avec des nombres.
Soit une propriété d'un entier . L'initialisation vérifie : le premier domino tombe. L'hérédité montre que entraîne : chacun pousse le suivant. Pourquoi est-ce vrai ? S'il y avait un premier entier où échoue, ce ne serait pas , grâce à l'initialisation ; l'entier d'avant vérifierait , et l'hérédité rendrait 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é.
Étape 2 sur 4Le principe de récurrence
ThéorèmePrincipe de récurrence
Soit un entier naturel et une fonction propositionnelle de la variable entière . On suppose :
- initialisation : est vraie ;
- hérédité : pour tout entier , l'implication est vraie.
Alors, pour tout entier naturel , est vraie.
Démonstration
Étape 1. Raisonnons par l'absurde (F11) : supposons qu'il existe un entier tel que soit fausse (F08). Parmi les entiers tels que soit fausse, il en existe un plus petit, noté (propriété de , admise).
Étape 2. Par l'initialisation, est vraie, donc . Comme , on a , donc est un entier et .
Étape 3. Comme , et que est le plus petit entier tel que soit fausse, n'est pas fausse, donc elle est vraie (F01). Par l'hérédité appliquée à , est vraie (F03). Or est fausse, par définition de : c'est une contradiction. Donc est vraie pour tout entier .

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 est admise. Elle et le principe de récurrence expriment au fond la même chose sur : 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 en défaut, et l'on prend le plus petit, . L'initialisation empêche ; le choix du plus petit rend vraie ; l'hérédité rend alors 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, est le plus petit entier tel que 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 , donc que .
Juste.
Juste : comme est vraie, dépasse , et reste dans le domaine.
Choix B :À montrer que l'entier existe.
Faux.
L'existence de vient de la propriété admise de .
Choix C :À montrer que entraîne .
Faux.
C'est le rôle de l'hérédité, appliquée à .
Choix D :À rien : l'hérédité suffit.
Faux.
Sans , l'entier pourrait valoir , et sortirait du domaine.
Voir la correction complète
L'initialisation donne vraie, donc . Comme , on obtient , soit . L'hérédité peut alors s'appliquer à .
ExempleContre-exemple : une hérédité sans initialisation
Soit : « divise ». L'hérédité est vraie : si avec entier, alors .
Mais est fausse : . Et aussi : n'est pas multiple de . Sans initialisation, l'hérédité seule ne prouve rien.

Étape 3 sur 4Rédiger une récurrence
Méthoderédiger une récurrence
- Énoncer la propriété et le rang de départ .
- Initialisation : vérifier par un calcul.
- Hérédité : « Soit un entier tel que soit vraie ; montrons que est vraie. » Utilise au bon moment.
- Conclusion : « D'après le principe de récurrence, est vraie pour tout entier . »

ExempleExemple guidé : une somme d'entiers
Énoncé. Pour tout entier , : « ».
Initialisation. Pour : le membre de gauche vaut , et . Donc est vraie.
Hérédité. Soit un entier tel que soit vraie. D'après l'hypothèse de récurrence, C'est .
Conclusion. D'après le principe de récurrence, est vraie pour tout entier .

ExempleExemple guidé : une inégalité à partir du rang 3
Énoncé. Pour tout entier , : « ». Pour , elle est fausse : .
Initialisation. et : est vraie.
Hérédité. Soit un entier tel que soit vraie. Alors, d'après l'hypothèse de récurrence et comme , . Or , car . Donc : c'est .
Conclusion. D'après le principe de récurrence, est vraie pour tout entier .

Étape 4 sur 4Pièges et rédaction
Attentionl'hypothèse de récurrence porte sur un seul entier
✗ « Hérédité : supposons que est vraie pour tout entier . »
✓ « Soit un entier tel que soit vraie. » On suppose pour un entier fixé. Supposer « pour tout », c'est supposer ce qu'on veut démontrer. Et l'initialisation reste obligatoire, comme le montre le contre-exemple de .

Vérifie : Le bon découpage

On veut montrer par récurrence que divise pour tout . Dans l'hérédité, quelle égalité fait apparaître ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
Le membre de droite vaut , et non .
Choix B :
Juste.
Juste : .
Choix C :
Faux.
Le membre de droite vaut : il manque .
Choix D :
Faux.
Pour : , mais .
Voir la correction complète
. Si , avec entier, alors . Avec l'initialisation , la récurrence est complète.
À toi : Rédige une récurrence

Rédige la preuve par récurrence de : pour tout entier , . Écris ta réponse avant de dévoiler la correction.
Besoin d'aide ? Indice 1
Écris , puis vérifie l'initialisation pour .
Encore bloqué ? Indice 2
Dans l'hérédité, le terme suivant de la somme est .
Encore bloqué ? Indice 3
Point délicat : remplace la somme jusqu'à par , grâce à .
Voir la solution complète
Soit : « ».
Initialisation. Pour : le membre de gauche vaut , et . Donc est vraie.
Hérédité. Soit un entier tel que soit vraie. Alors , d'après l'hypothèse de récurrence. C'est .
Conclusion. D'après le principe de récurrence, est vraie pour tout entier .
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 : « d'après l'hypothèse de récurrence ». Termine par la phrase « D'après le principe de récurrence, est vraie pour tout entier ». 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)
