CommeUnJeu · L1 MPSI

Logique

⌚ ~266 min ▢ 31 blocs ✓ 98 exercices ➣ Prérequis : Raisonnement et Démonstration

Ce chapitre traite du langage que nous utilisons pour faire des mathématiques. Nous avons tous déjà rédigé des démonstrations, et nous avons tous dit « si $p$ alors $q$ », « pour tout $x$ », « il existe ». Ce chapitre resserre la vis. On cesse de traiter ces locutions comme des tournures informelles ; on les traite comme des objets mathématiques à part entière. Un connecteur, c'est quelque chose que l'on va définir rigoureusement par sa table de vérité ; un quantificateur, c'est quelque chose dont la négation s'énonce comme un théorème ; une implication, c'est quelque chose que l'on saura réfuter, en exhibant un seul contre-exemple explicite.
Cette rigueur supplémentaire a deux bénéfices. D'abord, elle élimine les ambiguïtés que le langage vague véhicule inévitablement : quand on écrit $\neg(p \implies q)$, on saura exactement de quoi on parle, et on saura comment l'attaquer. Ensuite, elle nous donne un vocabulaire petit et fini --- cinq connecteurs, deux quantificateurs, quatre modes de raisonnement, trois variantes de récurrence --- qui suffit pour l'année entière de mathématiques qui suit. À la fin de ce chapitre, toute démonstration que nous lirons devrait tenir dans ce moule.
On utilise V (Vrai) et F (Faux) comme les deux valeurs de vérité tout au long. Le chapitre se déploie en cinq temps : on construit d'abord les connecteurs à partir de leurs tables de vérité, on les assemble ensuite en tautologies et dans le langage des conditions nécessaires et suffisantes, on introduit ensuite les quantificateurs et leur règle de négation, puis on recense les quatre modes de raisonnement classiques, et l'on termine par la récurrence et ses trois variantes.

I Propositions et connecteurs

Une proposition est un énoncé dont la valeur de vérité est l'une des deux valeurs V (vrai) ou F (faux). Les opérations que l'on peut construire sur les propositions --- négation, conjonction, disjonction, implication, équivalence --- sont appelées connecteurs logiques. L'idée décisive de cette section est que chaque connecteur est entièrement décrit par sa table de vérité : la donnée de son comportement sur toutes les combinaisons de valeurs de vérité de ses entrées. Une fois la table en main, on a le connecteur ; tout le reste --- De Morgan, la négation d'une implication, l'équivalence d'une implication avec sa contraposée --- se lit directement sur la table.

I.1 Propositions et valeurs de vérité

