Éducation Nationale Française · MP2I
Raisonner et rédiger
Vue d'ensemble du chapitre
Ce chapitre n'introduit aucun objet mathématique nouveau. Il codifie la rédaction dont se sert toute démonstration : comment introduire un objet, comment démontrer un énoncé construit avec des quantificateurs ou des connecteurs, comment démontrer une relation entre ensembles, comment rédiger une récurrence, comment raisonner par l'absurde ou par analyse-synthèse. Les textes « Piège » montrent les fautes que l'on rencontre le plus souvent dans les copies, avec leur correction. Les principes de récurrence sont démontrés à partir du bon ordre de \(\mathbb{N}\), dont l'existence du plus petit élément est admise.
Notations. Dans tout le chapitre, \(\mathbb{N}^* = \mathbb{N} \setminus \{0\}\), \(\mathbb{R}_+\) désigne l'ensemble des réels positifs, et pour des entiers \(a \le b\), \(\llbracket a, b \rrbracket = \{ k \in \mathbb{Z} \mid a \le k \le b \}\).
Notations. Dans tout le chapitre, \(\mathbb{N}^* = \mathbb{N} \setminus \{0\}\), \(\mathbb{R}_+\) désigne l'ensemble des réels positifs, et pour des entiers \(a \le b\), \(\llbracket a, b \rrbracket = \{ k \in \mathbb{Z} \mid a \le k \le b \}\).
Prérequis
Ce chapitre suppose connu le chapitre Raisonnement et démonstration : propositions et connecteurs (\(\neg\), et, ou, \(\Rightarrow\), \(\iff\)), tables de vérité, quantificateurs \(\forall\) et \(\exists\), structure d'une démonstration écrite, et les méthodes de démonstration qui y sont vues (démonstration directe, contraposée, disjonction des cas, contre-exemple, équivalence, absurde, récurrence simple). Les exemples et les exercices utilisent aussi : le calcul sur les réels (identités, inégalités, valeur absolue) ; les fonctions usuelles (puissances, racine carrée, exponentielle, logarithme, sinus, cosinus), les formules d'addition du sinus et du cosinus, leurs dérivées et leurs variations ; la continuité et le théorème des valeurs intermédiaires ; les suites définies par une relation de récurrence ; les sommes arithmétiques et géométriques ; la divisibilité des entiers (nombres pairs et impairs, nombres premiers, division euclidienne) ; le langage des ensembles du chapitre Théorie des ensembles (élément, inclusion, définition en compréhension, intersection, réunion, complémentaire).
I
Rédiger un texte mathématique
I.1
Vocabulaire : axiomes, définitions, théorèmes
Une démonstration est d'abord un texte, écrit pour un lecteur : elle a un vocabulaire, des verbes qui introduisent ses objets et une façon de parler des fonctions.
Pourquoi le vocabulaire compte
Une théorie mathématique est une tour d'énoncés vrais. En bas, quelques énoncés sont admis sans démonstration ; au-dessus, des mots reçoivent un sens précis ; tout autre énoncé se déduit de ce qui est en dessous de lui. Le vocabulaire d'un texte dit à quel étage vit chaque énoncé et, au dernier étage, quel rôle il joue : proposition, lemme, corollaire, caractérisation. Choisir le bon mot indique au lecteur, d'un coup d'œil, à quoi sert un énoncé.
Rien à un étage ne peut servir avant que les étages du dessous ne soient posés. Les quatre cases du dernier étage ne sont pas quatre sortes de vérité : ce sont quatre rôles que peut jouer un même type d'énoncé déduit. Le mot « proposition » a aussi un sens plus large : tout énoncé vrai ou faux ; le contexte tranche.
Définition — Axiome
Un axiome est une proposition acceptée comme vraie sans justification, prise comme point de départ d'une théorie. Par exemple, on admet en général l'existence de \(\mathbb{R}\) avec toutes les propriétés usuelles des nombres réels, plutôt que de construire \(\mathbb{R}\) à partir d'axiomes plus élémentaires. Définition — Définition
Une définition introduit un mot ou un symbole en précisant son sens mathématique exact. Elle peut nommer un objet, une classe d'objets, une propriété, une relation ou une opération. Dans une même portée active du raisonnement, un même symbole ne doit pas avoir deux significations. Définition — Théorème et ses variantes
Un théorème est une proposition dérivée des axiomes, des définitions et de résultats déjà établis. Quatre raffinements nomment le rôle joué par un théorème dans le développement : - une proposition est un théorème de portée modeste, généralement local à un chapitre ou à une section ;
- un lemme est un théorème préparatoire qui sert à découper un résultat plus gros en morceaux ;
- un corollaire est un théorème qui découle presque immédiatement d'un précédent ;
- une caractérisation est un théorème donnant une condition équivalente à une définition — au fond, une redéfinition alternative.
Exemple — Une définition et une caractérisation
Définition. Soient \(I\) un intervalle et \(f \colon I \to \mathbb{R}\) une fonction. On dit que \(f\) est croissante sur \(I\) si $$ \forall x, y \in I, \quad x < y \Rightarrow f(x) \le f(y). $$ Caractérisation. Soient \(I\) un intervalle non réduit à un point et \(f \colon I \to \mathbb{R}\) une fonction dérivable sur \(I\). Alors \(f\) est croissante sur \(I\) si et seulement si \(f'(x) \ge 0\) pour tout \(x \in I\).La définition fixe le sens du mot croissante avec la seule relation d'ordre de \(\mathbb{R}\). La caractérisation est un théorème : elle traduit ce sens en une condition sur \(f'\), ce qui ramène la preuve de la croissance de \(f\) à l'étude d'un signe.
Piège — pas d'homonymie
Dans un même raisonnement, chaque symbole a exactement une signification. Utiliser la lettre \(K\) pour deux quantités différentes dans la même démonstration crée une ambiguïté qui casse la rigueur : quand une seconde expression a besoin d'un nom court, on choisit une autre lettre. La langue courante tolère l'homonymie — le mot verre désigne à la fois une matière et l'objet dans lequel on boit — les mathématiques, non.
Compétences à pratiquer
- Reconnaître le statut d'un énoncé ★
- Rédiger des définitions et des énoncés ★★
I.2
Introduire un objet : Soit, On pose, On note
Pourquoi les introductions comptent
Première règle de la rédaction mathématique : tout objet dont on parle est d'abord introduit. Dans la langue courante, « Ils ont travaillé toute la soirée », dit avant que l'on sache qui sont « ils », n'apprend rien. En mathématiques de même, l'égalité \(\sin\left(x + \frac{\pi}{4}\right) = \frac{\sin x + \cos x}{\sqrt{2}}\), écrite avant d'avoir dit ce qu'est \(x\), n'a pas de sens. Trois verbes introduisent les objets, et ils ne sont pas interchangeables :
- Soit introduit une variable générique : un élément quelconque d'un ensemble donné. La variable vit jusqu'à la fin du raisonnement qui l'a introduite.
- On pose crée un nom nouveau, à gauche, pour une expression connue, à droite.
- On note donne un nom à un objet dont l'existence est déjà acquise.
Méthode — Introduire une variable générique
Pour démontrer une propriété de tout élément \(x\) d'un ensemble \(E\) : - Soit \(x \in E\).
- \(\vdots\) \(\quad\) (raisonner sur ce \(x\), en n'utilisant que \(x \in E\))
- Comme \(x\) est un élément quelconque de \(E\), la propriété vaut pour tout \(x \in E\).
Méthode — Nommer un objet précis : On pose ou On note
Pour donner un nom court \(K\) à une quantité construite avec des objets déjà introduits (ici \(\alpha \in \mathbb{R}\)) : - On pose \(K = \frac{e^\alpha + 1}{\alpha^2 + 1}\). \(\quad\) (le nom \(K\) est créé et lié à la valeur)
- On note \(K\) le réel \(\frac{e^\alpha + 1}{\alpha^2 + 1}\). \(\quad\) (le réel existe ; il reçoit un nom)
- le nouveau nom (\(K\)) n'est pas déjà utilisé dans le raisonnement ;
- le membre de droite n'utilise que des objets déjà introduits (\(\alpha\)).
Exemple — Deux ouvertures correctes et un indice muet
L'identité \(\sin\left(x + \frac{\pi}{4}\right) = \frac{\sin x + \cos x}{\sqrt{2}}\) vaut pour tout réel \(x\). Deux façons correctes de l'écrire, puis une lettre qui s'introduit seule : - Soit \(x \in \mathbb{R}\). Alors $$ \begin{aligned} \sin\left(x + \frac{\pi}{4}\right) &= \sin x \cos \frac{\pi}{4} + \cos x \sin \frac{\pi}{4} && \text{(formule d'addition)} \\ &= \sin x \cdot \frac{1}{\sqrt{2}} + \cos x \cdot \frac{1}{\sqrt{2}} && \text{(\(\cos \frac{\pi}{4} = \sin \frac{\pi}{4} = \frac{1}{\sqrt{2}}\))} \\ &= \frac{\sin x + \cos x}{\sqrt{2}}. \end{aligned} $$
- Pour tout \(x \in \mathbb{R}\), $$ \begin{aligned} \sin\left(x + \frac{\pi}{4}\right) &= \sin x \cos \frac{\pi}{4} + \cos x \sin \frac{\pi}{4} && \text{(formule d'addition)} \\ &= \sin x \cdot \frac{1}{\sqrt{2}} + \cos x \cdot \frac{1}{\sqrt{2}} && \text{(\(\cos \frac{\pi}{4} = \sin \frac{\pi}{4} = \frac{1}{\sqrt{2}}\))} \\ &= \frac{\sin x + \cos x}{\sqrt{2}}. \end{aligned} $$
- Dans une somme, une intégrale ou un ensemble, l'indice s'introduit tout seul : \(\sum_{k=1}^{n} \sqrt{k}\) ne demande pas de « Soit » pour \(k\). La lettre \(n\), en revanche, doit avoir été introduite avant.
Exemple — Noter sans expression
Quand l'objet a une expression, les deux verbes de la Méthode « Nommer un objet précis : On pose ou On note » conviennent, et la nouvelle lettre est à gauche : « On pose \(\frac{e^\alpha + 1}{\alpha^2 + 1} = K\) » cacherait le symbole que l'on introduit. Quand l'objet n'a pas d'expression, seul « On note » peut le nommer — une fois son existence démontrée.La fonction \(g \colon x \longmapsto e^x + x - 2\) est continue et strictement croissante sur \([0, 1]\), avec \(g(0) = -1 < 0\) et \(g(1) = e - 1 > 0\) : par le théorème des valeurs intermédiaires et la stricte monotonie, l'équation \(g(x) = 0\) a exactement une solution dans \([0, 1]\). Notons-la \(c\). Aucune expression de \(c\) avec les fonctions usuelles n'est disponible, donc « Posons \(c = \dots\) » est impossible ; « On note » est légitime parce que l'existence et l'unicité ont été démontrées d'abord.
Piège — l'existence demande une justification
Nommer un objet ne le fait pas exister. La phrase « On note \(N\) le plus grand entier strictement positif » présuppose qu'un tel \(N\) existe ; il n'existe pas (\(N + 1\) serait plus grand), et tout raisonnement qui part de ce \(N\) ne prouve rien. Avant « On note », l'existence de l'objet est évidente ou démontrée.
Compétences à pratiquer
- Choisir une entrée en matière ★
- Corriger une copie : introductions ★★
- Rédiger des introductions ★★
I.3
Rédiger avec les fonctions
Une fonction est un objet, pas une expression
L'expression \(e^x \sin x\) est un nombre réel qui dépend de \(x\) ; ce n'est pas une fonction. La fonction est la règle qui à \(x\) associe \(e^x \sin x\), notée \(x \longmapsto e^x \sin x\). La distinction compte : « la fonction \(e^x \sin x\) est dérivable » est incorrect ; la phrase correcte est « la fonction \(x \longmapsto e^x \sin x\) est dérivable sur \(\mathbb{R}\) ».
Méthode — Définir une fonction
Pour définir une fonction par une règle — ici de \(\mathbb{R}_+\) dans \(\mathbb{R}\) — quatre rédactions sont correctes : - On note \(f\) la fonction de \(\mathbb{R}_+\) dans \(\mathbb{R}\) définie par \(x \longmapsto \sqrt{x} + 1\).
- On note \(f\) la fonction \(\begin{cases} \mathbb{R}_+ \longrightarrow \mathbb{R} \\ x \longmapsto \sqrt{x} + 1 \end{cases}\).
- On note \(f \colon \mathbb{R}_+ \to \mathbb{R}\) la fonction définie pour tout \(x \in \mathbb{R}_+\) par \(f(x) = \sqrt{x} + 1\).
- On pose, pour tout \(x \in \mathbb{R}_+\), \(f(x) = \sqrt{x} + 1\), ce qui définit \(f \colon \mathbb{R}_+ \to \mathbb{R}\).
Méthode — Parler d'une fonction
Une fonction est continue, dérivable, croissante, bornée sur un ensemble ; elle peut aussi être dérivable en tout point d'un ensemble. La formule « pour tout \(x\) » ne s'accroche pas à la fonction \(x \longmapsto x^2\) : la fonction ne dépend pas de \(x\), la lettre est une variable muette de la règle. D'où : - Correct. La fonction \(x \longmapsto x^2\) est dérivable sur \(\mathbb{R}\).
- Correct. La fonction \(f\) est dérivable en tout point de \(\mathbb{R}\).
- À éviter. La fonction \(x \longmapsto x^2\) est dérivable pour tout \(x \in \mathbb{R}\).
Exemple — Calculer une dérivée proprement
Soit \(f \colon \mathbb{R} \to \mathbb{R}\), \(x \longmapsto e^{\sin(2x)}\). Dériver \(f\), avec une rédaction correcte.
La fonction \(x \longmapsto \sin(2x)\) est dérivable sur \(\mathbb{R}\), de dérivée \(x \longmapsto 2\cos(2x)\), et la fonction exponentielle est dérivable sur \(\mathbb{R}\) ; par composition, \(f\) est dérivable sur \(\mathbb{R}\). Pour tout \(x \in \mathbb{R}\), $$ \begin{aligned} f'(x) &= \frac{\mathrm{d}}{\mathrm{d}x}\bigl(\sin(2x)\bigr) \, e^{\sin(2x)} && \text{(dérivée d'une composée : \((e^u)' = u' e^u\))} \\
&= 2\cos(2x) \, e^{\sin(2x)}. \end{aligned} $$ La rédaction nomme la fonction, donne l'ensemble sur lequel elle est dérivable et introduit \(x\) avant d'écrire le nombre \(f'(x)\).
Piège — les deux flèches de fonction
\(\longrightarrow\) va d'ensemble à ensemble ; \(\longmapsto\) va d'élément à image. Écrire « \(x \longrightarrow e^{x^2}\) » pour décrire une fonction est incorrect : la règle qui à \(x\) associe son image utilise la flèche à talon, \(x \longmapsto e^{x^2}\). La flèche simple est réservée aux ensembles d'une fonction (\(f \colon \mathbb{R} \to \mathbb{R}\)) et aux limites (\(f(x) \to \ell\) quand \(x \to a\)).
Piège — la notation parenthèse prime
La notation \((f(x))'\) est à éviter : elle ne dit pas si l'on dérive la fonction \(f\) ou l'expression \(f(x)\), ni par rapport à quelle variable. La dérivée de \(f\) au point \(x\) s'écrit \(f'(x)\). Pour montrer la variable de dérivation, on utilise la notation de Leibniz \(\frac{\mathrm{d}}{\mathrm{d}x}\bigl(f(x)\bigr)\), surtout quand plusieurs lettres sont en jeu. Pour des fonctions \(u\) et \(v\), \((uv)'\) et \((e^u)'\) sont corrects : on y dérive une fonction, pas un nombre.
Compétences à pratiquer
- Distinguer une fonction d'une expression ★
- Corriger une copie : notation de fonction ★★
- Rédiger avec des fonctions ★★
II
Démontrer avec des quantificateurs
II.1
Propositions universelles et existentielles
Le quantificateur qui ouvre un énoncé dicte la première ligne de sa démonstration : « Soit » pour \(\forall\), « Posons » pour \(\exists\) ; l'unicité a son propre schéma.
Deux sortes de quantificateur
Une proposition universelle a la forme \(\forall x \in E, \ P(x)\) : « pour tout \(x\) de \(E\), la propriété \(P(x)\) est vraie ». Une proposition existentielle a la forme \(\exists x \in E, \ P(x)\) : « il existe \(x\) dans \(E\) tel que \(P(x)\) soit vraie ». Elles se démontrent par des mouvements opposés : une démonstration universelle commence par « Soit \(x \in E\) » et établit la propriété pour un \(x\) générique ; une démonstration existentielle exhibe un \(x\) précis et vérifie la propriété pour lui.
Méthode — Démontrer une proposition universelle
Pour démontrer \(\forall x \in E, \ P(x)\) : - Soit \(x \in E\). Montrons \(P(x)\).
- \(\vdots\) \(\quad\) (démonstration de \(P(x)\) pour ce \(x\) générique)
- Donc \(P(x)\). Comme \(x\) est quelconque dans \(E\), \(P(x)\) vaut pour tout \(x \in E\).
Exemple — Une inégalité universelle
Montrer que pour tout \(x \in \mathbb{R}\), \(\frac{x}{x^2 + 1} \le \frac{1}{2}\).
Soit \(x \in \mathbb{R}\). On étudie le signe de la différence. Un carré est positif et \(2(x^2 + 1) > 0\), donc $$ \begin{aligned} \frac{1}{2} - \frac{x}{x^2 + 1} &= \frac{x^2 + 1 - 2x}{2(x^2 + 1)} && \text{(même dénominateur, \(x^2 + 1 > 0\))} \\
&= \frac{(x - 1)^2}{2(x^2 + 1)} && \text{(identité \((a - b)^2 = a^2 - 2ab + b^2\))} \\
&\ge 0. \end{aligned} $$ Donc \(\frac{x}{x^2 + 1} \le \frac{1}{2}\), avec égalité exactement pour \(x = 1\). Comme \(x\) est un réel quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\).
Méthode — Démontrer une proposition existentielle
Pour démontrer \(\exists x \in E, \ P(x)\), on exhibe un \(x\) : - Posons \(x = \ldots\) \(\quad\) (le candidat explicite)
- Alors \(x \in E\), et \(P(x)\) est vraie : \(\vdots\) \(\quad\) (vérification pour ce \(x\))
- Donc il existe \(x \in E\) tel que \(P(x)\).
Exemple — Une existence qui dépend de paramètres
Montrer que pour tous \(x, y \in \mathbb{N}\), il existe \(z \in \mathbb{N}\) tel que \(\sqrt{z} > x + y\).
Soient \(x, y \in \mathbb{N}\). Posons \(z = (x + y + 1)^2\). Alors \(z \in \mathbb{N}\), comme carré d'un entier naturel, et $$ \begin{aligned} \sqrt{z} &= \sqrt{(x + y + 1)^2} && \text{(définition de \(z\))} \\
&= x + y + 1 && \text{(\(\sqrt{t^2} = t\) pour \(t \ge 0\), ici \(x + y + 1 \ge 1\))} \\
&> x + y. \end{aligned} $$ Donc \(z\) convient. Comme \(x\) et \(y\) sont quelconques dans \(\mathbb{N}\), pour tous \(x, y \in \mathbb{N}\) il existe \(z \in \mathbb{N}\) tel que \(\sqrt{z} > x + y\). Le candidat \(z\) est construit à partir de \(x\) et de \(y\), introduits avant lui.
Compétences à pratiquer
- Choisir le schéma d'un énoncé quantifié ★
- Démontrer des énoncés universels et existentiels ★★
- Démontrer des énoncés à quantificateurs alternés ★★★
II.2
Unicité
Deux sortes d'unicité
Deux énoncés sont à ne pas confondre :
- « Au plus un \(x \in E\) vérifie \(P\) » : l'unicité seule. Il n'affirme pas qu'un tel \(x\) existe ; il dit que s'il en existe un, il n'y en a qu'un.
- \(\exists ! \, x \in E, \ P(x)\), qui se lit « il existe un unique \(x\) » : l'existence et l'unicité.
Méthode — Démontrer l'unicité
Pour démontrer qu'au plus un \(x \in E\) vérifie \(P\) : - Soient \(x, x' \in E\) tels que \(P(x)\) et \(P(x')\). Montrons \(x = x'\).
- \(\vdots\) \(\quad\) (calcul, ou usage d'une propriété comme l'injectivité)
- Donc \(x = x'\) : au plus un élément de \(E\) vérifie \(P\).
Exemple — Existence et unicité d'une racine carrée positive
Soit \(a > 0\). Montrer qu'il existe un unique \(x \in \mathbb{R}_+\) tel que \(x^2 = a\).
Existence. La fonction \(g \colon t \longmapsto t^2 - a\) est continue sur \([0, a + 1]\), avec \(g(0) = -a < 0\) et \(g(a + 1) = a^2 + a + 1 > 0\). Par le théorème des valeurs intermédiaires, il existe \(x \in [0, a + 1]\) tel que \(g(x) = 0\), c'est-à-dire \(x^2 = a\) ; et \(x \in \mathbb{R}_+\).
Unicité. Soient \(x, x' \in \mathbb{R}_+\) tels que \(x^2 = a\) et \(x'^2 = a\). Montrons \(x = x'\). $$ \begin{aligned} (x - x')(x + x') &= x^2 - x'^2 && \text{(identité \((u - v)(u + v) = u^2 - v^2\))} \\ &= a - a && \text{(hypothèses sur \(x\) et \(x'\))} \\ &= 0. \end{aligned} $$ Comme \(x^2 = a > 0\), \(x \ne 0\) ; avec \(x \ge 0\) et \(x' \ge 0\), cela donne \(x + x' \ge x > 0\). Un produit de réels n'est nul que si l'un des facteurs est nul, donc \(x - x' = 0\), c'est-à-dire \(x = x'\).
Seconde méthode pour l'unicité. La fonction \(t \longmapsto t^2\) est strictement croissante sur \(\mathbb{R}_+\), donc deux éléments distincts de \(\mathbb{R}_+\) ont des carrés distincts ; comme \(x^2 = x'^2\), \(x = x'\).
Donc il existe un unique \(x \in \mathbb{R}_+\) tel que \(x^2 = a\) : c'est la racine carrée de \(a\), notée \(\sqrt{a}\). L'existence vient ici d'un théorème, pas d'un candidat explicite.
Unicité. Soient \(x, x' \in \mathbb{R}_+\) tels que \(x^2 = a\) et \(x'^2 = a\). Montrons \(x = x'\). $$ \begin{aligned} (x - x')(x + x') &= x^2 - x'^2 && \text{(identité \((u - v)(u + v) = u^2 - v^2\))} \\ &= a - a && \text{(hypothèses sur \(x\) et \(x'\))} \\ &= 0. \end{aligned} $$ Comme \(x^2 = a > 0\), \(x \ne 0\) ; avec \(x \ge 0\) et \(x' \ge 0\), cela donne \(x + x' \ge x > 0\). Un produit de réels n'est nul que si l'un des facteurs est nul, donc \(x - x' = 0\), c'est-à-dire \(x = x'\).
Seconde méthode pour l'unicité. La fonction \(t \longmapsto t^2\) est strictement croissante sur \(\mathbb{R}_+\), donc deux éléments distincts de \(\mathbb{R}_+\) ont des carrés distincts ; comme \(x^2 = x'^2\), \(x = x'\).
Donc il existe un unique \(x \in \mathbb{R}_+\) tel que \(x^2 = a\) : c'est la racine carrée de \(a\), notée \(\sqrt{a}\). L'existence vient ici d'un théorème, pas d'un candidat explicite.
Piège — au plus un n'est pas exactement un
« Au plus un » est l'unicité sans l'existence ; « exactement un », ou \(\exists !\), est l'existence et l'unicité. Écrire « au plus un » pour dire \(\exists !\) laisse la moitié « existence » implicite et non démontrée. Et montrer que deux objets possibles seraient égaux ne montre jamais qu'il en existe un : l'équation \(x^2 = -1\) a au plus une solution dans \(\mathbb{R}_+\), et elle n'en a aucune.
Compétences à pratiquer
- Distinguer « au plus un » et « exactement un » ★
- Démontrer l'unicité ★★
- Démontrer l'existence et l'unicité ★★★
III
Démontrer avec des connecteurs
III.1
Disjonction et disjonction des cas
Les connecteurs et leurs schémas de démonstration
Une proposition construite avec un connecteur — \(p\) ou \(q\), \(p \Rightarrow q\), \(p \iff q\), \(\neg p\) — a son propre schéma de démonstration, et un énoncé se réfute par un contre-exemple.
Méthode — Démontrer une disjonction
Les propositions « \(p\) ou \(q\) » et « \(\neg p \Rightarrow q\) » sont équivalentes. Pour démontrer « \(p\) ou \(q\) » : - Supposons \(p\) fausse. Montrons \(q\).
- \(\vdots\) \(\quad\) (démonstration de \(q\), en utilisant \(\neg p\))
- Donc \(q\). Ainsi « \(p\) ou \(q\) » est vraie.
Exemple — Un maximum minoré
Montrer que pour tout \(x \in \mathbb{R}\), \(\max\{x^2, (x - 2)^2\} \ge 1\).
Soit \(x \in \mathbb{R}\). L'énoncé à démontrer est la disjonction « \(x^2 \ge 1\) ou \((x - 2)^2 \ge 1\) ».
Supposons \(x^2 < 1\). Montrons \((x - 2)^2 \ge 1\). De \(x^2 < 1\) vient \(-1 < x < 1\), donc \(x - 2 < -1\) et \(|x - 2| > 1\). Par conséquent, la fonction carré étant strictement croissante sur \(\mathbb{R}_+\), \((x - 2)^2 = |x - 2|^2 > 1\).
Ainsi « \(x^2 \ge 1\) ou \((x - 2)^2 \ge 1\) » est vraie, c'est-à-dire \(\max\{x^2, (x - 2)^2\} \ge 1\). Comme \(x\) est quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\).
Seconde méthode, par disjonction des cas. Soit \(x \in \mathbb{R}\). On distingue deux cas, qui couvrent tous les réels. Cas \(x \ge 1\) : \(x^2 \ge 1\), la fonction carré étant croissante sur \(\mathbb{R}_+\). Cas \(x < 1\) : \(x - 2 < -1 \le 0\), donc \((x - 2)^2 \ge 1\), la fonction carré étant décroissante sur \(]-\infty, 0]\). Dans tous les cas, le maximum vaut au moins \(1\). Comme \(x\) est quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\).
Troisième méthode, sans cas. Soit \(x \in \mathbb{R}\). Un maximum vaut au moins la moyenne de ses deux termes, et un carré est positif, donc $$ \begin{aligned} \max\{x^2, (x - 2)^2\} &\ge \frac{x^2 + (x - 2)^2}{2} && \text{(un maximum majore chacun des termes)} \\ &= (x - 1)^2 + 1 && \text{(développement, forme canonique)} \\ &\ge 1. \end{aligned} $$ Comme \(x\) est quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\). La borne est atteinte en \(x = 1\), où les deux termes valent \(1\).
Supposons \(x^2 < 1\). Montrons \((x - 2)^2 \ge 1\). De \(x^2 < 1\) vient \(-1 < x < 1\), donc \(x - 2 < -1\) et \(|x - 2| > 1\). Par conséquent, la fonction carré étant strictement croissante sur \(\mathbb{R}_+\), \((x - 2)^2 = |x - 2|^2 > 1\).
Ainsi « \(x^2 \ge 1\) ou \((x - 2)^2 \ge 1\) » est vraie, c'est-à-dire \(\max\{x^2, (x - 2)^2\} \ge 1\). Comme \(x\) est quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\).
Seconde méthode, par disjonction des cas. Soit \(x \in \mathbb{R}\). On distingue deux cas, qui couvrent tous les réels. Cas \(x \ge 1\) : \(x^2 \ge 1\), la fonction carré étant croissante sur \(\mathbb{R}_+\). Cas \(x < 1\) : \(x - 2 < -1 \le 0\), donc \((x - 2)^2 \ge 1\), la fonction carré étant décroissante sur \(]-\infty, 0]\). Dans tous les cas, le maximum vaut au moins \(1\). Comme \(x\) est quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\).
Troisième méthode, sans cas. Soit \(x \in \mathbb{R}\). Un maximum vaut au moins la moyenne de ses deux termes, et un carré est positif, donc $$ \begin{aligned} \max\{x^2, (x - 2)^2\} &\ge \frac{x^2 + (x - 2)^2}{2} && \text{(un maximum majore chacun des termes)} \\ &= (x - 1)^2 + 1 && \text{(développement, forme canonique)} \\ &\ge 1. \end{aligned} $$ Comme \(x\) est quelconque, l'inégalité vaut pour tout \(x \in \mathbb{R}\). La borne est atteinte en \(x = 1\), où les deux termes valent \(1\).
Méthode — Raisonner par disjonction des cas
Pour démontrer une proposition \(P\) quand la situation se partage en cas \(C_1, \dots, C_r\) : - On distingue \(r\) cas, qui couvrent toutes les possibilités.
- Cas \(C_1\) : \(\vdots\) \(\quad\) donc \(P\). \(\quad \dots \quad\) Cas \(C_r\) : \(\vdots\) \(\quad\) donc \(P\).
- Dans tous les cas, \(P\) est vraie.
Exemple — Le reste d'un carré dans la division par 4
Montrer que pour tout \(n \in \mathbb{Z}\), le reste de la division euclidienne de \(n^2\) par \(4\) vaut \(0\) ou \(1\).
Soit \(n \in \mathbb{Z}\). Par la division euclidienne de \(n\) par \(2\), il existe \(m \in \mathbb{Z}\) tel que \(n = 2m\) ou \(n = 2m + 1\). On distingue ces deux cas, qui couvrent tous les entiers.
Cas \(n = 2m\). Alors \(n^2 = 4m^2 + 0\), avec \(m^2 \in \mathbb{Z}\) et \(0 \le 0 < 4\) : par unicité de la division euclidienne, le reste vaut \(0\).
Cas \(n = 2m + 1\). $$ \begin{aligned} n^2 &= 4m^2 + 4m + 1 && \text{(identité \((a + b)^2 = a^2 + 2ab + b^2\))} \\ &= 4(m^2 + m) + 1, \end{aligned} $$ avec \(m^2 + m \in \mathbb{Z}\) et \(0 \le 1 < 4\) : par unicité de la division euclidienne, le reste vaut \(1\).
Dans les deux cas, le reste de \(n^2\) dans la division par \(4\) vaut \(0\) ou \(1\). Comme \(n\) est quelconque, cela vaut pour tout \(n \in \mathbb{Z}\).
Cas \(n = 2m\). Alors \(n^2 = 4m^2 + 0\), avec \(m^2 \in \mathbb{Z}\) et \(0 \le 0 < 4\) : par unicité de la division euclidienne, le reste vaut \(0\).
Cas \(n = 2m + 1\). $$ \begin{aligned} n^2 &= 4m^2 + 4m + 1 && \text{(identité \((a + b)^2 = a^2 + 2ab + b^2\))} \\ &= 4(m^2 + m) + 1, \end{aligned} $$ avec \(m^2 + m \in \mathbb{Z}\) et \(0 \le 1 < 4\) : par unicité de la division euclidienne, le reste vaut \(1\).
Dans les deux cas, le reste de \(n^2\) dans la division par \(4\) vaut \(0\) ou \(1\). Comme \(n\) est quelconque, cela vaut pour tout \(n \in \mathbb{Z}\).
Compétences à pratiquer
- Distinguer des cas ★
- Démontrer une disjonction ou raisonner par cas ★★
III.2
Implication et contraposition
Ce que dit une implication
Une implication \(p \Rightarrow q\) ne dit rien de \(p\) elle-même : elle dit que chaque fois que \(p\) est vraie, \(q\) l'est aussi. Elle se démontre en supposant \(p\) et en en déduisant \(q\) — ou, quand \(p\) donne peu de prise, en démontrant l'implication équivalente \(\neg q \Rightarrow \neg p\), sa contraposée.
Méthode — Démontrer une implication
Pour démontrer \(p \Rightarrow q\) : - Supposons \(p\). Montrons \(q\).
- \(\vdots\) \(\quad\) (démonstration de \(q\), en utilisant \(p\))
- Donc \(q\). Ainsi \(p \Rightarrow q\) est vraie.
Exemple — Une implication qui restreint les solutions
Montrer que pour tout \(x \in [0, 1]\), \(x - x^2 \in \mathbb{Z} \Rightarrow x \in \{0, 1\}\).
Soit \(x \in [0, 1]\) tel que \(x - x^2 \in \mathbb{Z}\). Montrons \(x \in \{0, 1\}\).
Minoration. Comme \(x \in [0, 1]\), \(x \ge 0\) et \(1 - x \ge 0\). Un produit de deux nombres positifs étant positif, $$ \begin{aligned} x - x^2 &= x(1 - x) && \text{(factorisation)} \\ &\ge 0. \end{aligned} $$ Majoration. Un carré est positif, donc $$ \begin{aligned} x - x^2 &= \frac{1}{4} - \left(x - \frac{1}{2}\right)^2 && \text{(forme canonique)} \\ &\le \frac{1}{4}. \end{aligned} $$ Ainsi \(x - x^2\) est un entier de \(\left[0, \frac{1}{4}\right]\), donc \(x - x^2 = 0\), c'est-à-dire \(x(1 - x) = 0\) : \(x = 0\) ou \(x = 1\), car un produit n'est nul que si l'un de ses facteurs est nul.
Donc \(x \in \{0, 1\}\), et l'implication vaut pour tout \(x \in [0, 1]\). Les deux hypothèses ont servi — \(x - x^2 \in \mathbb{Z}\) pour l'entier, \(x \in [0, 1]\) pour la minoration — et la seconde ne peut pas être retirée : \(x = 2\) donne \(x - x^2 = -2 \in \mathbb{Z}\) et \(2 \notin \{0, 1\}\).
Minoration. Comme \(x \in [0, 1]\), \(x \ge 0\) et \(1 - x \ge 0\). Un produit de deux nombres positifs étant positif, $$ \begin{aligned} x - x^2 &= x(1 - x) && \text{(factorisation)} \\ &\ge 0. \end{aligned} $$ Majoration. Un carré est positif, donc $$ \begin{aligned} x - x^2 &= \frac{1}{4} - \left(x - \frac{1}{2}\right)^2 && \text{(forme canonique)} \\ &\le \frac{1}{4}. \end{aligned} $$ Ainsi \(x - x^2\) est un entier de \(\left[0, \frac{1}{4}\right]\), donc \(x - x^2 = 0\), c'est-à-dire \(x(1 - x) = 0\) : \(x = 0\) ou \(x = 1\), car un produit n'est nul que si l'un de ses facteurs est nul.
Donc \(x \in \{0, 1\}\), et l'implication vaut pour tout \(x \in [0, 1]\). Les deux hypothèses ont servi — \(x - x^2 \in \mathbb{Z}\) pour l'entier, \(x \in [0, 1]\) pour la minoration — et la seconde ne peut pas être retirée : \(x = 2\) donne \(x - x^2 = -2 \in \mathbb{Z}\) et \(2 \notin \{0, 1\}\).
Piège — la flèche d'implication n'est pas le mot donc
Le symbole \(\Rightarrow\) construit la proposition « \(p \Rightarrow q\) » ; ce n'est pas une abréviation de « donc ». Une copie fausse typique écrit $$ 0 \le x \le 1 \Rightarrow 0 \le x^2 \le 1 \Rightarrow 0 \le 1 - x^2 \le 1 \Rightarrow \sqrt{1 - x^2} \in [0, 1]. $$ Ce n'est pas une démonstration : \(x\) n'est pas introduit, et chaque flèche affirme une implication sans dire que son membre de gauche est vrai. Une copie correcte écrit : « Soit \(x \in [0, 1]\). La fonction carré étant croissante sur \(\mathbb{R}_+\), \(0 \le x^2 \le 1\). Donc \(0 \le 1 - x^2 \le 1\). La fonction racine carrée étant croissante sur \(\mathbb{R}_+\), \(0 \le \sqrt{1 - x^2} \le 1\), c'est-à-dire \(\sqrt{1 - x^2} \in [0, 1]\). » Dans le corps d'une démonstration, la flèche \(\Rightarrow\) est rare : le raisonnement s'articule avec des mots — donc, ainsi, par conséquent, d'où.
Méthode — Démontrer une implication par contraposée
L'implication \(p \Rightarrow q\) et sa contraposée \(\neg q \Rightarrow \neg p\) sont équivalentes. Pour démontrer \(p \Rightarrow q\) : - Montrons la contraposée : si \(\neg q\), alors \(\neg p\). Supposons \(\neg q\).
- \(\vdots\) \(\quad\) (démonstration de \(\neg p\), en utilisant \(\neg q\))
- Donc \(\neg p\). Puisque nous avons démontré la contraposée, \(p \Rightarrow q\) est vraie.
Exemple — Nombres de Mersenne
Soit \(n \ge 2\) un entier. Montrer que si \(2^n - 1\) est premier, alors \(n\) est premier.
Montrons la contraposée : si \(n\) n'est pas premier, alors \(2^n - 1\) n'est pas premier. Supposons \(n\) non premier. Comme \(n \ge 2\), \(n\) a un diviseur \(a\) tel que \(1 < a < n\) : il existe \(b \in \mathbb{N}^*\) tel que \(n = ab\). Posons \(x = 2^a\) ; alors \(x \ne 1\), et $$ \begin{aligned} 2^n - 1 &= x^b - 1 && \text{(\(2^{ab} = (2^a)^b\))} \\
&= (x - 1) \sum_{k=0}^{b-1} x^k && \text{(somme géométrique, \(x \ne 1\))} \\
&= (2^a - 1) \sum_{k=0}^{b-1} 2^{ak}. \end{aligned} $$ La somme est un entier naturel, donc \(2^a - 1\) divise \(2^n - 1\). De plus \(2 \le a < n\) donne \(3 \le 2^a - 1 < 2^n - 1\), la fonction \(t \longmapsto 2^t\) étant strictement croissante. Ainsi \(2^n - 1\) a un diviseur autre que \(1\) et lui-même : il n'est pas premier.
Donc \(2^n - 1\) n'est pas premier. Puisque nous avons démontré la contraposée, l'énoncé initial est vrai.
Contre-exemple à la réciproque : \(n = 11\). D'une part, \(11\) est premier ; d'autre part, \(2^{11} - 1 = 2047 = 23 \times 89\) n'est pas premier.
Donc \(2^n - 1\) n'est pas premier. Puisque nous avons démontré la contraposée, l'énoncé initial est vrai.
Contre-exemple à la réciproque : \(n = 11\). D'une part, \(11\) est premier ; d'autre part, \(2^{11} - 1 = 2047 = 23 \times 89\) n'est pas premier.
Compétences à pratiquer
- Écrire la contraposée ★
- Corriger une copie : implication et équivalence ★★
- Démontrer une implication ★★
- Choisir entre preuve directe et contraposée ★★★
III.3
Équivalence
Deux implications à la fois
Une équivalence \(p \iff q\) est deux implications à la fois, \(p \Rightarrow q\) et \(q \Rightarrow p\). Elle se démontre en un seul passage quand chaque étape peut être renversée, en deux passages sinon.
Méthode — Démontrer une équivalence
Deux approches : - Par double implication. (\(\Rightarrow\)) Supposons \(p\) ; \(\dots\) donc \(q\). (\(\Leftarrow\)) Supposons \(q\) ; \(\dots\) donc \(p\). Ainsi \(p \iff q\).
- Par une chaîne d'équivalences. \(p \iff r_1 \iff \dots \iff q\), écrite en chaîne alignée, la raison de chaque \(\iff\) sur sa ligne (celle de la dernière en prose).
Exemple — Une équivalence par une chaîne
Montrer que pour tous \(x, y \in \mathbb{R}\), \(x^2 + y^2 = 0 \iff (x = 0 \text{ et } y = 0)\).
Soient \(x, y \in \mathbb{R}\). Comme \(x^2 \ge 0\) et \(y^2 \ge 0\), et qu'une somme de réels positifs est nulle si et seulement si chacun d'eux est nul, $$ \begin{aligned} x^2 + y^2 = 0 &\iff \left(x^2 = 0 \text{ et } y^2 = 0\right) && \text{(somme de termes positifs)} \\
&\iff (x = 0 \text{ et } y = 0). \end{aligned} $$ Chaque étape est réversible et justifiée, la dernière par l'équivalence \(t^2 = 0 \iff t = 0\), valable pour tout \(t \in \mathbb{R}\). Comme \(x\) et \(y\) sont quelconques, l'équivalence vaut pour tous \(x, y \in \mathbb{R}\).
Seconde méthode : par double implication. Soient \(x, y \in \mathbb{R}\). (\(\Rightarrow\)) Supposons \(x^2 + y^2 = 0\). On a \(x^2 \ge 0\) et \(y^2 \ge 0\), et $$ \begin{aligned} x^2 &= -y^2 && \text{(hypothèse \(x^2 + y^2 = 0\))} \\ &\le 0. \end{aligned} $$ Donc \(x^2 = 0\), d'où \(x = 0\) ; de même \(y = 0\). (\(\Leftarrow\)) Si \(x = 0\) et \(y = 0\), alors \(x^2 + y^2 = 0\). Donc les deux énoncés sont équivalents. Comme \(x\) et \(y\) sont quelconques, l'équivalence vaut pour tous \(x, y \in \mathbb{R}\).
Seconde méthode : par double implication. Soient \(x, y \in \mathbb{R}\). (\(\Rightarrow\)) Supposons \(x^2 + y^2 = 0\). On a \(x^2 \ge 0\) et \(y^2 \ge 0\), et $$ \begin{aligned} x^2 &= -y^2 && \text{(hypothèse \(x^2 + y^2 = 0\))} \\ &\le 0. \end{aligned} $$ Donc \(x^2 = 0\), d'où \(x = 0\) ; de même \(y = 0\). (\(\Leftarrow\)) Si \(x = 0\) et \(y = 0\), alors \(x^2 + y^2 = 0\). Donc les deux énoncés sont équivalents. Comme \(x\) et \(y\) sont quelconques, l'équivalence vaut pour tous \(x, y \in \mathbb{R}\).
Piège — la double flèche n'est pas l'abréviation c.-à-d.
La double flèche \(\iff\) engage celui qui l'écrit dans les deux sens. Elle signifie « si et seulement si ». Pour réécrire un énoncé sous une forme plus claire, on emploie les mots « c'est-à-dire » ; on n'écrit \(\iff\) que lorsque la transformation est réversible, chaque \(\iff\) étant évident (\(x + 1 = 3 \iff x = 2\)) ou justifié. Le piège classique : \(x = 2 \Rightarrow x^2 = 4\) est vraie, mais \(x^2 = 4 \iff x = 2\) est fausse, puisque \(x = -2\) vérifie aussi \(x^2 = 4\).
Compétences à pratiquer
- Démontrer une équivalence ★★
- Démontrer une équivalence par deux implications ★★★
III.4
Négation et contre-exemple
Réfuter, c'est démontrer la négation
Réfuter un énoncé, c'est démontrer sa négation. Écrire cette négation est une méthode, pas une devinette : les quantificateurs s'échangent et la propriété finale est niée. La négation d'un énoncé universel est existentielle : un seul exemple suffit, un contre-exemple.
Méthode — Nier un énoncé quantifié
Pour écrire la négation d'un énoncé : - on change chaque \(\forall\) en \(\exists\) et chaque \(\exists\) en \(\forall\), en gardant leur ordre et leurs ensembles ;
- on nie la propriété finale, avec \(\neg(p \text{ et } q) \iff (\neg p \text{ ou } \neg q)\), \(\neg(p \text{ ou } q) \iff (\neg p \text{ et } \neg q)\) et \(\neg(p \Rightarrow q) \iff (p \text{ et } \neg q)\).
Méthode — Réfuter une implication
Pour réfuter \(\forall x \in E, \ p(x) \Rightarrow q(x)\), on démontre sa négation \(\exists x \in E, \ p(x) \text{ et } \neg q(x)\) : - Contre-exemple : \(x = \ldots\)
- D'une part, \(p(x)\) est vraie : \(\vdots\) ; d'autre part, \(q(x)\) est fausse : \(\vdots\)
- Donc l'énoncé est faux.
Exemple — Une implication fausse pour le sinus
Montrer que la proposition \(\forall x, y \in \mathbb{R}, \ x < y \Rightarrow \sin x \le \sin y\) est fausse.
La négation s'écrit : \(\exists x, y \in \mathbb{R}, \ x < y \text{ et } \sin x > \sin y\).
Contre-exemple : \(x = \frac{\pi}{2}\) et \(y = \pi\). D'une part, \(x < y\) ; d'autre part, \(\sin x = 1\) et \(\sin y = 0\), donc \(\sin x > \sin y\).
Donc la proposition est fausse : la fonction sinus n'est pas croissante sur \(\mathbb{R}\).
Contre-exemple : \(x = \frac{\pi}{2}\) et \(y = \pi\). D'une part, \(x < y\) ; d'autre part, \(\sin x = 1\) et \(\sin y = 0\), donc \(\sin x > \sin y\).
Donc la proposition est fausse : la fonction sinus n'est pas croissante sur \(\mathbb{R}\).
Compétences à pratiquer
- Nier un énoncé quantifié ★
- Trouver un contre-exemple ★
- Réfuter un énoncé ★★
IV
Démontrer une relation entre ensembles
IV.1
Inclusion et égalité
Des éléments aux ensembles
Un énoncé sur des ensembles est un énoncé sur leurs éléments : \(A \subset B\) signifie \(\forall x, \ x \in A \Rightarrow x \in B\), et \(A = B\) signifie \(A \subset B\) et \(B \subset A\). Une inclusion se démontre donc comme une implication universelle, avec un élément générique du plus petit ensemble ; une égalité, par deux inclusions ou par une chaîne d'équivalences.
Méthode — Démontrer une inclusion
Pour démontrer \(A \subset B\) : - Soit \(x \in A\).
- \(\vdots\) \(\quad\) (déduire \(x \in B\) de \(x \in A\), en dépliant les définitions)
- Donc \(x \in B\). Comme \(x\) est quelconque dans \(A\), \(A \subset B\).
Exemple — Une petite inclusion
Soit \(A = \{x \in \mathbb{R} \mid \exists y \in \mathbb{R}_+, \ x \ge y\}\). Montrer que \(A \subset \mathbb{R}_+\).
Soit \(x \in A\). Par définition de \(A\), \(x \in \mathbb{R}\) et il existe \(y \in \mathbb{R}_+\) tel que \(x \ge y\). Alors \(x \ge y \ge 0\), donc \(x \in \mathbb{R}_+\). Comme \(x\) est quelconque dans \(A\), \(A \subset \mathbb{R}_+\).
L'inclusion réciproque est vraie aussi : pour \(x \in \mathbb{R}_+\), \(y = 0\) est un témoin, car \(0 \in \mathbb{R}_+\) et \(x \ge 0\). Donc \(A = \mathbb{R}_+\), par double inclusion.
L'inclusion réciproque est vraie aussi : pour \(x \in \mathbb{R}_+\), \(y = 0\) est un témoin, car \(0 \in \mathbb{R}_+\) et \(x \ge 0\). Donc \(A = \mathbb{R}_+\), par double inclusion.
Méthode — Démontrer une égalité d'ensembles
Deux approches : - Par double inclusion. Démontrer \(A \subset B\) et \(B \subset A\), chacune par la Méthode « Démontrer une inclusion ».
- Par une chaîne d'équivalences. Pour \(x\) dans un ensemble qui contient \(A\) et \(B\), démontrer \(x \in A \iff \dots \iff x \in B\), chaque étape justifiée.
Exemple — Loi de De Morgan pour deux ensembles
Soient \(E\) un ensemble et \(A\), \(B\) deux parties de \(E\). Montrer que \(E \setminus (A \cup B) = (E \setminus A) \cap (E \setminus B)\).
Les deux ensembles sont des parties de \(E\). Soit \(x \in E\). $$ \begin{aligned} x \in E \setminus (A \cup B) &\iff x \notin A \cup B && \text{(définition du complémentaire, \(x \in E\))} \\
&\iff \neg\,(x \in A \text{ ou } x \in B) && \text{(définition de la réunion)} \\
&\iff (x \notin A \text{ et } x \notin B) && \text{(négation de « ou »)} \\
&\iff (x \in E \setminus A \text{ et } x \in E \setminus B) && \text{(définition du complémentaire, \(x \in E\))} \\
&\iff x \in (E \setminus A) \cap (E \setminus B). \end{aligned} $$ La dernière équivalence est la définition de l'intersection. Les deux ensembles ont les mêmes éléments dans \(E\), et ce sont deux parties de \(E\) : ils sont égaux.
Seconde méthode : par double inclusion.
(\(\subset\)) Soit \(x \in E \setminus (A \cup B)\) : \(x \in E\) et \(x \notin A \cup B\). Si \(x\) était dans \(A\), il serait dans \(A \cup B\) ; donc \(x \notin A\), et de même \(x \notin B\). Ainsi \(x \in E \setminus A\) et \(x \in E \setminus B\), c'est-à-dire \(x \in (E \setminus A) \cap (E \setminus B)\).
(\(\supset\)) Soit \(x \in (E \setminus A) \cap (E \setminus B)\) : \(x \in E\), \(x \notin A\) et \(x \notin B\). Un élément de \(A \cup B\) est dans \(A\) ou dans \(B\), donc \(x \notin A \cup B\), et \(x \in E \setminus (A \cup B)\).
Donc l'égalité, par double inclusion.
Seconde méthode : par double inclusion.
(\(\subset\)) Soit \(x \in E \setminus (A \cup B)\) : \(x \in E\) et \(x \notin A \cup B\). Si \(x\) était dans \(A\), il serait dans \(A \cup B\) ; donc \(x \notin A\), et de même \(x \notin B\). Ainsi \(x \in E \setminus A\) et \(x \in E \setminus B\), c'est-à-dire \(x \in (E \setminus A) \cap (E \setminus B)\).
(\(\supset\)) Soit \(x \in (E \setminus A) \cap (E \setminus B)\) : \(x \in E\), \(x \notin A\) et \(x \notin B\). Un élément de \(A \cup B\) est dans \(A\) ou dans \(B\), donc \(x \notin A \cup B\), et \(x \in E \setminus (A \cup B)\).
Donc l'égalité, par double inclusion.
Compétences à pratiquer
- Lire une inclusion ★
- Démontrer une inclusion, une égalité d'ensembles ★★
- Démontrer une identité ensembliste par double inclusion ★★★
V
Démontrer par récurrence
V.1
Bon ordre et récurrence simple
L'idée de la récurrence
Une propriété \(P_n\) de l'entier \(n\) ne peut pas se vérifier pour chaque \(n\) l'un après l'autre : \(\mathbb{N}\) est infini. La récurrence remplace une infinité de vérifications par deux : la propriété est vraie au départ, et elle passe de chaque entier au suivant. La récurrence n'est pas un axiome : elle se démontre à partir d'une propriété de \(\mathbb{N}\), l'existence d'un plus petit élément, et ses variantes aussi.
Proposition — Plus petit élément
Toute partie non vide \(A\) de \(\mathbb{N}\) possède un plus petit élément : il existe \(m \in A\) tel que \(m \le a\) pour tout \(a \in A\). Cet élément est unique ; on l'appelle le plus petit élément de \(A\).
L'existence est admise : c'est l'une des propriétés fondatrices de \(\mathbb{N}\), qu'une construction de \(\mathbb{N}\) prend pour axiome ou démontre, et dont partent les théorèmes de récurrence.
Unicité. Si \(m\) et \(m'\) sont deux plus petits éléments de \(A\), alors \(m \le m'\) et \(m' \le m\), donc \(m = m'\).
Cette propriété s'appelle le bon ordre de \(\mathbb{N}\). Elle est fausse dans \(\mathbb{Z}\), qui n'a pas de plus petit élément, et dans \(\mathbb{R}_+\), dont la partie \(]0, 1]\) n'en a pas.
Unicité. Si \(m\) et \(m'\) sont deux plus petits éléments de \(A\), alors \(m \le m'\) et \(m' \le m\), donc \(m = m'\).
Cette propriété s'appelle le bon ordre de \(\mathbb{N}\). Elle est fausse dans \(\mathbb{Z}\), qui n'a pas de plus petit élément, et dans \(\mathbb{R}_+\), dont la partie \(]0, 1]\) n'en a pas.
Théorème — Récurrence simple
Soit \(A \subset \mathbb{N}\). Si \(0 \in A\) et \(\forall n \in \mathbb{N}, \ n \in A \Rightarrow n + 1 \in A\), alors \(A = \mathbb{N}\).
Soit \(A \subset \mathbb{N}\) tel que \(0 \in A\) et \(n \in A \Rightarrow n + 1 \in A\) pour tout \(n \in \mathbb{N}\).
Supposons par l'absurde que \(A \ne \mathbb{N}\). Alors l'ensemble \(F = \mathbb{N} \setminus A\) des entiers hors de \(A\) est une partie non vide de \(\mathbb{N}\) ; par la Proposition « Plus petit élément », il possède un plus petit élément \(m\).
Comme \(m \in F\) et \(0 \in A\), \(m \ne 0\) ; donc \(m \ge 1\) et \(m - 1 \in \mathbb{N}\).
Comme \(m - 1 < m\) et que \(m\) est le plus petit élément de \(F\), \(m - 1 \notin F\), c'est-à-dire \(m - 1 \in A\).
L'hypothèse appliquée à \(n = m - 1\) donne \(m \in A\), c'est-à-dire \(m \notin F\) — alors que \(m \in F\).
Contradiction ! Donc l'hypothèse est fausse, et \(A = \mathbb{N}\).
Supposons par l'absurde que \(A \ne \mathbb{N}\). Alors l'ensemble \(F = \mathbb{N} \setminus A\) des entiers hors de \(A\) est une partie non vide de \(\mathbb{N}\) ; par la Proposition « Plus petit élément », il possède un plus petit élément \(m\).
Comme \(m \in F\) et \(0 \in A\), \(m \ne 0\) ; donc \(m \ge 1\) et \(m - 1 \in \mathbb{N}\).
Comme \(m - 1 < m\) et que \(m\) est le plus petit élément de \(F\), \(m - 1 \notin F\), c'est-à-dire \(m - 1 \in A\).
L'hypothèse appliquée à \(n = m - 1\) donne \(m \in A\), c'est-à-dire \(m \notin F\) — alors que \(m \in F\).
Contradiction ! Donc l'hypothèse est fausse, et \(A = \mathbb{N}\).
Méthode — Rédiger une récurrence simple
Pour démontrer \(\forall n \in \mathbb{N}, \ P_n\), on applique le Théorème « Récurrence simple » à \(A = \{n \in \mathbb{N} \mid P_n \text{ est vraie}\}\). La copie s'écrit : - Pour \(n \in \mathbb{N}\), notons \(P_n\) la propriété « … ».
- Initialisation. \(P_0\) est vraie car \(\dots\)
- Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_n\) (hypothèse de récurrence). Montrons \(P_{n+1}\). \(\vdots\) \(\quad\) (l'hypothèse de récurrence est citée là où elle sert) Donc \(P_{n+1}\).
- Conclusion. Puisque \(P_0\) est vraie et que \(P_n \Rightarrow P_{n+1}\) pour tout \(n \in \mathbb{N}\), par récurrence, \(P_n\) est vraie pour tout \(n \in \mathbb{N}\).
Méthode — Récurrence à partir d'un rang non nul
Soit \(n_0 \in \mathbb{N}\). Pour démontrer \(\forall n \ge n_0, \ P_n\) : - Initialisation. Montrer \(P_{n_0}\).
- Hérédité. Soit \(n \ge n_0\). Supposons \(P_n\). Montrons \(P_{n+1}\).
- Conclusion. Puisque \(P_{n_0}\) est vraie et que \(P_n \Rightarrow P_{n+1}\) pour tout \(n \ge n_0\), par récurrence à partir du rang \(n_0\), \(P_n\) est vraie pour tout \(n \ge n_0\).
Exemple — Une suite récurrente majorée
Soit \((a_n)_{n \in \mathbb{N}}\) définie par \(a_0 = 1\) et \(a_{n+1} = 1 + \frac{a_n}{n + 1}\) pour tout \(n \in \mathbb{N}\). Montrer que \(a_n \le 2\) pour tout \(n \in \mathbb{N}\).
L'inégalité dont l'hérédité a besoin ne vaut que pour \(n \ge 1\). On démontre donc \(a_n \le 2\) pour tout \(n \ge 1\) par récurrence à partir du rang \(1\), et l'on vérifie \(a_0\) à part : \(a_0 = 1 \le 2\).
Pour \(n \ge 1\), notons \(P_n\) la propriété « \(a_n \le 2\) ».
Initialisation. \(a_1 = 1 + \frac{a_0}{1} = 2\), donc \(P_1\) est vraie.
Hérédité. Soit \(n \ge 1\). Supposons \(P_n\). Montrons \(P_{n+1}\). $$ \begin{aligned} a_{n+1} &= 1 + \frac{a_n}{n + 1} && \text{(définition de la suite)} \\ &\le 1 + \frac{2}{n + 1} && \text{(hypothèse de récurrence, \(n + 1 > 0\))} \\ &\le 1 + \frac{2}{2} && \text{(\(n + 1 \ge 2\))} \\ &= 2. \end{aligned} $$ Donc \(P_{n+1}\).
Conclusion. Puisque \(P_1\) est vraie et que \(P_n \Rightarrow P_{n+1}\) pour tout \(n \ge 1\), par récurrence à partir du rang \(1\), \(a_n \le 2\) pour tout \(n \ge 1\) ; avec \(a_0 = 1\), \(a_n \le 2\) pour tout \(n \in \mathbb{N}\).
Pour \(n \ge 1\), notons \(P_n\) la propriété « \(a_n \le 2\) ».
Initialisation. \(a_1 = 1 + \frac{a_0}{1} = 2\), donc \(P_1\) est vraie.
Hérédité. Soit \(n \ge 1\). Supposons \(P_n\). Montrons \(P_{n+1}\). $$ \begin{aligned} a_{n+1} &= 1 + \frac{a_n}{n + 1} && \text{(définition de la suite)} \\ &\le 1 + \frac{2}{n + 1} && \text{(hypothèse de récurrence, \(n + 1 > 0\))} \\ &\le 1 + \frac{2}{2} && \text{(\(n + 1 \ge 2\))} \\ &= 2. \end{aligned} $$ Donc \(P_{n+1}\).
Conclusion. Puisque \(P_1\) est vraie et que \(P_n \Rightarrow P_{n+1}\) pour tout \(n \ge 1\), par récurrence à partir du rang \(1\), \(a_n \le 2\) pour tout \(n \ge 1\) ; avec \(a_0 = 1\), \(a_n \le 2\) pour tout \(n \in \mathbb{N}\).
Piège — l'hérédité porte sur un entier générique
L'hérédité démontre un énoncé universel : pour tout \(n \in \mathbb{N}\), \(P_n \Rightarrow P_{n+1}\). Elle s'ouvre donc comme toute démonstration universelle : « Soit \(n \in \mathbb{N}\). Supposons \(P_n\). » Deux autres ouvertures se rencontrent dans les copies. « Supposons \(P_n\) vraie pour tout \(n \in \mathbb{N}\) » est faux : c'est supposer ce qu'il faut démontrer, et il ne resterait rien à prouver. « Supposons \(P_n\) vraie pour un certain \(n\) » n'est acceptable que si \(n\) désigne un entier quelconque fixé : cela ne doit pas vouloir dire que l'on suppose seulement l'existence d'un rang où \(P_n\) est vraie. « Soit \(n \in \mathbb{N}\). Supposons \(P_n\). » le dit explicitement, c'est pourquoi on préfère cette ouverture.
Compétences à pratiquer
- Calculer à partir d'une définition par récurrence ★
- Corriger une copie : hérédité ★★
- Rédiger une récurrence simple ★★
- Trouver la bonne hypothèse de récurrence ★★★
V.2
Récurrences double et forte
Quand un rang ne suffit pas
Parfois \(P_{n+1}\) demande plus que \(P_n\) : les deux rangs précédents, pour une suite définie par \(u_{n+2} = a u_{n+1} + b u_n\) ; ou tous les rangs précédents, comme lorsque \(n + 1 = k \ell\) se décompose en deux facteurs plus petits. Les deux variantes découlent de la récurrence simple, appliquée à une propriété plus forte.
Théorème — Récurrence double
Soit \(A \subset \mathbb{N}\). Si \(0 \in A\), \(1 \in A\), et \(\forall n \in \mathbb{N}, \ (n \in A \text{ et } n + 1 \in A) \Rightarrow n + 2 \in A\), alors \(A = \mathbb{N}\).
Supposons par l'absurde que \(A \ne \mathbb{N}\). L'ensemble \(F = \mathbb{N} \setminus A\) est une partie non vide de \(\mathbb{N}\) ; par la Proposition « Plus petit élément », il possède un plus petit élément \(m\). Comme \(m \in F\) et \(0, 1 \in A\), \(m \ge 2\), donc \(m - 2\) et \(m - 1\) sont des entiers naturels.
Les entiers \(m - 2\) et \(m - 1\) sont plus petits que \(m\), donc ils ne sont pas dans \(F\) : \(m - 2 \in A\) et \(m - 1 \in A\).
L'hypothèse appliquée à \(n = m - 2\) donne \(m \in A\), c'est-à-dire \(m \notin F\) — alors que \(m \in F\).
Contradiction ! Donc l'hypothèse est fausse, et \(A = \mathbb{N}\).
Seconde démonstration, par récurrence simple. Soit \(B = \{n \in \mathbb{N} \mid n \in A \text{ et } n + 1 \in A\}\) ; on applique le Théorème « Récurrence simple » à \(B\).
\(0 \in B\), puisque \(0 \in A\) et \(1 \in A\).
Soit \(n \in \mathbb{N}\) tel que \(n \in B\) : \(n \in A\) et \(n + 1 \in A\). L'hypothèse donne \(n + 2 \in A\) ; ainsi \(n + 1 \in A\) et \(n + 2 \in A\), c'est-à-dire \(n + 1 \in B\).
Par récurrence simple, \(B = \mathbb{N}\). Tout \(n \in \mathbb{N}\) est alors dans \(B\), donc dans \(A\) : \(A = \mathbb{N}\).
Les entiers \(m - 2\) et \(m - 1\) sont plus petits que \(m\), donc ils ne sont pas dans \(F\) : \(m - 2 \in A\) et \(m - 1 \in A\).
L'hypothèse appliquée à \(n = m - 2\) donne \(m \in A\), c'est-à-dire \(m \notin F\) — alors que \(m \in F\).
Contradiction ! Donc l'hypothèse est fausse, et \(A = \mathbb{N}\).
Seconde démonstration, par récurrence simple. Soit \(B = \{n \in \mathbb{N} \mid n \in A \text{ et } n + 1 \in A\}\) ; on applique le Théorème « Récurrence simple » à \(B\).
\(0 \in B\), puisque \(0 \in A\) et \(1 \in A\).
Soit \(n \in \mathbb{N}\) tel que \(n \in B\) : \(n \in A\) et \(n + 1 \in A\). L'hypothèse donne \(n + 2 \in A\) ; ainsi \(n + 1 \in A\) et \(n + 2 \in A\), c'est-à-dire \(n + 1 \in B\).
Par récurrence simple, \(B = \mathbb{N}\). Tout \(n \in \mathbb{N}\) est alors dans \(B\), donc dans \(A\) : \(A = \mathbb{N}\).
Méthode — Rédiger une récurrence double
Pour démontrer \(\forall n \in \mathbb{N}, \ P_n\) quand \(P_{n+2}\) utilise à la fois \(P_n\) et \(P_{n+1}\) : - Initialisation. Montrer \(P_0\) et \(P_1\).
- Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_n\) et \(P_{n+1}\) (hypothèse de récurrence). Montrons \(P_{n+2}\).
- Conclusion. Puisque \(P_0\) et \(P_1\) sont vraies et que (\(P_n\) et \(P_{n+1}\)) \(\Rightarrow P_{n+2}\) pour tout \(n \in \mathbb{N}\), par récurrence double, \(P_n\) est vraie pour tout \(n \in \mathbb{N}\).
Exemple — Une formule explicite par récurrence double
Soit \((u_n)_{n \in \mathbb{N}}\) définie par \(u_0 = 4\), \(u_1 = 5\) et \(u_{n+2} = 3 u_{n+1} - 2 u_n\) pour tout \(n \in \mathbb{N}\). Montrer que \(u_n = 2^n + 3\) pour tout \(n \in \mathbb{N}\).
Pour \(n \in \mathbb{N}\), notons \(P_n\) la propriété « \(u_n = 2^n + 3\) ».
Initialisation. \(u_0 = 4 = 2^0 + 3\) et \(u_1 = 5 = 2^1 + 3\) : \(P_0\) et \(P_1\) sont vraies.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_n\) et \(P_{n+1}\). Montrons \(P_{n+2}\). $$ \begin{aligned} u_{n+2} &= 3 u_{n+1} - 2 u_n && \text{(définition de la suite)} \\ &= 3\left(2^{n+1} + 3\right) - 2\left(2^n + 3\right) && \text{(hypothèse de récurrence \(P_{n+1}\) et \(P_n\))} \\ &= 3 \cdot 2^{n+1} - 2^{n+1} + 3 && \text{(\(2 \cdot 2^n = 2^{n+1}\))} \\ &= 2^{n+2} + 3. \end{aligned} $$ Donc \(P_{n+2}\).
Conclusion. Puisque \(P_0\) et \(P_1\) sont vraies et que (\(P_n\) et \(P_{n+1}\)) \(\Rightarrow P_{n+2}\) pour tout \(n \in \mathbb{N}\), par récurrence double, \(u_n = 2^n + 3\) pour tout \(n \in \mathbb{N}\).
Seconde méthode : la formule trouvée, pas seulement vérifiée. Pour tout \(n \in \mathbb{N}\), $$ \begin{aligned} u_{n+2} - 2 u_{n+1} &= 3 u_{n+1} - 2 u_n - 2 u_{n+1} && \text{(définition de la suite)} \\ &= u_{n+1} - 2 u_n, \end{aligned} $$ donc la suite \((u_{n+1} - 2 u_n)_{n \in \mathbb{N}}\) est constante, égale à \(u_1 - 2 u_0 = -3\). Ainsi \(u_{n+1} = 2 u_n - 3\), c'est-à-dire \(u_{n+1} - 3 = 2(u_n - 3)\), pour tout \(n \in \mathbb{N}\) : la suite \((u_n - 3)_{n \in \mathbb{N}}\) est géométrique de raison \(2\) et de premier terme \(u_0 - 3 = 1\), donc \(u_n - 3 = 2^n\), c'est-à-dire \(u_n = 2^n + 3\). La récurrence double est devenue une récurrence simple, et la formule sort du calcul au lieu d'être donnée.
Initialisation. \(u_0 = 4 = 2^0 + 3\) et \(u_1 = 5 = 2^1 + 3\) : \(P_0\) et \(P_1\) sont vraies.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_n\) et \(P_{n+1}\). Montrons \(P_{n+2}\). $$ \begin{aligned} u_{n+2} &= 3 u_{n+1} - 2 u_n && \text{(définition de la suite)} \\ &= 3\left(2^{n+1} + 3\right) - 2\left(2^n + 3\right) && \text{(hypothèse de récurrence \(P_{n+1}\) et \(P_n\))} \\ &= 3 \cdot 2^{n+1} - 2^{n+1} + 3 && \text{(\(2 \cdot 2^n = 2^{n+1}\))} \\ &= 2^{n+2} + 3. \end{aligned} $$ Donc \(P_{n+2}\).
Conclusion. Puisque \(P_0\) et \(P_1\) sont vraies et que (\(P_n\) et \(P_{n+1}\)) \(\Rightarrow P_{n+2}\) pour tout \(n \in \mathbb{N}\), par récurrence double, \(u_n = 2^n + 3\) pour tout \(n \in \mathbb{N}\).
Seconde méthode : la formule trouvée, pas seulement vérifiée. Pour tout \(n \in \mathbb{N}\), $$ \begin{aligned} u_{n+2} - 2 u_{n+1} &= 3 u_{n+1} - 2 u_n - 2 u_{n+1} && \text{(définition de la suite)} \\ &= u_{n+1} - 2 u_n, \end{aligned} $$ donc la suite \((u_{n+1} - 2 u_n)_{n \in \mathbb{N}}\) est constante, égale à \(u_1 - 2 u_0 = -3\). Ainsi \(u_{n+1} = 2 u_n - 3\), c'est-à-dire \(u_{n+1} - 3 = 2(u_n - 3)\), pour tout \(n \in \mathbb{N}\) : la suite \((u_n - 3)_{n \in \mathbb{N}}\) est géométrique de raison \(2\) et de premier terme \(u_0 - 3 = 1\), donc \(u_n - 3 = 2^n\), c'est-à-dire \(u_n = 2^n + 3\). La récurrence double est devenue une récurrence simple, et la formule sort du calcul au lieu d'être donnée.
Théorème — Récurrence forte
Soit \(A \subset \mathbb{N}\). Si \(0 \in A\) et \(\forall n \in \mathbb{N}, \ \left(\forall k \in \llbracket 0, n \rrbracket, \ k \in A\right) \Rightarrow n + 1 \in A\), alors \(A = \mathbb{N}\).
Soit \(A \subset \mathbb{N}\) vérifiant les deux hypothèses.
Supposons par l'absurde que \(A \ne \mathbb{N}\). L'ensemble \(F = \mathbb{N} \setminus A\) est une partie non vide de \(\mathbb{N}\) ; par la Proposition « Plus petit élément », il possède un plus petit élément \(m\). Comme \(m \in F\) et \(0 \in A\), \(m \ge 1\), donc \(m - 1 \in \mathbb{N}\).
Tout \(k \in \llbracket 0, m - 1 \rrbracket\) vérifie \(k < m\), donc \(k \notin F\) par minimalité de \(m\), c'est-à-dire \(k \in A\).
L'hypothèse appliquée à \(n = m - 1\) donne alors \(m \in A\), c'est-à-dire \(m \notin F\) — alors que \(m \in F\).
Contradiction ! Donc l'hypothèse est fausse, et \(A = \mathbb{N}\).
Seconde démonstration, par récurrence simple. Soit \(B = \{n \in \mathbb{N} \mid \llbracket 0, n \rrbracket \subset A\}\).
\(0 \in B\), puisque \(\llbracket 0, 0 \rrbracket = \{0\} \subset A\).
Soit \(n \in \mathbb{N}\) tel que \(n \in B\) : \(\llbracket 0, n \rrbracket \subset A\), donc l'hypothèse donne \(n + 1 \in A\), et \(\llbracket 0, n + 1 \rrbracket = \llbracket 0, n \rrbracket \cup \{n + 1\} \subset A\), c'est-à-dire \(n + 1 \in B\).
Par récurrence simple, \(B = \mathbb{N}\). Tout \(n \in \mathbb{N}\) vérifie alors \(n \in \llbracket 0, n \rrbracket \subset A\), donc \(A = \mathbb{N}\).
Supposons par l'absurde que \(A \ne \mathbb{N}\). L'ensemble \(F = \mathbb{N} \setminus A\) est une partie non vide de \(\mathbb{N}\) ; par la Proposition « Plus petit élément », il possède un plus petit élément \(m\). Comme \(m \in F\) et \(0 \in A\), \(m \ge 1\), donc \(m - 1 \in \mathbb{N}\).
Tout \(k \in \llbracket 0, m - 1 \rrbracket\) vérifie \(k < m\), donc \(k \notin F\) par minimalité de \(m\), c'est-à-dire \(k \in A\).
L'hypothèse appliquée à \(n = m - 1\) donne alors \(m \in A\), c'est-à-dire \(m \notin F\) — alors que \(m \in F\).
Contradiction ! Donc l'hypothèse est fausse, et \(A = \mathbb{N}\).
Seconde démonstration, par récurrence simple. Soit \(B = \{n \in \mathbb{N} \mid \llbracket 0, n \rrbracket \subset A\}\).
\(0 \in B\), puisque \(\llbracket 0, 0 \rrbracket = \{0\} \subset A\).
Soit \(n \in \mathbb{N}\) tel que \(n \in B\) : \(\llbracket 0, n \rrbracket \subset A\), donc l'hypothèse donne \(n + 1 \in A\), et \(\llbracket 0, n + 1 \rrbracket = \llbracket 0, n \rrbracket \cup \{n + 1\} \subset A\), c'est-à-dire \(n + 1 \in B\).
Par récurrence simple, \(B = \mathbb{N}\). Tout \(n \in \mathbb{N}\) vérifie alors \(n \in \llbracket 0, n \rrbracket \subset A\), donc \(A = \mathbb{N}\).
Méthode — Rédiger une récurrence forte
Pour démontrer \(\forall n \in \mathbb{N}, \ P_n\) quand \(P_{n+1}\) peut utiliser n'importe lequel des \(P_0, \dots, P_n\) : - Initialisation. Montrer \(P_0\).
- Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_k\) pour tout \(k \in \llbracket 0, n \rrbracket\) (hypothèse de récurrence forte). Montrons \(P_{n+1}\).
- Conclusion. Puisque \(P_0\) est vraie et que (\(P_0, \dots, P_n\)) \(\Rightarrow P_{n+1}\) pour tout \(n \in \mathbb{N}\), par récurrence forte, \(P_n\) est vraie pour tout \(n \in \mathbb{N}\).
Exemple — Une majoration par la somme des termes précédents
Soit \((v_n)_{n \in \mathbb{N}}\) une suite réelle telle que \(v_0 \ge 0\) et \(v_{n+1} \le \sum_{k=0}^{n} v_k\) pour tout \(n \in \mathbb{N}\). Montrer que \(v_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\).
Pour \(n \in \mathbb{N}\), notons \(P_n\) la propriété « \(v_n \le 2^n v_0\) ».
Initialisation. \(v_0 = 2^0 v_0\), donc \(P_0\) est vraie.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_k\) pour tout \(k \in \llbracket 0, n \rrbracket\). Montrons \(P_{n+1}\). Comme \(v_0 \ge 0\), $$ \begin{aligned} v_{n+1} &\le \sum_{k=0}^{n} v_k && \text{(hypothèse sur la suite)} \\ &\le \sum_{k=0}^{n} 2^k v_0 && \text{(hypothèse de récurrence forte, pour chaque \(k \in \llbracket 0, n \rrbracket\))} \\ &= \left(2^{n+1} - 1\right) v_0 && \text{(somme géométrique)} \\ &\le 2^{n+1} v_0. \end{aligned} $$ Donc \(P_{n+1}\).
Conclusion. Puisque \(P_0\) est vraie et que (\(P_0, \dots, P_n\)) \(\Rightarrow P_{n+1}\) pour tout \(n \in \mathbb{N}\), par récurrence forte, \(v_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\). L'hérédité utilise tous les rangs précédents à la fois : une récurrence simple sur \(P_n\) seule ne suffirait pas.
Seconde méthode : une récurrence simple sur les sommes partielles. Pour \(n \in \mathbb{N}\), posons \(S_n = \sum_{k=0}^{n} v_k\). Pour tout \(n \in \mathbb{N}\), comme \(v_{n+1} \le S_n\) par hypothèse, $$ \begin{aligned} S_{n+1} &= S_n + v_{n+1} && \text{(dernier terme à part)} \\ &\le 2 S_n. \end{aligned} $$ Pour \(n \in \mathbb{N}\), notons \(Q_n\) la propriété « \(S_n \le 2^n v_0\) ».
Initialisation. \(S_0 = v_0 = 2^0 v_0\), donc \(Q_0\) est vraie.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(Q_n\). Montrons \(Q_{n+1}\). $$ \begin{aligned} S_{n+1} &\le 2 S_n && \text{(ci-dessus)} \\ &\le 2 \cdot 2^n v_0 && \text{(hypothèse de récurrence)} \\ &= 2^{n+1} v_0. \end{aligned} $$ Donc \(Q_{n+1}\).
Conclusion. Puisque \(Q_0\) est vraie et que \(Q_n \Rightarrow Q_{n+1}\) pour tout \(n \in \mathbb{N}\), par récurrence, \(S_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\).
Enfin, comme \(v_0 \ge 0\), pour tout \(n \in \mathbb{N}\), $$ \begin{aligned} v_{n+1} &\le S_n && \text{(hypothèse sur la suite)} \\ &\le 2^n v_0 && \text{(propriété \(Q_n\))} \\ &\le 2^{n+1} v_0. \end{aligned} $$ Avec \(v_0 = 2^0 v_0\), \(v_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\). La somme \(S_n\) porte tous les rangs précédents en un seul nombre : une récurrence simple suffit, et elle donne même \(v_{n+1} \le 2^n v_0\).
Initialisation. \(v_0 = 2^0 v_0\), donc \(P_0\) est vraie.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P_k\) pour tout \(k \in \llbracket 0, n \rrbracket\). Montrons \(P_{n+1}\). Comme \(v_0 \ge 0\), $$ \begin{aligned} v_{n+1} &\le \sum_{k=0}^{n} v_k && \text{(hypothèse sur la suite)} \\ &\le \sum_{k=0}^{n} 2^k v_0 && \text{(hypothèse de récurrence forte, pour chaque \(k \in \llbracket 0, n \rrbracket\))} \\ &= \left(2^{n+1} - 1\right) v_0 && \text{(somme géométrique)} \\ &\le 2^{n+1} v_0. \end{aligned} $$ Donc \(P_{n+1}\).
Conclusion. Puisque \(P_0\) est vraie et que (\(P_0, \dots, P_n\)) \(\Rightarrow P_{n+1}\) pour tout \(n \in \mathbb{N}\), par récurrence forte, \(v_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\). L'hérédité utilise tous les rangs précédents à la fois : une récurrence simple sur \(P_n\) seule ne suffirait pas.
Seconde méthode : une récurrence simple sur les sommes partielles. Pour \(n \in \mathbb{N}\), posons \(S_n = \sum_{k=0}^{n} v_k\). Pour tout \(n \in \mathbb{N}\), comme \(v_{n+1} \le S_n\) par hypothèse, $$ \begin{aligned} S_{n+1} &= S_n + v_{n+1} && \text{(dernier terme à part)} \\ &\le 2 S_n. \end{aligned} $$ Pour \(n \in \mathbb{N}\), notons \(Q_n\) la propriété « \(S_n \le 2^n v_0\) ».
Initialisation. \(S_0 = v_0 = 2^0 v_0\), donc \(Q_0\) est vraie.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(Q_n\). Montrons \(Q_{n+1}\). $$ \begin{aligned} S_{n+1} &\le 2 S_n && \text{(ci-dessus)} \\ &\le 2 \cdot 2^n v_0 && \text{(hypothèse de récurrence)} \\ &= 2^{n+1} v_0. \end{aligned} $$ Donc \(Q_{n+1}\).
Conclusion. Puisque \(Q_0\) est vraie et que \(Q_n \Rightarrow Q_{n+1}\) pour tout \(n \in \mathbb{N}\), par récurrence, \(S_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\).
Enfin, comme \(v_0 \ge 0\), pour tout \(n \in \mathbb{N}\), $$ \begin{aligned} v_{n+1} &\le S_n && \text{(hypothèse sur la suite)} \\ &\le 2^n v_0 && \text{(propriété \(Q_n\))} \\ &\le 2^{n+1} v_0. \end{aligned} $$ Avec \(v_0 = 2^0 v_0\), \(v_n \le 2^n v_0\) pour tout \(n \in \mathbb{N}\). La somme \(S_n\) porte tous les rangs précédents en un seul nombre : une récurrence simple suffit, et elle donne même \(v_{n+1} \le 2^n v_0\).
Compétences à pratiquer
- Rédiger une récurrence double ou forte ★★
- Choisir la récurrence ★★★
VI
Raisonner par l'absurde, par analyse-synthèse
VI.1
Raisonnement par l'absurde
L'absurde démontre qu'une chose ne peut pas arriver ; l'analyse-synthèse trouve toutes les solutions d'un problème.
L'idée
Pour démontrer \(p\) par l'absurde, on suppose \(\neg p\) et l'on aboutit à une contradiction : un énoncé \(q\) accompagné de sa négation \(\neg q\). L'hypothèse \(\neg p\) est alors fausse, donc \(p\) est vraie. La méthode convient aux énoncés qui disent qu'une chose n'existe pas ou ne peut pas arriver — une irrationalité, une impossibilité : leur négation fournit un objet sur lequel travailler.
Méthode — Rédiger un raisonnement par l'absurde
Pour démontrer \(p\) : - Supposons par l'absurde que \(\neg p\).
- \(\vdots\) \(\quad\) (aboutir à un énoncé \(q\) et à sa négation \(\neg q\))
- Contradiction ! Donc l'hypothèse est fausse, et \(p\) est vraie.
Exemple — Une racine carrée qui n'est jamais entière
Montrer que pour tout \(n \in \mathbb{N}\), \(\sqrt{n^2 + 2}\) n'est pas un entier.
Soit \(n \in \mathbb{N}\). Supposons par l'absurde que \(\sqrt{n^2 + 2}\) est un entier ; notons-le \(p\). Alors \(p \in \mathbb{N}\) et \(p^2 = n^2 + 2\). Un carré laisse le reste \(0\) ou \(1\) dans la division par \(4\) (Exemple « Le reste d'un carré dans la division par 4 ») : \(n^2 = 4q + r\) avec \(q \in \mathbb{Z}\) et \(r \in \{0, 1\}\), donc $$ \begin{aligned} p^2 &= n^2 + 2 && \text{(définition de \(p\))} \\
&= 4q + (r + 2), \end{aligned} $$ avec \(0 \le r + 2 < 4\) : par unicité de la division euclidienne, le reste de \(p^2\) dans la division par \(4\) vaut \(r + 2\), c'est-à-dire \(2\) ou \(3\). Or \(p^2\) est un carré, donc ce reste vaut \(0\) ou \(1\).
Contradiction ! Donc l'hypothèse est fausse : \(\sqrt{n^2 + 2}\) n'est pas un entier. Comme \(n\) est quelconque, cela vaut pour tout \(n \in \mathbb{N}\).
Seconde méthode : entre deux carrés consécutifs. Soit \(n \in \mathbb{N}\). Si \(n \ge 1\), alors \(n^2 < n^2 + 2\) et $$ \begin{aligned} n^2 + 2 &< n^2 + 2n + 1 && \text{(\(2 < 2n + 1\), car \(n \ge 1\))} \\ &= (n + 1)^2. \end{aligned} $$ Si \(n = 0\), alors \(1^2 < 2 < 2^2\). Ainsi \(n^2 + 2\) est strictement compris entre les carrés de deux entiers consécutifs \(k\) et \(k + 1\) (\(k = n\) si \(n \ge 1\), \(k = 1\) si \(n = 0\)). La fonction racine carrée étant strictement croissante sur \(\mathbb{R}_+\), \(k < \sqrt{n^2 + 2} < k + 1\), et aucun entier n'est strictement compris entre \(k\) et \(k + 1\). Donc \(\sqrt{n^2 + 2}\) n'est pas un entier. Comme \(n\) est quelconque, cela vaut pour tout \(n \in \mathbb{N}\).
Contradiction ! Donc l'hypothèse est fausse : \(\sqrt{n^2 + 2}\) n'est pas un entier. Comme \(n\) est quelconque, cela vaut pour tout \(n \in \mathbb{N}\).
Seconde méthode : entre deux carrés consécutifs. Soit \(n \in \mathbb{N}\). Si \(n \ge 1\), alors \(n^2 < n^2 + 2\) et $$ \begin{aligned} n^2 + 2 &< n^2 + 2n + 1 && \text{(\(2 < 2n + 1\), car \(n \ge 1\))} \\ &= (n + 1)^2. \end{aligned} $$ Si \(n = 0\), alors \(1^2 < 2 < 2^2\). Ainsi \(n^2 + 2\) est strictement compris entre les carrés de deux entiers consécutifs \(k\) et \(k + 1\) (\(k = n\) si \(n \ge 1\), \(k = 1\) si \(n = 0\)). La fonction racine carrée étant strictement croissante sur \(\mathbb{R}_+\), \(k < \sqrt{n^2 + 2} < k + 1\), et aucun entier n'est strictement compris entre \(k\) et \(k + 1\). Donc \(\sqrt{n^2 + 2}\) n'est pas un entier. Comme \(n\) est quelconque, cela vaut pour tout \(n \in \mathbb{N}\).
Compétences à pratiquer
- Reconnaître un raisonnement par l'absurde ★
- Raisonner par l'absurde ★★
- Démontrer une impossibilité ★★★
VI.2
Analyse-synthèse
La méthode du détective
Pour trouver tous les objets qui vérifient une condition, l'analyse-synthèse procède en deux passages, comme un détective. Analyse : on suppose qu'un objet vérifie la condition et l'on en déduit ce qu'il doit être — une condition nécessaire, qui réduit le champ à un ensemble de candidats : quelques valeurs, ou une famille dépendant d'un paramètre. Synthèse : on détermine les candidats qui vérifient vraiment la condition — une condition suffisante. Les solutions sont exactement les candidats que garde la synthèse.
Méthode — Rédiger une démonstration par analyse-synthèse
Pour déterminer les éléments de \(E\) qui vérifient \(P\) : - Analyse. Soit \(x \in E\) vérifiant \(P\). \(\vdots\) \(\quad\) (conditions nécessaires) Donc \(x \in C\), où \(C \subset E\) est un ensemble de candidats : quelques valeurs \(c_1, \dots, c_r\), ou une famille dépendant d'un paramètre.
- Synthèse. Réciproquement, on détermine les éléments de \(C\) qui vérifient \(P\) : on teste chaque valeur, ou \(P\) devient une condition sur le paramètre.
- Conclusion. L'ensemble des solutions est exactement l'ensemble des éléments de \(C\) qui vérifient \(P\).
Exemple — Résoudre une équation avec une racine carrée
Déterminer les réels \(x\) tels que \(\sqrt{x + 2} = x\).
L'équation est définie pour \(x \ge -2\).
Analyse. Soit \(x \ge -2\) tel que \(\sqrt{x + 2} = x\). Comme un produit est nul si et seulement si l'un de ses facteurs est nul, $$ \begin{aligned} \sqrt{x + 2} = x &\Rightarrow x + 2 = x^2 && \text{(élévation au carré)} \\ &\iff (x - 2)(x + 1) = 0 && \text{(factorisation)} \\ &\iff (x = 2 \text{ ou } x = -1). \end{aligned} $$ Donc \(x = 2\) ou \(x = -1\).
Synthèse. Pour \(x = 2\) : \(\sqrt{2 + 2} = 2\), donc \(2\) est solution. Pour \(x = -1\) : \(\sqrt{-1 + 2} = 1 \ne -1\), donc \(-1\) n'est pas solution.
Conclusion. L'ensemble des solutions est \(\{2\}\). L'élévation au carré est une implication, pas une équivalence : elle a fait entrer le candidat \(-1\), que la synthèse écarte.
Seconde méthode : une chaîne d'équivalences. L'élévation au carré devient réversible dès que les deux membres sont positifs : pour \(a, b \ge 0\), \(a = b \iff a^2 = b^2\). Comme \(\sqrt{x + 2} \ge 0\), pour tout \(x \ge -2\), $$ \begin{aligned} \sqrt{x + 2} = x &\iff \left(x \ge 0 \text{ et } x + 2 = x^2\right) && \text{(\(\sqrt{x + 2} \ge 0\), puis élévation au carré)} \\ &\iff \left(x \ge 0 \text{ et } (x - 2)(x + 1) = 0\right) && \text{(factorisation)} \\ &\iff x = 2. \end{aligned} $$ La dernière équivalence vient du produit nul, la valeur \(-1\) étant exclue par \(x \ge 0\). L'ensemble des solutions est \(\{2\}\). La condition \(x \ge 0\), écrite dès la première ligne, fait le travail de la synthèse.
Analyse. Soit \(x \ge -2\) tel que \(\sqrt{x + 2} = x\). Comme un produit est nul si et seulement si l'un de ses facteurs est nul, $$ \begin{aligned} \sqrt{x + 2} = x &\Rightarrow x + 2 = x^2 && \text{(élévation au carré)} \\ &\iff (x - 2)(x + 1) = 0 && \text{(factorisation)} \\ &\iff (x = 2 \text{ ou } x = -1). \end{aligned} $$ Donc \(x = 2\) ou \(x = -1\).
Synthèse. Pour \(x = 2\) : \(\sqrt{2 + 2} = 2\), donc \(2\) est solution. Pour \(x = -1\) : \(\sqrt{-1 + 2} = 1 \ne -1\), donc \(-1\) n'est pas solution.
Conclusion. L'ensemble des solutions est \(\{2\}\). L'élévation au carré est une implication, pas une équivalence : elle a fait entrer le candidat \(-1\), que la synthèse écarte.
Seconde méthode : une chaîne d'équivalences. L'élévation au carré devient réversible dès que les deux membres sont positifs : pour \(a, b \ge 0\), \(a = b \iff a^2 = b^2\). Comme \(\sqrt{x + 2} \ge 0\), pour tout \(x \ge -2\), $$ \begin{aligned} \sqrt{x + 2} = x &\iff \left(x \ge 0 \text{ et } x + 2 = x^2\right) && \text{(\(\sqrt{x + 2} \ge 0\), puis élévation au carré)} \\ &\iff \left(x \ge 0 \text{ et } (x - 2)(x + 1) = 0\right) && \text{(factorisation)} \\ &\iff x = 2. \end{aligned} $$ La dernière équivalence vient du produit nul, la valeur \(-1\) étant exclue par \(x \ge 0\). L'ensemble des solutions est \(\{2\}\). La condition \(x \ge 0\), écrite dès la première ligne, fait le travail de la synthèse.
Exemple — Une équation fonctionnelle
Déterminer les fonctions \(f \colon \mathbb{R} \to \mathbb{R}\) telles que pour tous \(x, y \in \mathbb{R}\), \(f(y - f(x)) = 2 - x - y\).
Analyse. Soit \(f \colon \mathbb{R} \to \mathbb{R}\) vérifiant l'équation. Soit \(x \in \mathbb{R}\) ; l'équation avec \(y = f(x)\) donne \(f(0) = 2 - x - f(x)\), c'est-à-dire \(f(x) = \lambda - x\) avec \(\lambda = 2 - f(0)\), une constante. Donc \(f\) est de la forme \(x \longmapsto \lambda - x\) pour un certain \(\lambda \in \mathbb{R}\).
Synthèse. Soient \(\lambda \in \mathbb{R}\) et \(f \colon x \longmapsto \lambda - x\). Pour tous \(x, y \in \mathbb{R}\), $$ \begin{aligned} f(y - f(x)) &= f(y - \lambda + x) && \text{(\(f(x) = \lambda - x\))} \\ &= \lambda - (y - \lambda + x) && \text{(définition de \(f\))} \\ &= 2\lambda - x - y. \end{aligned} $$ Donc \(f\) vérifie l'équation si et seulement si \(2\lambda - x - y = 2 - x - y\) pour tous \(x, y \in \mathbb{R}\), c'est-à-dire \(\lambda = 1\).
Conclusion. L'équation a exactement une solution : la fonction \(x \longmapsto 1 - x\).
Synthèse. Soient \(\lambda \in \mathbb{R}\) et \(f \colon x \longmapsto \lambda - x\). Pour tous \(x, y \in \mathbb{R}\), $$ \begin{aligned} f(y - f(x)) &= f(y - \lambda + x) && \text{(\(f(x) = \lambda - x\))} \\ &= \lambda - (y - \lambda + x) && \text{(définition de \(f\))} \\ &= 2\lambda - x - y. \end{aligned} $$ Donc \(f\) vérifie l'équation si et seulement si \(2\lambda - x - y = 2 - x - y\) pour tous \(x, y \in \mathbb{R}\), c'est-à-dire \(\lambda = 1\).
Conclusion. L'équation a exactement une solution : la fonction \(x \longmapsto 1 - x\).
Pourquoi l'analyse-synthèse donne toutes les solutions
L'analyse démontre « toute solution est l'un des candidats » ; la synthèse décide quels candidats sont solutions. Ensemble, elles donnent l'ensemble exact des solutions, qui peut être vide, un singleton ou plus grand. Dans l'équation \(\sqrt{x + 2} = x\), l'analyse laisse deux candidats et la synthèse en garde un ; dans l'équation fonctionnelle \(f(y - f(x)) = 2 - x - y\), l'analyse laisse la famille \(x \longmapsto \lambda - x\) et la synthèse fixe \(\lambda = 1\). L'unicité n'est une conclusion de la méthode que lorsqu'un seul candidat survit.
Pour aller plus loin
La descente infinie. La Proposition « Plus petit élément » interdit une suite strictement décroissante d'entiers naturels : l'ensemble de ses termes serait une partie non vide de \(\mathbb{N}\) sans plus petit élément. Fermat en a tiré une méthode, la descente infinie : pour montrer qu'aucun entier naturel n'a une propriété, on montre qu'à partir de tout entier naturel qui l'a, on en construit un strictement plus petit qui l'a aussi. Par exemple, \(\sqrt{2}\) est irrationnel. Soit \(A = \left\{p \in \mathbb{N}^* \mid \exists q \in \mathbb{N}^*, \ \sqrt{2} = \frac{p}{q}\right\}\) et supposons par l'absurde que \(A\) n'est pas vide ; soient \(p\) son plus petit élément et \(q \in \mathbb{N}^*\) tel que \(\sqrt{2} = \frac{p}{q}\). Alors \(p^2 = 2q^2\) est pair, donc \(p\) est pair, le carré d'un entier impair étant impair : \(p = 2p'\) avec \(p' \in \mathbb{N}^*\). Alors \(4p'^2 = 2q^2\), c'est-à-dire \(q^2 = 2p'^2\), et \(\sqrt{2} = \frac{q}{p'}\) : donc \(q \in A\). Or \(\sqrt{2} > 1\) donne \(q < p\), ce qui contredit la minimalité de \(p\). Contradiction ! Donc l'hypothèse est fausse, et \(A\) est vide. Comme \(\sqrt{2} > 0\), une fraction égale à \(\sqrt{2}\) s'écrirait \(\frac{p}{q}\) avec \(p, q \in \mathbb{N}^*\) : donc \(\sqrt{2}\) est irrationnel.
Compétences à pratiquer
- Trouver le candidat ★
- Raisonner par analyse-synthèse ★★
- Résoudre une équation fonctionnelle ★★★
VII
Exercices de colle
Compétences à pratiquer
- Travailler un exercice de colle ★
- Travailler un exercice de colle ★★
- Travailler un exercice de colle ★★★
- Travailler un exercice de colle ★★★★
VIII
Problèmes d'écrit
Compétences à pratiquer
- Travailler un problème d'écrit ★
- Travailler un problème d'écrit ★★
- Travailler un problème d'écrit ★★★
- Travailler un problème d'écrit ★★★★
- Quiz
Devoir facile : les tours de puissances
3 exercices, sur 20 points. Durée indicative : 1 h 30.
À traiter sur papier, puis à photographier : la correction est automatique, par IA.
Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.
Aucun exercice composé.
Devoir difficile : un encadrement du nombre de nombres premiers
3 exercices, sur 20 points. Durée indicative : 3 h.
À traiter sur papier, puis à photographier : la correction est automatique, par IA.
Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.
Aucun exercice composé.
Aller à la section