On commence au tout début. Avant les connecteurs, avant les quantificateurs, l'objet atomique de la logique est la proposition : un énoncé auquel on attribue exactement une valeur de vérité. L'objet de cette courte sous-section est de tracer une ligne claire entre deux choses que l'on confond parfois : une proposition (qui a une valeur de vérité telle qu'écrite) et un prédicat (qui dépend d'une variable libre et n'acquiert une valeur de vérité qu'une fois cette variable fixée). La distinction sera essentielle dès que l'on écrira $\forall x$ et $\exists x$ dans la section sur les quantificateurs.

Définition — Proposition$\virgule$ valeur de vérité$\virgule$ prédicat

Une proposition est un énoncé déclaratif auquel on peut attribuer exactement l'une des deux valeurs de vérité V (vrai) ou F (faux). On note les propositions par des lettres minuscules $p, q, r, \dots$. Une proposition n'est jamais simultanément V et F ; c'est le principe de non-contradiction, que l'on adopte comme loi primitive du discours mathématique.
Un énoncé qui dépend d'une variable libre, par exemple « $n$ est pair » ou « $f(x) > 0$ », est appelé prédicat. Un prédicat n'a pas de valeur de vérité tel quel ; il n'en acquiert une qu'une fois la variable fixée.

Exemple

Chaque ligne ci-dessous est une proposition de la valeur de vérité indiquée :

$p$ : « $7$ est un nombre premier » --- valeur V.
$q$ : « $\sqrt{2}$ est un nombre rationnel » --- valeur F.
$s$ : « $\pi > 3$ » --- valeur V.
$t$ : « $0 = 1$ » --- valeur F.

Exemple

Considérons le prédicat $r(n) = $ « $n$ est pair ». Tel quel, $r$ n'a pas de valeur de vérité : $n$ n'est pas précisé. Mais dès qu'on substitue une valeur particulière à $n$, le prédicat devient une proposition :

$r(4)$ : « $4$ est pair » --- valeur V.
$r(5)$ : « $5$ est pair » --- valeur F.
$r(0)$ : « $0$ est pair » --- valeur V.

Il en va de même pour tout prédicat. La phrase « $f$ est croissante » est un prédicat de $f$ ; la phrase « la fonction $x \mapsto x^2$ est croissante sur $\mathbb{R}_+$ » est une proposition (et sa valeur est V).

Compétences à pratiquer

Déterminer la valeur de vérité d'une proposition
Distinguer proposition et prédicat

I.2 Négation$\virgule$ conjonction$\virgule$ disjonction

Nous construisons à présent les trois connecteurs les plus simples : la négation (à une entrée), la conjonction et la disjonction (à deux entrées). Chacun est présenté de la même façon : une définition par table de vérité, un exemple pour ancrer l'intuition, et l'on passe au suivant. La récompense arrive en fin de sous-section : les deux lois de De Morgan, qui décrivent la manière dont la négation se distribue sur les deux autres connecteurs. De Morgan est le premier théorème du chapitre --- un énoncé que l'on peut démontrer, simplement en lisant des tables de vérité.

Définition — Négation

La négation d'une proposition $p$, notée $\neg p$ (lue « non $p$ »), est la proposition dont la valeur de vérité est l'opposée de celle de $p$. Sa table de vérité est :

$p$	$\neg p$
V	F
F	V

Exemple

Nier une inégalité la rend stricte :

la négation de « $x \ge 0$ » est « $x < 0$ » (pas « $x \le 0$ »).
la négation de « $x = 1$ » est « $x \ne 1$ ».
la négation de « $f$ est croissante » est « $f$ n'est pas croissante » --- ce qui n'est pas la même chose que « $f$ est décroissante ». Une fonction peut être ni l'une ni l'autre.

Le troisième point est le piège : la négation d'une propriété est l'absence de cette propriété, pas la propriété opposée.

Définition — Conjonction

La conjonction de deux propositions $p$ et $q$, notée $p \wedge q$ (lue « $p$ et $q$ »), est vraie lorsque $p$ et $q$ sont vraies toutes les deux, et fausse sinon. Sa table de vérité est :

$p$	$q$	$p \wedge q$
V	V	V
V	F	F
F	V	F
F	F	F

Exemple

Pour un entier $n$, soit $p$ : « $n$ est multiple de $2$ » et $q$ : « $n$ est multiple de $3$ ». La conjonction $p \wedge q$ est « $n$ est multiple de $2$ et de $3$ », ce qui revient à « $n$ est multiple de $6$ » : $$ \big( 2 \mid n \big) \wedge \big( 3 \mid n \big) \ \Longleftrightarrow \ 6 \mid n. $$ La conjonction exprime la simultanéité de deux contraintes ; en arithmétique, c'est le PPCM qui la capture.

Définition — Disjonction

La disjonction de deux propositions $p$ et $q$, notée $p \vee q$ (lue « $p$ ou $q$ »), est vraie lorsque au moins l'une de $p$ ou $q$ est vraie, et fausse sinon. C'est le « ou » inclusif : $p$ seul, $q$ seul, ou les deux, sont acceptés. Sa table de vérité est :

$p$	$q$	$p \vee q$
V	V	V
V	F	V
F	V	V
F	F	F

Exemple

Pour un réel $x$, la disjonction « $x \le -1$ ou $x \ge 1$ » décrit la réunion de deux demi-droites fermées : $$ \{ x \in \mathbb{R} \mid x \le -1 \vee x \ge 1 \} = \mathbb{R} \setminus \, ]-1, 1[ = ]-\infty, -1] \cup [1, +\infty[. $$ La disjonction exprime l'alternative entre deux cas ; en géométrie, c'est la réunion des deux régions.

Proposition — Lois de De Morgan

Pour toutes propositions $p$ et $q$, on a les équivalences : $$ \neg (p \wedge q) \ \Longleftrightarrow \ (\neg p) \vee (\neg q) \qquad \neg (p \vee q) \ \Longleftrightarrow \ (\neg p) \wedge (\neg q). $$

Preuve

On démontre la première équivalence par table de vérité ; la seconde s'obtient de la même manière.

$p$	$q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p$	$\neg q$	$\neg p \vee \neg q$
V	V	V	F	F	F	F
V	F	F	V	F	V	V
F	V	F	V	V	F	V
F	F	F	V	V	V	V

Les colonnes $\neg(p \wedge q)$ et $\neg p \vee \neg q$ coïncident sur chaque ligne : les deux propositions ont la même valeur de vérité dans tous les cas, elles sont donc équivalentes.

Exemple

La négation de « $x \le 1$ et $x \ge -1$ » est, par De Morgan, « $x > 1$ ou $x < -1$ ». Géométriquement : le complémentaire d'un intervalle fermé est la réunion des deux demi-droites ouvertes extérieures. $$ \neg \big( -1 \le x \le 1 \big) \ \Longleftrightarrow \ x < -1 \vee x > 1. $$

Compétences à pratiquer

Calculer la négation d'une inégalité
Évaluer une proposition composée
Appliquer les lois de De Morgan

I.3 Implication et équivalence

De tous les connecteurs, l'implication est celui que l'on manie le plus mal. Le point de confusion est la convention selon laquelle une implication d'hypothèse fausse est automatiquement vraie --- fait qui heurte l'intuition courante (« si les cochons volent, alors $0 = 1$ » : oui, c'est vrai). Cette convention est nécessaire : tout théorème de la forme $\forall x \in E, \mathcal{P}(x) \implies \mathcal{Q}(x)$ serait sans elle faux pour tout $x$ ne vérifiant pas $\mathcal{P}$, et l'énoncé universel s'effondrerait. Une fois la convention admise, la table de vérité est simple : une implication $p \implies q$ est fausse dans un seul cas, à savoir $p$ vraie et $q$ fausse.
La même sous-section introduit l'équivalence ($p \iff q$, deux implications), la contraposée ($\neg q \implies \neg p$) et la réciproque ($q \implies p$). Le fait crucial, démontré en Proposition ci-dessous, est qu'une implication et sa contraposée ont toujours la même valeur de vérité --- tandis qu'une implication et sa réciproque, en général, non. Nous exploiterons cette asymétrie chaque fois que nous choisirons de raisonner par contraposition.

Définition — Implication

L'implication de $p$ vers $q$, notée $p \implies q$ (lue « si $p$, alors $q$ » ou « $p$ implique $q$ »), est la proposition qui est fausse uniquement lorsque $p$ est vraie et $q$ est fausse ; elle est vraie dans tous les autres cas. En particulier, une implication d'hypothèse fausse est automatiquement vraie. Sa table de vérité :

$p$	$q$	$p \implies q$
V	V	V
V	F	F
F	V	V
F	F	V

Exemple

L'implication « $0 = 1 \implies 1 = 1 $ » est vraie. L'hypothèse $0 = 1$ est fausse, donc par convention l'implication est vraie quelle que soit la conclusion. On parle de vérité par défaut : l'implication tient pour la raison triviale qu'aucune instance n'est à tester.
L'implication « $0 = 1 \implies 0 = 2$ » est elle aussi vraie, pour la même raison. Le principe est inconfortable mais inévitable : d'une hypothèse fausse, tout se déduit.

Définition — Équivalence$\virgule$ contraposée$\virgule$ réciproque

Soient $p$ et $q$ deux propositions.

L'équivalence de $p$ et $q$, notée $p \iff q$, est la proposition $(p \implies q) \wedge (q \implies p)$ : elle est vraie exactement lorsque $p$ et $q$ ont la même valeur de vérité.
La contraposée de $p \implies q$ est l'implication $(\neg q) \implies (\neg p)$.
La réciproque de $p \implies q$ est l'implication $q \implies p$.

La table de vérité de l'équivalence est :

$p$	$q$	$p \iff q$
V	V	V
V	F	F
F	V	F
F	F	V

Exemple

Pour un réel $x$ fixé, l'implication « $x = 1 \implies x^2 = 1$ » est vraie : de $x = 1$, on élève au carré et l'on obtient $x^2 = 1$.
Sa réciproque est « $x^2 = 1 \implies x = 1$ ». Elle est fausse : pour $x = -1$, on a $x^2 = 1$ mais $x \ne 1$. L'exemple $x = -1$ est un contre-exemple à la réciproque.
Cela montre qu'une implication et sa réciproque sont indépendantes : connaître l'une ne dit rien sur l'autre. À l'inverse, une implication et sa contraposée s'accordent toujours --- fait que nous démontrons à présent.

Proposition — Équivalence avec la contraposée

Pour toutes propositions $p$ et $q$ : $$ \big( p \implies q \big) \ \Longleftrightarrow \ \big( (\neg q) \implies (\neg p) \big). $$ Une implication et sa contraposée ont toujours la même valeur de vérité. La réciproque, en revanche, n'est en général pas équivalente à l'implication initiale.

Preuve

Table de vérité :

$p$	$q$	$p \implies q$	$\neg q$	$\neg p$	$\neg q \implies \neg p$
V	V	V	F	F	V
V	F	F	V	F	F
F	V	V	F	V	V
F	F	V	V	V	V

Les colonnes $p \implies q$ et $\neg q \implies \neg p$ coïncident sur chaque ligne.

Proposition — Négation d'une implication

Pour toutes propositions $p$ et $q$ : $$ \neg ( p \implies q ) \ \Longleftrightarrow \ p \wedge (\neg q). $$ La négation de « si $p$ alors $q$ » est « $p$ et non $q$ » --- l'unique configuration dans laquelle l'implication est fausse.

Preuve

Par table de vérité :

$p$	$q$	$p \implies q$	$\neg(p \implies q)$	$\neg q$	$p \wedge \neg q$
V	V	V	F	F	F
V	F	F	V	V	V
F	V	V	F	F	F
F	F	V	F	V	F

Les colonnes $\neg(p \implies q)$ et $p \wedge \neg q$ coïncident.

Exemple

L'implication « s'il pleut, alors le sol est mouillé » est par exemple fausse un jour où il pleut mais où le sol est abrité (il pleut et le sol n'est pas mouillé). Elle est en revanche vraie un jour ensoleillé avec une pelouse mouillée par l'arrosage : l'hypothèse « il pleut » étant fausse, l'implication est automatiquement vraie.

Compétences à pratiquer

Déterminer la valeur de vérité d'une implication
Écrire la contraposée et la réciproque
Nier une implication

II Tautologies et équivalences logiques

Avec les connecteurs et leurs propriétés de base, on peut grimper d'un cran en abstraction. Une formule bâtie à partir de variables propositionnelles et de connecteurs est une tautologie lorsqu'elle est vraie quelles que soient les valeurs de vérité attribuées à ses variables. Les tautologies sont les lois de la logique ; elles décrivent exactement les manipulations que l'on s'autorise sur les propositions sans risquer la moindre fausseté.
Cette section comporte trois parties. On définit ce qu'est une tautologie et l'on vérifie la plus célèbre (la loi du tiers exclu, $p \vee \neg p$). On rassemble ensuite les quatre autres tautologies que l'on utilisera le plus dans l'année qui suit. On clôt par le vocabulaire mathématique standard --- conditions nécessaire et suffisante --- qui n'est essentiellement qu'une relecture de l'implication et de sa contraposée en langage humainement lisible.

II.1 Tautologies

Une tautologie est une formule propositionnelle vraie sur chaque ligne de sa table de vérité. L'exemple le plus simple non trivial est $p \vee \neg p$ --- entre $p$ et sa négation, l'une des deux est forcément V. L'opposé d'une tautologie est une antilogie : une formule fausse sur chaque ligne. Le plus simple est $p \wedge \neg p$, faux partout puisque $p$ ne peut être simultanément V et F. Ces deux formules sont les bornes de la logique propositionnelle : entre les deux vivent toutes les formules dont la valeur de vérité dépend des variables d'entrée.

Définition — Tautologie$\virgule$ antilogie$\virgule$ équivalence logique

Une tautologie est une formule propositionnelle qui prend la valeur V sur toutes les lignes de sa table de vérité --- c'est-à-dire indépendamment des valeurs de vérité de ses variables propositionnelles. Une antilogie est une formule qui prend la valeur F sur toutes les lignes.
Deux formules $A$ et $B$ sont dites logiquement équivalentes lorsque $A \iff B$ est une tautologie. De manière équivalente, $A$ et $B$ ont la même valeur de vérité sur chaque ligne.

Exemple

La formule $p \vee \neg p$ est le célèbre tiers exclu : toute proposition est soit vraie, soit fausse, sans troisième option. La formule $p \wedge \neg p$ est une contradiction (toujours fausse) ; sa négation $\neg(p \wedge \neg p)$ est le principe de non-contradiction (toujours vraie). Table de vérité commune :

$p$	$\neg p$	$p \vee \neg p$	$p \wedge \neg p$
V	F	V	F
F	V	V	F

Exemple

Une tautologie non triviale, que l'on retrouvera à la sous-section suivante : $\big( (p \implies q) \wedge p \big) \implies q$. Table de vérité :

$p$	$q$	$p \implies q$	$(p \implies q) \wedge p$	$\big((p\implies q) \wedge p\big) \implies q$
V	V	V	V	V
V	F	F	F	V
F	V	V	F	V
F	F	V	F	V

La dernière colonne vaut V partout : la formule est une tautologie --- c'est le modus ponens. À l'inverse, la formule $p \implies q$ n'est pas une tautologie (elle vaut F à la ligne 2) : sa valeur dépend de $p$ et $q$.

Compétences à pratiquer

Vérifier une tautologie par table de vérité

II.2 Tautologies classiques

On rassemble ici les quatre tautologies que l'on utilisera le plus dans l'année, en plus des deux lois de De Morgan et de l'équivalence avec la contraposée déjà démontrées dans la section précédente sur les connecteurs. Chacune est énoncée comme une Proposition et accompagnée d'une démonstration courte par table de vérité. Leur donner un nom remplit deux fonctions : cela nous permet de citer le résultat plus tard par son nom (« par transitivité de $\implies$, $\dots$ ») plutôt que de le redémontrer, et cela nous discipline à reconnaître que chaque étape d'une démonstration correspond à l'application de quelque tautologie.

Proposition — Double négation

Pour toute proposition $p$ : $$ \neg(\neg p) \ \Longleftrightarrow \ p. $$

Preuve

$p$	$\neg p$	$\neg(\neg p)$
V	F	V
F	V	F

La première et la troisième colonnes coïncident.

Proposition — Modus ponens

Pour toutes propositions $p$ et $q$ : $$ \big( p \wedge (p \implies q) \big) \implies q $$ est une tautologie. En mots : de $p$ et $p \implies q$, on déduit $q$. C'est la règle qui autorise le mot « donc » dans une démonstration rédigée.

Preuve

$p$	$q$	$p \implies q$	$p \wedge (p \implies q)$	$\big( p \wedge (p \implies q) \big) \implies q$
V	V	V	V	V
V	F	F	F	V
F	V	V	F	V
F	F	V	F	V

La dernière colonne vaut V partout.

Exemple

Une application concrète. Prenons $p$ : « $n$ est multiple de $4$ » et $q$ : « $n$ est multiple de $2$ ». On sait que $p \implies q$ (tout multiple de $4$ est multiple de $2$). Pour $n = 12$, la proposition $p$ est vraie. Le modus ponens donne $q$ : $12$ est multiple de $2$. Toute la déduction tient en une ligne : $12$ est multiple de $4$, donc multiple de $2$.
Le mot donc est précisément l'application du modus ponens. Dans une démonstration rédigée, chaque « donc », « ainsi », « par conséquent » correspond à une application (silencieuse) du modus ponens.

Proposition — Transitivité de l'implication

Pour toutes propositions $p$, $q$, $r$ : $$ \big( (p \implies q) \wedge (q \implies r) \big) \implies (p \implies r) $$ est une tautologie. C'est la règle invoquée implicitement chaque fois que l'on enchaîne deux implications.

Preuve

Une table de vérité sur $(p, q, r)$ comporte $2^3 = 8$ lignes. On calcule la colonne $H = (p \implies q) \wedge (q \implies r)$ puis la colonne $H \implies (p \implies r)$ :

$p$	$q$	$r$	$p \implies q$	$q \implies r$	$H$	$p \implies r$	$H \implies (p \implies r)$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

La dernière colonne vaut V sur toutes les lignes.

Exemple

Un enchaînement typique d'implications : $$ \begin{aligned} n \in 12 \mathbb{Z} &\implies n \in 6 \mathbb{Z} && \text{(tout multiple de 12 est multiple de 6)} \\ n \in 6 \mathbb{Z} &\implies n \in 2 \mathbb{Z} && \text{(tout multiple de 6 est pair)}. \end{aligned} $$ Par transitivité de $\implies$ : $$ n \in 12 \mathbb{Z} \implies n \in 2 \mathbb{Z}. $$ Ce raisonnement par enchaînement est si naturel qu'on l'utilise sans le nommer ; la Proposition ci-dessus est ce qui le rend valide.

Proposition — Distributivité de $\wedge$ et $\vee$

Pour toutes propositions $p$, $q$, $r$ : $$ p \wedge (q \vee r) \ \Longleftrightarrow \ (p \wedge q) \vee (p \wedge r) \qquad p \vee (q \wedge r) \ \Longleftrightarrow \ (p \vee q) \wedge (p \vee r). $$

Preuve

On démontre la première équivalence ; la seconde est duale. On compare les colonnes $p \wedge (q \vee r)$ et $(p \wedge q) \vee (p \wedge r)$ sur les huit lignes en $(p, q, r)$ :

$p$	$q$	$r$	$q \vee r$	$p \wedge (q \vee r)$	$p \wedge q$	$p \wedge r$	$(p \wedge q) \vee (p \wedge r)$
V	V	V	V	V	V	V	V
V	V	F	V	V	V	F	V
V	F	V	V	V	F	V	V
V	F	F	F	F	F	F	F
F	V	V	V	F	F	F	F
F	V	F	V	F	F	F	F
F	F	V	V	F	F	F	F
F	F	F	F	F	F	F	F

Les colonnes $p \wedge (q \vee r)$ et $(p \wedge q) \vee (p \wedge r)$ coïncident.

Compétences à pratiquer

Appliquer le modus ponens
Enchaîner des implications par transitivité

II.3 Conditions nécessaire et suffisante

Le vocabulaire des conditions nécessaire et suffisante n'est, formellement, qu'une relecture de l'implication. Mais c'est le vocabulaire dans lequel la plupart des théorèmes de l'année seront énoncés --- « il faut et il suffit que », « il est nécessaire que », « il suffit que » --- et apprendre à le traduire instantanément en implications fait gagner du temps et évite les erreurs. Une condition suffisante correspond à une implication ; une condition nécessaire correspond à l'implication réciproque. La contraposée est équivalente à l'implication initiale, mais la réciproque ne l'est pas en général.

Définition — Condition nécessaire$\virgule$ suffisante$\virgule$ nécessaire et suffisante

Soient $p$ et $q$ deux propositions.

$p$ est une condition suffisante (CS) pour $q$ lorsque $p \implies q$ est vraie : « il suffit que $p$ pour $q$ ».
$p$ est une condition nécessaire (CN) pour $q$ lorsque $q \implies p$ est vraie : « il faut que $p$ pour $q$ ». De manière équivalente (par contraposée), $\neg p \implies \neg q$ : sans $p$, pas de $q$.
$p$ est une condition nécessaire et suffisante (CNS) pour $q$ lorsque $p \iff q$ est vraie.

Les locutions « il faut $p$ pour $q$ » et « $p$ est nécessaire pour $q$ » correspondent à $q \implies p$. Les locutions « il suffit que $p$ pour $q$ » et « $p$ est suffisant pour $q$ » correspondent à $p \implies q$. La phrase « $p$ si et seulement si $q$ » est exactement l'équivalence $p \iff q$.

Exemple

Pour un entier $n$ :

« $n$ est divisible par $4$ » est une condition suffisante pour « $n$ est divisible par $2$ » : $4 \mid n \implies 2 \mid n$.
« $n$ est divisible par $2$ » est une condition nécessaire pour « $n$ est divisible par $4$ » : $4 \mid n \implies 2 \mid n$, soit par contraposée « si $n$ est impair, alors $n$ n'est pas divisible par $4$ ».
« $n$ est divisible par $6$ » est une condition nécessaire et suffisante pour « $n$ est divisible par $2$ et par $3$ ».

Exemple

Le vocabulaire sur un exemple non mathématique. Pour s'inscrire sur les listes électorales en France, deux conditions doivent être réunies : être de nationalité française et avoir au moins 18 ans.

« Être de nationalité française » est nécessaire (CN) mais pas suffisant (CS) pour voter : un Français de 16 ans ne peut pas voter.
« Avoir au moins 18 ans » est nécessaire mais pas suffisant : un étranger de 25 ans ne peut pas voter.
« Être de nationalité française et avoir au moins 18 ans » est nécessaire et suffisante (CNS).

Le piège, dans le langage courant, est de dire « il suffit » à la place de « il faut » et vice versa. En mathématiques, les deux vont dans des sens opposés et les inverser transforme un théorème vrai en énoncé faux.

Compétences à pratiquer

Identifier des conditions nécessaire et suffisante
Traduire « il faut » et « il suffit » en implications

III Quantificateurs

Un prédicat est un énoncé dépendant d'une variable libre ; il acquiert une valeur de vérité dès que la variable est fixée. Les quantificateurs transforment un prédicat en une proposition en parcourant un ensemble : « pour tout $x$ dans $E$, $\mathcal{P}(x)$ », « il existe $x$ dans $E$ tel que $\mathcal{P}(x)$ ». Les deux quantificateurs $\forall$ et $\exists$, et leurs règles de négation, sont le second pilier du chapitre --- et la source des erreurs d'étudiants les plus fréquentes.
Ces erreurs viennent, en règle générale, de l'un de trois écueils : confondre $\forall$ et $\exists$ en niant ; confondre $\exists$ et $\exists !$ ; ou intervertir l'ordre de deux quantificateurs. Nous les traitons l'un après l'autre : une première sous-section introduit les trois quantificateurs, une seconde énonce la règle de négation comme une Proposition, et une troisième explique pourquoi l'ordre compte.

III.1 Quantificateurs universel et existentiel

Le quantificateur universel $\forall$ affirme que chaque élément d'un ensemble vérifie un prédicat ; le quantificateur existentiel $\exists$ affirme qu'au moins un le vérifie. Un troisième quantificateur $\exists !$ affirme qu'exactement un le vérifie --- énoncé strictement plus fort que $\exists$. On les liste tous les trois en une définition, avec leurs conventions de lecture, et on les accompagne d'exemples qui soulignent l'écart entre les trois.

Définition — Universel$\virgule$ existentiel$\virgule$ unicité

Soit $E$ un ensemble et $\mathcal{P}(x)$ un prédicat d'une variable $x \in E$.

$\forall x \in E, \mathcal{P}(x)$ est la proposition « pour tout $x \in E$, $\mathcal{P}(x)$ est vraie ». Elle vaut V exactement lorsque chaque élément de $E$ vérifie $\mathcal{P}$.
$\exists x \in E, \mathcal{P}(x)$ est la proposition « il existe $x \in E$ tel que $\mathcal{P}(x)$ soit vraie ». Elle vaut V exactement lorsqu'au moins un élément de $E$ vérifie $\mathcal{P}$.
$\exists ! x \in E, \mathcal{P}(x)$ est la proposition « il existe un unique $x \in E$ tel que $\mathcal{P}(x)$ soit vraie ». Elle vaut V exactement lorsqu'un et un seul élément de $E$ vérifie $\mathcal{P}$.

Les symboles $\forall$ et $\exists$ font partie du langage formel. Ce ne sont pas des abréviations typographiques et l'on n'écrit pas « $\forall$ entier $n$ » dans le corps d'une démonstration ; on écrit « pour tout entier $n$ ».

Exemple

Trois propositions sur les réels, toutes vraies, qui illustrent l'écart $\forall$ / $\exists$ / $\exists !$ :

$\forall x \in \mathbb{R}, x^2 \ge 0$. Tout réel a un carré positif.
$\exists x \in \mathbb{R}, x^2 = 2$. Au moins un réel a $2$ pour carré (en fait deux : $\sqrt{2}$ et $-\sqrt{2}$).
$\exists ! x \in \mathbb{R}_+, x^2 = 2$. Dans les réels positifs, seul $\sqrt{2}$ a $2$ pour carré --- une et une seule solution. La restriction à $\mathbb{R}_+$ est ce qui transforme « au moins un » en « exactement un ».

Le dernier item illustre l'usage typique de $\exists !$ : pointer le représentant unique d'une classe en imposant une contrainte (ici, la positivité).

Compétences à pratiquer

Traduire un énoncé avec quantificateurs
Traduire des propriétés de fonction avec quantificateurs

III.2 Négation des quantificateurs

Proposition — Négation des quantificateurs

Pour tout ensemble $E$ et tout prédicat $\mathcal{P}(x)$ sur $E$ : $$ \neg \big( \forall x \in E, \mathcal{P}(x) \big) \ \Longleftrightarrow \ \exists x \in E, \neg \mathcal{P}(x) $$ $$ \neg \big( \exists x \in E, \mathcal{P}(x) \big) \ \Longleftrightarrow \ \forall x \in E, \neg \mathcal{P}(x). $$

Preuve

On démontre la première équivalence ; la seconde s'en déduit en l'appliquant à $\neg \mathcal{P}$ et en utilisant la double négation.
La proposition $\forall x \in E, \mathcal{P}(x)$ vaut V ssi chaque élément de $E$ vérifie $\mathcal{P}$, c'est-à-dire ssi aucun élément de $E$ ne le réfute. Sa négation vaut donc V ssi au moins un élément de $E$ réfute $\mathcal{P}$, c'est-à-dire V ssi $\exists x \in E, \neg \mathcal{P}(x)$.

Exemple

La négation de « $\forall n \in \mathbb{N}, n^2 \ge n$ » est « $\exists n \in \mathbb{N}, n^2 < n$ ». Pour réfuter l'énoncé universel, il suffit d'exhiber un contre-exemple. Ici, aucun contre-exemple n'existe (l'énoncé est vrai), donc la négation est fausse.
La négation de « $\exists x \in \mathbb{R}, x^2 < 0$ » est « $\forall x \in \mathbb{R}, x^2 \ge 0$ ». La négation est vraie (un carré est toujours positif), donc l'énoncé existentiel initial est faux.

Exemple

Un exemple plus délicat : la négation de la définition de convergence d'une suite. L'énoncé « la suite $(u_n)$ converge vers $\ell$ » est, formellement : $$ \forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n \ge N, |u_n - \ell| < \varepsilon. $$ En le niant, on inverse chaque $\forall$ en $\exists$ (et réciproquement) et l'on nie le prédicat le plus interne : $$ \exists \varepsilon > 0, \forall N \in \mathbb{N}, \exists n \ge N, |u_n - \ell| \ge \varepsilon. $$ À voix haute : « il existe un $\varepsilon > 0$ tel que pour tout $N$, on peut trouver $n \ge N$ avec $|u_n - \ell| \ge \varepsilon$ » --- la suite reste à au moins $\varepsilon$ de $\ell$ une infinité de fois.
Cette manipulation formelle est le pain quotidien de l'analyse : on la refera de nombreuses fois dans le chapitre des suites. Assurez-vous dès maintenant que la règle est devenue mécanique : balayer de gauche à droite, inverser chaque quantificateur, nier le prédicat à la fin.

Compétences à pratiquer

Nier un énoncé universel ou existentiel
Nier des quantificateurs imbriqués
Distinguer la portée d'un quantificateur d'une disjonction

III.3 Combinaison de quantificateurs

Deux quantificateurs consécutifs du même type s'échangent librement : $\forall x, \forall y$ est la même chose que $\forall y, \forall x$, et de même pour $\exists$. Deux quantificateurs de types différents ne s'échangent pas. L'implication $$ \big( \exists y, \forall x, \mathcal{P}(x, y) \big) \implies \big( \forall x, \exists y, \mathcal{P}(x, y) \big) $$ est toujours vraie (le $y$ qui convient pour tous les $x$ dans l'antécédent convient pour chaque $x$ dans la conséquence). La réciproque est en général fausse : dans $\forall x, \exists y$, le $y$ choisi peut dépendre de $x$, tandis que dans $\exists y, \forall x$ le même $y$ doit convenir à tous les $x$. Cette asymétrie est au cœur de toutes les nuances de l'analyse (convergence uniforme contre simple, continuité uniforme contre simple, $\dots$).

Exemple

Considérons le prédicat $\mathcal{P}(x, y) = $ « $y > x$ » sur $\mathbb{R}^2$.

$\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y > x$ est vraie : pour chaque $x$, on prend $y = x + 1$. Le choix de $y$ dépend de $x$.
$\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, y > x$ est fausse : aucun réel n'est plus grand que tous les réels.

Cela montre que $\forall \exists$ est strictement plus faible que $\exists \forall$.

Compétences à pratiquer

Distinguer $\forall \exists$ de $\exists \forall$
Comparer $\forall \exists$ et $\exists \forall$ sur un ensemble fini

IV Modes de raisonnement

Les quatre modes de raisonnement classiques --- disjonction des cas, contraposition, absurde, analyse--synthèse --- ne sont pas des recettes magiques. Les trois premiers sont des conséquences directes de la loi du tiers exclu et des tautologies de la section~2. Le quatrième, l'analyse--synthèse, est une méthode systématique pour déterminer l'ensemble des solutions d'un problème, séparée en une phase qui restreint les candidats (analyse) et une phase qui confirme lesquels sont effectivement solutions (synthèse).

IV.1 La loi du tiers exclu

Axiome du tiers exclu

On adopte comme axiome de la logique classique la loi du tiers exclu : pour toute proposition $p$, la proposition $p \vee \neg p$ est vraie. De manière équivalente, toute proposition est soit vraie, soit fausse --- il n'y a pas de troisième option (tertium non datur). Cet axiome est le fondement qui autorise les trois modes de raisonnement des sous-sections suivantes : disjonction des cas, contraposition et absurde. Le quatrième mode, l'analyse--synthèse, n'en dépend pas.

Compétences à pratiquer

Identifier les usages de la loi du tiers exclu

IV.2 Disjonction des cas

Principe. Pour démontrer une proposition $r$, on suppose que la situation se partage en un nombre fini de cas $p_1, \dots, p_n$ tels que $p_1 \vee \dots \vee p_n$ soit vraie. Si sous chaque $p_i$ on déduit $r$, alors $r$ est vraie. Le cas le plus simple --- et le plus fréquent --- découle directement du tiers exclu : prendre $p_1 = p$ et $p_2 = \neg p$.
La rédaction est : « On distingue $n$ cas. Cas 1 : $p_1$. Alors \dots, donc $r$. Cas 2 : $p_2$. Alors \dots, donc $r$. (\dots) Dans tous les cas, $r$. »

Exemple

Démontrer que pour tout $n \in \mathbb{N}$, l'entier $n(n+1)$ est pair.

Correction

Soit $n \in \mathbb{N}$. Par tiers exclu, $n$ est pair ou $n$ est impair.

Cas 1 : $n$ est pair. Écrivons $n = 2k$ avec $k \in \mathbb{N}$. Alors $n(n+1) = 2k(n+1)$, qui est pair.
Cas 2 : $n$ est impair. Alors $n+1$ est pair, donc $n(n+1)$ est pair.

Dans tous les cas, $n(n+1)$ est pair.

Exemple

La valeur absolue $|x| = \max(x, -x)$ est définie par disjonction des cas sur le signe de $x$. Démontrer que $\forall x \in \mathbb{R}, |x| \ge 0$.

Correction

Soit $x \in \mathbb{R}$. Par tiers exclu, $x \ge 0$ ou $x < 0$.

Cas 1 : $x \ge 0$. Alors $|x| = x \ge 0$.
Cas 2 : $x < 0$. Alors $|x| = -x > 0 \ge 0$.

Dans tous les cas, $|x| \ge 0$.
La structure par cas reproduit exactement la définition par morceaux de $|x|$. Chaque fois qu'un objet est défini par cas, une démonstration le concernant procédera typiquement aussi par cas.

Compétences à pratiquer

Démontrer par disjonction des cas

IV.3 Contraposition

Principe. Pour démontrer une implication $p \implies q$, on démontre plutôt sa contraposée $\neg q \implies \neg p$. D'après l'équivalence avec la contraposée (Proposition de la section~1.3), les deux implications sont équivalentes. On y a recours lorsque la négation de $q$ a une forme algébrique plus exploitable que $q$ elle-même.
La rédaction est : « Par contraposition, supposons $\neg q$. Montrons $\neg p$. »

Exemple

Démontrer que pour tout $n \in \mathbb{N}$, si $n^2$ est pair, alors $n$ est pair.

Correction

Soit $n \in \mathbb{N}$. Raisonnons par contraposition : supposons $n$ impair. Montrons que $n^2$ est impair.
Écrivons $n = 2k + 1$ avec $k \in \mathbb{N}$. Alors : $$ \begin{aligned} n^2 &= (2k + 1)^2 && \text{(élévation au carré)} \\ &= 4 k^2 + 4 k + 1 && \text{(développement)} \\ &= 2 (2 k^2 + 2 k) + 1 && \text{(factorisation par 2)}. \end{aligned} $$ En posant $k' = 2 k^2 + 2 k \in \mathbb{N}$, on obtient $n^2 = 2 k' + 1$, qui est impair.

Compétences à pratiquer

Démontrer par contraposition

IV.4 Raisonnement par l'absurde

Principe. Une contradiction est toute proposition de la forme $r \wedge \neg r$ --- toujours fausse par le principe de non-contradiction. Pour démontrer $p$ par l'absurde, on suppose $\neg p$ et on en déduit une contradiction ; par le tiers exclu, $p$ est alors vraie. On y a recours lorsque l'hypothèse $\neg p$ donne une information algébrique exploitable que la vérité de $p$ ne fournirait pas.
La rédaction est : « Raisonnons par l'absurde et supposons $\neg p$. \dots [déductions menant à une contradiction]. Contradiction. Donc $p$. »

Exemple

Démontrer que pour tout $n \in \mathbb{N}$, $\sqrt{n^2 + 2}$ n'est pas un entier.

Correction

Soit $n \in \mathbb{N}$.
Raisonnons par l'absurde et supposons $\sqrt{n^2 + 2}$ entier ; notons-le $p$.
Alors : $$ \begin{aligned} p^2 &= n^2 + 2 && \text{(élévation au carré)} \\ p^2 - n^2 &= 2 && \text{(réarrangement)} \\ (p - n)(p + n) &= 2 && \text{(différence de carrés)}. \end{aligned} $$ Comme $p \ge 0$ et $p^2 > n^2$, on a $p > n \ge 0$.
Donc $p - n \ge 1$ et $p + n \ge p - n \ge 1$ sont deux entiers naturels.
La seule factorisation de $2$ dans $\mathbb{N}^*$ est $2 \cdot 1$, donc $p - n = 1$ et $p + n = 2$.
En sommant les deux équations : $2p = 3$, donc $p = \tfrac{3}{2}$ --- contradiction avec $p \in \mathbb{N}$.
Donc $\sqrt{n^2 + 2}$ n'est pas un entier.

Compétences à pratiquer

Démontrer par l'absurde
Majorer par l'absurde

IV.5 Analyse--synthèse

Méthode — Analyse--synthèse

Pour déterminer l'ensemble des objets $x$ d'un ensemble $E$ qui vérifient une propriété $\mathcal{P}$, on procède en deux phases :

Analyse. Supposons que $x \in E$ vérifie $\mathcal{P}$. On en déduit le plus possible sur $x$, restreignant les candidats à une petite liste explicite. L'analyse répond à : à quoi $x$ ressemble-t-il, s'il existe ? Elle établit l'unicité (ou du moins restreint les candidats).
Synthèse. Pour chaque candidat produit par l'analyse, vérifier s'il appartient effectivement à $E$ et vérifie $\mathcal{P}$. La synthèse répond à : lesquels des candidats sont de véritables solutions ? Elle établit l'existence.

Les deux phases ensemble décrivent toutes les solutions : l'analyse borne la recherche ; la synthèse confirme quels candidats conviennent.
Slogan. Analyse = restriction des candidats ; synthèse = vérification / existence.

Exemple

Un premier exemple très simple : déterminer tous les $x \in \mathbb{R}$ tels que $x^2 = x$.

Correction

Analyse. Soit $x \in \mathbb{R}$ vérifiant $x^2 = x$. Alors : $$ \begin{aligned} x^2 - x &= 0 && \text{(réarrangement)} \\ x (x - 1) &= 0 && \text{(factorisation)} \\ x = 0 \ \text{ou}\ x &= 1 && \text{(produit nul dans $\mathbb{R}$)}. \end{aligned} $$ Les candidats sont $\{0, 1\}$.
Synthèse. Pour $x = 0$ : $x^2 = 0 = x$, OK. Pour $x = 1$ : $x^2 = 1 = x$, OK. Les deux candidats sont solutions.
Conclusion. L'ensemble des solutions est $\{0, 1\}$.

Toute la structure --- analyse réduisant à deux candidats, synthèse confirmant les deux --- est le schéma canonique.

Exemple

Un exemple plus riche, montrant que l'analyse peut laisser plusieurs candidats et que la synthèse doit valider chacun. Déterminer toutes les fonctions $f \colon \mathbb{R} \to \mathbb{R}$ telles que pour tout $x \in \mathbb{R}$, $f(x) + f(-x) = 0$ et $f(1) = 3$.

Correction

Analyse. Soit $f$ une solution.
La condition impose $f(-x) = -f(x)$ pour tout $x$ : $f$ est impaire.
Pour $x = 0$ : $2 f(0) = 0$, donc $f(0) = 0$.
L'hypothèse $f(1) = 3$ force alors $f(-1) = -3$.
Les contraintes fixent ainsi $f$ sur $\{-1, 0, 1\}$, mais laissent libre le choix des valeurs sur un représentant de chaque paire $\{x, -x\}$ avec $x \notin \{-1, 0, 1\}$.
Toute fonction impaire avec $f(1) = 3$ est donc candidate.
Synthèse. Soit $f \colon \mathbb{R} \to \mathbb{R}$ une fonction impaire telle que $f(1) = 3$, par exemple $f(x) = 3x$ ou $f(x) = 3 \sin\!\big(\tfrac{\pi x}{2}\big)$.
Pour tout $x$, $f(-x) = -f(x)$, donc $f(x) + f(-x) = 0$.
Et $f(1) = 3$ par hypothèse.
Chaque telle $f$ est donc solution.
Conclusion. L'ensemble des solutions est l'ensemble des fonctions impaires $f \colon \mathbb{R} \to \mathbb{R}$ vérifiant $f(1) = 3$ --- il y en a une infinité.

Comparer avec l'exemple précédent : là, l'analyse a pointé deux candidats et la synthèse les a tous deux validés. Ici, l'analyse pointe une famille entière. La synthèse doit donc valider la famille entière, et non simplement vérifier deux cas.

Compétences à pratiquer

Résoudre par analyse--synthèse

V Raisonnement par récurrence

Le raisonnement par récurrence est l'outil standard pour démontrer les énoncés de la forme $\forall n \in \mathbb{N}, \mathcal{P}_n$. Trois variantes sont couramment distinguées --- simple, double, forte --- choisies selon le ou les rangs antérieurs que l'étape d'hérédité doit invoquer. Nous énonçons chacune sous forme de Théorème et l'accompagnons d'un patron de rédaction plus un exemple. Les trois théorèmes se ressemblent mais diffèrent par leur initialisation et l'hypothèse d'hérédité ; les lire en parallèle fait apparaître ce que chaque variante autorise à supposer.

V.1 Récurrence simple

Theorem — Récurrence simple

Soit $A$ une partie de $\mathbb{N}$. Si $$ 0 \in A \quad \ \text{et}\ \quad \forall n \in \mathbb{N}, \big( n \in A \implies n+1 \in A \big) $$ alors $A = \mathbb{N}$. De manière équivalente : pour tout prédicat $\mathcal{P}$ sur $\mathbb{N}$, si $\mathcal{P}_0$ est vraie et $\mathcal{P}_n \implies \mathcal{P}_{n+1}$ pour tout $n \in \mathbb{N}$, alors $\mathcal{P}_n$ est vraie pour tout $n \in \mathbb{N}$.

Méthode — Rédiger une récurrence simple

Une démonstration par récurrence simple est structurée :

Initialisation : vérifier $\mathcal{P}_0$.
Hérédité : soit $n \in \mathbb{N}$ ; supposer $\mathcal{P}_n$ ; montrer $\mathcal{P}_{n+1}$.
Conclusion : par récurrence, $\forall n \in \mathbb{N}, \mathcal{P}_n$.

Deux erreurs à éviter. N'écrivez pas « supposons $\mathcal{P}_n$ pour tout $n \in \mathbb{N}$ » : ce serait supposer ce que l'on veut démontrer. N'écrivez pas « supposons $\mathcal{P}_n$ pour un certain $n \in \mathbb{N}$ » : l'hérédité doit être démontrée pour tout $n$, la variable étant introduite au début de l'étape.

Exemple

La formule classique de Gauss : $\forall n \in \mathbb{N}, \displaystyle \sum_{k=0}^{n} k = \frac{n(n+1)}{2}$.

Correction

Notons $\mathcal{P}_n$ : « $\displaystyle \sum_{k=0}^{n} k = \frac{n(n+1)}{2}$ ».

Initialisation. Pour $n = 0$ : $\sum_{k=0}^{0} k = 0 = \tfrac{0 \cdot 1}{2}$. Donc $\mathcal{P}_0$.
Hérédité. Soit $n \in \mathbb{N}$, supposons $\mathcal{P}_n$. Alors : $$ \begin{aligned} \sum_{k=0}^{n+1} k &= \sum_{k=0}^{n} k + (n+1) && \text{(en isolant le dernier terme)} \\ &= \frac{n(n+1)}{2} + (n+1) && \text{(par } \mathcal{P}_n \text{)} \\ &= (n+1) \cdot \frac{n + 2}{2} && \text{(factorisation par $n+1$)} \\ &= \frac{(n+1)(n+2)}{2}. \end{aligned} $$ Donc $\mathcal{P}_{n+1}$.
Conclusion. Par récurrence, $\mathcal{P}_n$ est vraie pour tout $n \in \mathbb{N}$.

Exemple

Une majoration sur une suite définie par récurrence. Soit $(u_n)_{n \in \mathbb{N}}$ définie par $u_0 = 1$ et $u_{n+1} = 1 + \dfrac{u_n}{n+1}$. Démontrer que $\forall n \in \mathbb{N}, u_n \le 2$.

Correction

Notons $\mathcal{P}_n$ : « $u_n \le 2$ ».

Initialisation. $u_0 = 1 \le 2$. Donc $\mathcal{P}_0$.
Hérédité. Soit $n \in \mathbb{N}$, supposons $u_n \le 2$. Alors : $$ \begin{aligned} u_{n+1} &= 1 + \frac{u_n}{n+1} && \text{(définition)} \\ &\le 1 + \frac{2}{n+1} && \text{(par } u_n \le 2 \text{)}. \end{aligned} $$ On distingue selon $n$ :
- si $n = 0$, $u_1 = 1 + u_0 = 2$ ;
- si $n \ge 1$, $\dfrac{2}{n+1} \le 1$, donc $u_{n+1} \le 2$.
Dans tous les cas $u_{n+1} \le 2$.
Conclusion. Par récurrence, $\forall n \in \mathbb{N}, u_n \le 2$.

Compétences à pratiquer

Démontrer une identité par récurrence
Démontrer une majoration par récurrence

V.2 Récurrence double

Theorem — Récurrence double

Soit $A$ une partie de $\mathbb{N}$. Si $$ \{0, 1\} \subset A \quad \ \text{et}\ \quad \forall n \in \mathbb{N}, \big( (n \in A \wedge n+1 \in A) \implies n+2 \in A \big) $$ alors $A = \mathbb{N}$.

Méthode — Rédiger une récurrence double

On utilise la récurrence double lorsque le calcul de $\mathcal{P}_{n+2}$ requiert à la fois $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ --- typiquement pour les récurrences linéaires d'ordre $2$.

Initialisation : vérifier $\mathcal{P}_0$ et $\mathcal{P}_1$.
Hérédité : soit $n \in \mathbb{N}$ ; supposer $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$ ; montrer $\mathcal{P}_{n+2}$.

Exemple

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$. Démontrer que $\forall n \in \mathbb{N}, u_n = 2^n + 3$.

Correction

Notons $\mathcal{P}_n$ : « $u_n = 2^n + 3$ ».

Initialisation. $u_0 = 4 = 2^0 + 3$ et $u_1 = 5 = 2^1 + 3$.
Hérédité. Soit $n \in \mathbb{N}$, supposons $\mathcal{P}_n$ et $\mathcal{P}_{n+1}$. Alors : $$ \begin{aligned} u_{n+2} &= 3 u_{n+1} - 2 u_n && \text{(définition)} \\ &= 3 (2^{n+1} + 3) - 2 (2^n + 3) && \text{(par } \mathcal{P}_{n+1}, \mathcal{P}_n \text{)} \\ &= (3 \cdot 2 - 2) \cdot 2^n + (9 - 6) && \text{(regroupement)} \\ &= 4 \cdot 2^n + 3 && \text{(arithmétique)} \\ &= 2^{n+2} + 3. \end{aligned} $$ Donc $\mathcal{P}_{n+2}$.
Conclusion. Par récurrence double, $\forall n \in \mathbb{N}, u_n = 2^n + 3$.

Compétences à pratiquer

Démontrer la forme explicite d'une récurrence d'ordre 2

V.3 Récurrence forte

Theorem — Récurrence forte

Soit $A$ une partie de $\mathbb{N}$. Si $$ 0 \in A \quad \ \text{et}\ \quad \forall n \in \mathbb{N}, \big( \{0, 1, \dots, n\} \subset A \implies n+1 \in A \big) $$ alors $A = \mathbb{N}$.

Méthode — Rédiger une récurrence forte

On utilise la récurrence forte lorsque l'établissement de $\mathcal{P}_{n+1}$ requiert tous les rangs précédents $\mathcal{P}_0, \dots, \mathcal{P}_n$, et non $\mathcal{P}_n$ seule.

Initialisation : vérifier $\mathcal{P}_0$.
Hérédité : soit $n \in \mathbb{N}$ ; supposer $\mathcal{P}_k$ pour tout $k \in \{0, 1, \dots, n\}$ ; montrer $\mathcal{P}_{n+1}$.

Malgré son nom, la récurrence forte est logiquement équivalente à la récurrence simple (appliquer la récurrence simple à $\mathcal{Q}_n = $ « $\mathcal{P}_k$ pour tout $k \in \{0, \dots, n\}$ »). L'intérêt est purement tactique.

Exemple

Soit $(v_n)_{n \in \mathbb{N}}$ une suite réelle telle que $v_0 \ge 0$ et $v_{n+1} \le \displaystyle \sum_{k=0}^{n} v_k$ pour tout $n \in \mathbb{N}$. Démontrer que $\forall n \in \mathbb{N}, v_n \le 2^n v_0$.

Correction

Notons $\mathcal{P}_n$ : « $v_n \le 2^n v_0$ ».

Initialisation. $v_0 = 2^0 v_0$, donc $\mathcal{P}_0$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$, supposons $\mathcal{P}_k$ pour tout $k \in \{0, \dots, n\}$. Alors : $$ \begin{aligned} v_{n+1} &\le \sum_{k=0}^{n} v_k && \text{(hypothèse sur } (v_n) \text{)} \\ &\le \sum_{k=0}^{n} 2^k v_0 && \text{(par } \mathcal{P}_k \text{ pour chaque } k \text{)} \\ &= (2^{n+1} - 1) v_0 && \text{(somme géométrique)} \\ &\le 2^{n+1} v_0 && \text{(puisque } v_0 \ge 0 \text{)}. \end{aligned} $$ Donc $\mathcal{P}_{n+1}$.
Conclusion. Par récurrence forte, $\forall n \in \mathbb{N}, v_n \le 2^n v_0$.

Compétences à pratiquer

Démontrer une propriété par récurrence forte
Décomposer $n$ en $3a + 5b$

VI Pour aller plus loin

Compétences à pratiquer

Quiz

Aller à la section

\(p\)	\(q\)	\(p \wedge q\)	\(\neg(p \wedge q)\)	\(\neg p\)	\(\neg q\)	\(\neg p \vee \neg q\)
V	V	V	F	F	F	F
V	F	F	V	F	V	V
F	V	F	V	V	F	V
F	F	F	V	V	V	V

\(p\)	\(q\)	\(p \implies q\)	\(\neg q\)	\(\neg p\)	\(\neg q \implies \neg p\)
V	V	V	F	F	V
V	F	F	V	F	F
F	V	V	F	V	V
F	F	V	V	V	V

\(p\)	\(q\)	\(p \implies q\)	\(\neg(p \implies q)\)	\(\neg q\)	\(p \wedge \neg q\)
V	V	V	F	F	F
V	F	F	V	V	V
F	V	V	F	F	F
F	F	V	F	V	F

\(p\)	\(\neg p\)	\(p \vee \neg p\)	\(p \wedge \neg p\)
V	F	V	F
F	V	V	F

\(p\)	\(q\)	\(p \implies q\)	\((p \implies q) \wedge p\)	\(\big((p\implies q) \wedge p\big) \implies q\)
V	V	V	V	V
V	F	F	F	V
F	V	V	F	V
F	F	V	F	V

\(p\)	\(q\)	\(r\)	\(p \implies q\)	\(q \implies r\)	\(H\)	\(p \implies r\)	\(H \implies (p \implies r)\)
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V