Le cours

Résumé en cinq points

Une implication $P \Rightarrow Q$ n'est fausse que si $P$ est vraie et $Q$ fausse. Sa négation est « $P$ et non $Q$ », sa contraposée « non $Q \Rightarrow$ non $P$ » lui est équivalente, sa réciproque n'a rien à voir.
De Morgan : la négation d'un « et » est un « ou » de négations, celle d'un « ou » est un « et » de négations. Même chose pour le complémentaire d'une intersection et d'une réunion.
Une égalité d'ensembles se démontre par double inclusion. On ne confond jamais $\in$ et $\subset$ .
On nie une phrase quantifiée en échangeant les quantificateurs dans l'ordre puis en niant la fin. L'ordre $\forall\,\exists$ n'est pas celui de $\exists\,\forall$ .
Une récurrence a trois étapes nommées. L'initialisation n'est jamais facultative.

Pourquoi ce chapitre

Ce chapitre est une boîte à outils, pas un chapitre de théorie. Les notions présentées ont déjà été rencontrées au lycée, elles sont reprises sans abstraction excessive, et elles ne peuvent pas constituer le thème principal d'une question d'écrit ou d'oral. Elles servent de langage pour tout le reste de l'année.

Trois usages dominent en BCPST.

Probabilités : un événement est une partie de l'univers. « A et B » devient $A \cap B$ , « A ou B » devient $A \cup B$ , « contraire de A » devient le complémentaire de $A$ . Les formules de De Morgan sont les règles que l'on applique pour calculer la probabilité d'un événement contraire.
Algorithmique : les connecteurs logiques sont les tests d'une instruction conditionnelle, et savoir nier proprement une condition évite les bugs.
Récurrence : elle sert dans tout le programme, des suites aux puissances de matrices.

L'objectif est modeste mais ferme : savoir écrire une phrase mathématique correcte, savoir la nier, savoir mener une récurrence sans oublier d'étape.

1Logique élémentaire

1.1Assertion

Définition 1.1Assertion

Une assertion (ou proposition) est un énoncé mathématique qui est soit vrai, soit faux, jamais les deux.

Exemple 1.2

« 12 est divisible par 3 » est une assertion vraie. « 12 est un nombre premier » est une assertion fausse.

Attention

« $x > 0$ » n'est pas une assertion tant que $x$ n'est pas fixé : c'est un prédicat. Il devient une assertion quand on donne une valeur à $x$ ou quand on le quantifie.

1.2Négation

Définition 1.3Négation

La négation de $P$ , notée « non $P$ », est vraie exactement quand $P$ est fausse. Nier deux fois redonne l'assertion de départ.

Attention

La négation de « $x > 0$ » est « $x \leqslant 0$ », pas « $x < 0$ ».

1.3Les connecteurs « et » et « ou »

Définition 1.4Connecteurs « et » et « ou »

« $P$ et $Q$ » est vraie quand les deux assertions sont vraies simultanément.
« $P$ ou $Q$ » est vraie dès qu'au moins l'une des deux est vraie.

Le « ou » mathématique est inclusif : si $P$ et $Q$ sont vraies toutes les deux, « $P$ ou $Q$ » est vraie. Le « ou » du langage courant (« fromage ou dessert ») est exclusif, ce n'est pas celui des mathématiques.

Loi 1.5Règles de De Morgan

Pour toutes assertions $P$ et $Q$ :

la négation de « $P$ et $Q$ » est « non $P$ ou non $Q$ » ;
la négation de « $P$ ou $Q$ » est « non $P$ et non $Q$ ».

Exemple 1.6

Un réel $x$ n'appartient pas au segment $[0, 1]$ signifie non ( $x \geqslant 0$ et $x \leqslant 1$ ), c'est-à-dire $x < 0$ ou $x > 1$ .

Exemple 1.7Exemple biologique

Un individu est de phénotype récessif quand ses deux allèles sont récessifs. La négation, c'est-à-dire le phénotype dominant, s'écrit : le premier allèle est dominant ou le second l'est.

Propriété 1.8Distributivité

Pour toutes assertions $P$ , $Q$ , $R$ :

« $P$ et ( $Q$ ou $R$ ) » équivaut à « ( $P$ et $Q$ ) ou ( $P$ et $R$ ) » ;
« $P$ ou ( $Q$ et $R$ ) » équivaut à « ( $P$ ou $Q$ ) et ( $P$ ou $R$ ) ».

On les vérifie par tables de vérité, en examinant les huit combinaisons de valeurs de $P$ , $Q$ , $R$ .

1.4Implication

Définition 1.9Implication

« $P$ implique $Q$ », notée $P \Rightarrow Q$ , est fausse dans un seul cas : $P$ vraie et $Q$ fausse. Elle est donc vraie dans les trois autres cas, en particulier chaque fois que $P$ est fausse. Autrement dit, $P \Rightarrow Q$ signifie « non $P$ ou $Q$ ».

Propriété 1.10Négation et conditions

La négation de « $P \Rightarrow Q$ » est « $P$ et non $Q$ ». Pour réfuter une implication, on exhibe une situation où l'hypothèse est vraie et la conclusion fausse : c'est un contre-exemple.
Dans $P \Rightarrow Q$ , $P$ est une condition suffisante pour $Q$ , et $Q$ est une condition nécessaire pour $P$ .

Attention

L'implication n'est pas une relation de cause à effet, et elle ne dit rien quand l'hypothèse est fausse.

1.5Réciproque, contraposée

Définition 1.11Réciproque et contraposée

La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$ .
La contraposée de $P \Rightarrow Q$ est « non $Q \Rightarrow$ non $P$ ».

Exemple 1.12

« $n$ est multiple de 4 $\Rightarrow$ $n$ est pair » est vraie. Sa réciproque est fausse, comme le montre $n = 2$ .

Propriété 1.13Principe de contraposition

Une implication et sa contraposée sont vraies en même temps ou fausses en même temps. Il fournit une méthode de démonstration.

Exemple 1.14

Soit $n$ un entier. Montrons que si $n^2$ est pair alors $n$ est pair. On démontre la contraposée : si $n$ est impair, alors $n = 2k + 1$ et $\begin{aligned} n^2 &= 4k^2 + 4k + 1\\ &= 2(2k^2 + 2k) + 1, \end{aligned}$ qui est impair.

1.6Équivalence

Définition 1.15Équivalence

$P \Leftrightarrow Q$ signifie « $P \Rightarrow Q$ et $Q \Rightarrow P$ ». On dit alors que $P$ est une condition nécessaire et suffisante pour $Q$ .

Pour établir une équivalence, on démontre le plus souvent les deux implications séparément.

Attention

Piège de rédaction, très sanctionné : enchaîner des $\Leftrightarrow$ alors qu'une étape n'est qu'une implication. Élever au carré, multiplier par une quantité qui peut être nulle, appliquer une fonction non injective : ces opérations ne conservent qu'une implication. Sur $\sqrt{x + 2} = x$ , l'élévation au carré donne $x + 2 = x^2$ , donc $x = 2$ ou $x = -1$ , mais seul $x = 2$ convient. La synthèse est obligatoire.

2Vocabulaire des ensembles

2.1Ensemble, élément, appartenance

Définition 2.1Ensemble

Un ensemble est une collection d'objets appelés ses éléments. On note $x \in E$ pour dire que $x$ est un élément de $E$ , et $x \notin E$ sinon. L'ensemble vide, noté $\emptyset$ , n'a aucun élément.

On décrit un ensemble de deux façons :

en extension, en listant ses éléments, comme $\{0, 1, 2\}$ ;
en compréhension, en donnant une propriété caractéristique, comme $\{x \in \R,\ x^2 \leqslant 4\}$ , qui est le segment $[-2, 2]$ .

2.2Inclusion et égalité

Définition 2.2Inclusion

$A$ est inclus dans $E$ , noté $A \subset E$ , quand tout élément de $A$ est élément de $E$ . On dit alors que $A$ est une partie, ou un sous-ensemble, de $E$ . L'ensemble des parties de $E$ est noté $\mathcal{P}(E)$ .

Attention

Il ne faut pas confondre $\in$ et $\subset$ . Pour $E = \{1, 2, 3\}$ , on a $1 \in E$ et $\{1\} \subset E$ , mais pas $1 \subset E$ ni $\{1\} \in E$ .

MéthodeDémontrer une égalité d'ensembles

Prouver la double inclusion $A \subset B$ et $B \subset A$ .
Pour $A \subset B$ , partir de « soit $x \in A$ » et montrer $x \in B$ .

2.3Réunion, intersection, complémentaire

Définition 2.3Réunion, intersection, complémentaire

Pour $A$ et $B$ parties de $E$ :

$A \cup B$ est l'ensemble des $x$ qui sont dans $A$ ou dans $B$ , au sens inclusif ;
$A \cap B$ est l'ensemble des $x$ qui sont dans $A$ et dans $B$ ;
le complémentaire de $A$ dans $E$ , noté $\overline{A}$ , est l'ensemble des éléments de $E$ qui ne sont pas dans $A$ .

$A$ et $B$ sont disjoints quand $A \cap B = \emptyset$ .

Le programme se limite aux réunions et intersections d'un nombre fini de parties.

Loi 2.4Règles de De Morgan ensemblistes

Pour toutes parties $A$ et $B$ de $E$ : $\overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}.$

Propriété 2.5Distributivité

Pour toutes parties $A$ , $B$ , $C$ de $E$ : $\begin{aligned} A \cap (B \cup C) &= (A \cap B) \cup (A \cap C),\\ A \cup (B \cap C) &= (A \cup B) \cap (A \cup C). \end{aligned}$

Exemple 2.6Exemple pour les probabilités

On tire une plante dans une population. $A$ est l'événement « la plante est résistante au champignon », $B$ l'événement « la plante est de grande taille ». L'événement « la plante n'est ni résistante ni grande » est le complémentaire de $A \cup B$ , c'est-à-dire $\overline{A} \cap \overline{B}$ . C'est la règle de De Morgan.

2.4Couples, p-uplets, produit cartésien

Définition 2.7Couple et produit cartésien

Un couple $(x, y)$ est la donnée ordonnée de deux objets. Deux couples sont égaux quand leurs premières composantes sont égales et leurs secondes composantes aussi.

Le produit cartésien $E \times F$ est l'ensemble des couples $(x, y)$ avec $x \in E$ et $y \in F$ .

L'ordre compte : $(1, 2)$ et $(2, 1)$ sont différents, alors que les ensembles $\{1, 2\}$ et $\{2, 1\}$ sont égaux.

Définition 2.8 $p$ -uplet

Un $p$ -uplet est une liste ordonnée $(x_1, \dots, x_p)$ . On note $E^p$ l'ensemble des $p$ -uplets d'éléments de $E$ . Un élément de $E^p$ est aussi appelé une $p$ -liste d'éléments de $E$ .

Exemple 2.9

Une séquence d'ADN de longueur 3 est un élément de $E^3$ avec $E = \{A, C, G, T\}$ . C'est une 3-liste : l'ordre des bases compte et les répétitions sont permises. Ce point de vue sera repris tel quel en dénombrement.

3Quantificateurs

3.1Les deux quantificateurs

Définition 3.1Quantificateurs

« $\forall x \in E,\ P(x)$ » se lit « pour tout $x$ de $E$ , $P(x)$ ».
« $\exists x \in E,\ P(x)$ » se lit « il existe $x$ dans $E$ tel que $P(x)$ ».

La notation $\exists !$ signifie « il existe un unique ».

MéthodeDémontrer une assertion quantifiée

Pour « $\forall x \in E,\ P(x)$ » : écrire « soit $x$ un élément de $E$ » et prouver $P(x)$ sans rien supposer de particulier sur $x$ .
Pour « $\exists x \in E,\ P(x)$ » : exhiber un élément précis et vérifier qu'il convient, ou invoquer un théorème d'existence.

3.2Négation d'une assertion quantifiée

Propriété 3.2Négation des quantificateurs

La négation de « $\forall x \in E,\ P(x)$ » est « $\exists x \in E,\ \text{non } P(x)$ ».
La négation de « $\exists x \in E,\ P(x)$ » est « $\forall x \in E,\ \text{non } P(x)$ ».

Sur une phrase à plusieurs quantificateurs, on échange chaque $\forall$ avec $\exists$ dans l'ordre où ils apparaissent, puis on nie la propriété finale.

Exemple 3.3

« $\forall n \in \N,\ \exists m \in \N,\ m > n^2$ » a pour négation « $\exists n \in \N,\ \forall m \in \N,\ m \leqslant n^2$ ».

3.3L'ordre des quantificateurs

Deux quantificateurs de même nature se permutent. Un $\forall$ et un $\exists$ ne se permutent pas.

Exemple 3.4

« $\forall x \in \R,\ \exists y \in \R,\ y > x$ » est vraie : il suffit de prendre $y = x + 1$ .
« $\exists y \in \R,\ \forall x \in \R,\ y > x$ » est fausse : aucun réel n'est plus grand que tous les réels.

Dans « $\forall x,\ \exists y$ », le $y$ dépend de $x$ . Dans « $\exists y,\ \forall x$ », le même $y$ doit convenir pour tous les $x$ .

3.4Règles d'écriture

Le programme est explicite : l'usage des quantificateurs hors des énoncés mathématiques est à proscrire. On n'écrit pas « $\forall$ les plantes de l'échantillon ». On rédige soit une phrase française complète, soit une formule entièrement symbolique.

Dans une formule, la variable quantifiée est muette : « $\forall x \in E,\ P(x)$ » et « $\forall t \in E,\ P(t)$ » disent la même chose.

4Raisonnement par récurrence

4.1Le principe

Théorème 4.1Principe de récurrence

Hypothèses

$P(n)$ est une propriété dépendant d'un entier $n$ ;
$n_0$ est un entier ;
$P(n_0)$ est vraie (initialisation) ;
pour tout entier $n \geqslant n_0$ , $P(n)$ vraie entraîne $P(n+1)$ (hérédité).

Alors $P(n)$ est vraie pour tout $n \geqslant n_0$ .

MéthodeRédiger une récurrence

Initialisation : vérifier $P(n_0)$ .
Hérédité : fixer un entier $n \geqslant n_0$ , supposer $P(n)$ vraie (c'est l'hypothèse de récurrence) et démontrer $P(n+1)$ .
Conclusion : par le principe de récurrence, $P(n)$ est vraie pour tout $n \geqslant n_0$ .

Exemple 4.2Une somme

Pour tout $n \geqslant 1$ , $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ .

Initialisation : pour $n = 1$ , la somme vaut 1 et la formule donne $\dfrac{1 \times 2}{2} = 1$ .

Hérédité : si la formule vaut au rang $n$ , alors $\begin{aligned} 1 + \dots + n + (n+1) &= \frac{n(n+1)}{2} + (n+1)\\ &= \frac{(n+1)(n+2)}{2}, \end{aligned}$ qui est la formule au rang $n + 1$ .

Exemple 4.3Une suite

Une population évolue selon $u_{n+1} = 1{,}2\,u_n$ avec $u_0 = 50$ . Montrons par récurrence que $u_n > 0$ pour tout $n$ .

Initialisation : $u_0 = 50 > 0$ . Hérédité : si $u_n > 0$ , alors $u_{n+1} = 1{,}2\,u_n > 0$ . La conclusion est immédiate. Ce type de récurrence, qui sert à justifier qu'une suite reste dans un intervalle, revient sans cesse.

4.2Récurrence forte

Il arrive que $P(n+1)$ ne se déduise pas de $P(n)$ seule, mais de toutes les propriétés précédentes. On suppose alors $P(k)$ vraie pour tout $k$ compris entre $n_0$ et $n$ , et on démontre $P(n+1)$ .

Le programme précise que lorsqu'une récurrence nécessite une hypothèse dite forte, la formulation de cette hypothèse doit être proposée par l'énoncé. On ne demandera pas à un étudiant de BCPST d'inventer seul une récurrence forte, mais il doit savoir la rédiger quand elle est suggérée.

4.3Erreurs classiques

Attention

Quatre erreurs à éviter :

oublier l'initialisation : la propriété « $n = n + 1$ » est héréditaire et pourtant fausse pour tout $n$ , seule l'initialisation manque ;
écrire « supposons que $P(n)$ est vraie pour tout $n$ », ce qui est la conclusion et non l'hypothèse ;
oublier de préciser le rang de départ ;
utiliser l'hypothèse de récurrence sans dire où on l'utilise.

Méthodes

MéthodeDémontrer une inclusion ou une égalité d'ensembles

Pour $A \subset B$ , partir de « soit $x \in A$ » et aboutir à $x \in B$ .
Pour une égalité, faire la double inclusion.

MéthodeDémontrer une implication difficile

Essayer la contraposée.
La préférer surtout quand la conclusion est de la forme « non quelque chose » ou quand l'hypothèse porte sur un carré.

MéthodeRéfuter une assertion universelle

Chercher un contre-exemple.
Se souvenir qu'un exemple ne prouve jamais une assertion universelle.

MéthodeNier une phrase quantifiée

Procéder mécaniquement de gauche à droite, sans réfléchir au sens.
Relire le résultat pour vérifier qu'il a un sens.

MéthodeProuver une identité portant sur un entier $n$

Penser récurrence.
Vérifier d'abord si un calcul direct ou une somme télescopique ne suffit pas.

MéthodeRésoudre une équation en élevant au carré

Annoncer que l'on raisonne par implication.
Faire la vérification finale.

Ce qu'il faut savoir refaire en khôlle

Nier une assertion à deux ou trois quantificateurs sans hésiter.
Écrire les formules de De Morgan, en version logique et en version ensembliste, et les illustrer sur un exemple de probabilités.
Démontrer une égalité d'ensembles par double inclusion, par exemple $\overline{A \cup B} = \overline{A} \cap \overline{B}$ .
Démontrer par contraposée que si $n^2$ est pair alors $n$ est pair.
Rédiger une récurrence complète en nommant initialisation, hérédité et conclusion, sur une somme et sur une propriété d'une suite.
Expliquer, avec un exemple, pourquoi « $\forall x\ \exists y$ » et « $\exists y\ \forall x$ » ne disent pas la même chose.
Justifier qu'une équivalence annoncée dans une résolution d'équation en est bien une, ou faire la synthèse.

Méthodes et exercices

Les résultats à connaître

Négation d'un « et » et d'un « ou » (règles de De Morgan) : exigible, vérification par table de vérité.
Distributivité du « ou » sur le « et » et du « et » sur le « ou » : exigible, table de vérité à huit lignes.
P ⇒ Q équivaut à « non P ou Q », sa négation est « P et non Q » : exigible, table de vérité.
Principe de contraposition, P ⇒ Q équivaut à « non Q ⇒ non P » : rappelé par le programme, exigible avec justification.
Négation de « ∀x ∈ E, P(x) » et de « ∃x ∈ E, P(x) » : exigible, y compris sur des phrases à plusieurs quantificateurs.
∀ et ∃ ne commutent pas : exigible, avec un contre-exemple.
Égalité de deux ensembles par double inclusion : exigible, c'est la méthode de référence.
Complémentaire d'une réunion et d'une intersection (De Morgan ensembliste) : exigible avec démonstration par double inclusion.
Distributivité de ∩ sur ∪ et de ∪ sur ∩ : exigible avec démonstration.
Égalité de deux couples, produit cartésien, p-listes : définitions exigibles, sans théorème.
Principe de récurrence : admis (c'est une propriété des entiers), rédaction en trois étapes exigible.
Récurrence forte : rédaction exigible, mais le programme impose que l'énoncé propose la formulation de l'hypothèse.
Raisonnement par l'absurde et raisonnement par analyse-synthèse : non cités par le programme, d'usage courant, à savoir rédiger sans en faire un thème.
Hors programme signalé : réunions et intersections infinies, ensemble des parties comme objet d'étude, cardinaux (vus en dénombrement), théorie axiomatique.

Clés de démonstration

De Morgan logique. On dresse la table des quatre couples de valeurs de P et Q. « non (P et Q) » n'est fausse que si P et Q sont toutes deux vraies, exactement comme « non P ou non Q ». L'astuce : ne jamais raisonner « au sens », toujours par table.

Contraposition. P ⇒ Q s'écrit « non P ou Q ». La contraposée « non Q ⇒ non P » s'écrit « Q ou non P ». C'est la même assertion, le « ou » étant commutatif. Trois lignes suffisent.

De Morgan ensembliste. Soit x dans le complémentaire de A ∪ B. Alors x n'est pas dans A ∪ B, donc non (x ∈ A ou x ∈ B), donc x ∉ A et x ∉ B par De Morgan logique, donc x ∈ Ā ∩ B̄. Chaque étape est une équivalence, la double inclusion est donc obtenue d'un coup. L'astuce : traduire l'appartenance en assertion logique, appliquer la règle logique, retraduire.

Distributivité ensembliste. Même schéma, x ∈ A ∩ (B ∪ C) se traduit par « x ∈ A et (x ∈ B ou x ∈ C) », on applique la distributivité logique, on retraduit.

Négation quantifiée. On échange les quantificateurs de gauche à droite sans toucher aux ensembles, puis on nie la propriété finale. L'astuce : nier « ≤ » donne « > », nier « = » donne « ≠ », nier une implication donne « hypothèse et non conclusion ».

Récurrence. Pourquoi ça marche : si P était fausse pour certains entiers, il y aurait un plus petit entier fautif n₁. Il n'est pas n₀ par initialisation, donc n₁ − 1 vérifie P, et l'hérédité donne P(n₁), contradiction. Ce n'est pas exigible, mais cela explique pourquoi les deux étapes sont indispensables.

Exemples et contre-exemples à connaître

« n multiple de 4 ⇒ n pair » est vraie, sa réciproque est fausse (n = 2). Une implication et sa réciproque sont indépendantes.
La négation de x > 0 est x ≤ 0, pas x < 0. La négation d'une inégalité stricte est large.
« ∀x ∈ R, ∃y ∈ R, y > x » est vraie (y = x + 1), « ∃y ∈ R, ∀x ∈ R, y > x » est fausse. L'ordre des quantificateurs change le sens.
La propriété « n = n + 1 » est héréditaire et fausse pour tout n : l'initialisation n'est jamais décorative.
« Toute famille de n réels est constante » : l'hérédité passe de n à n + 1 en comparant deux sous-familles de n réels qui se chevauchent, ce qui échoue quand n = 1 (elles ne se chevauchent pas). Une hérédité doit valoir pour tous les n à partir de n₀, sans exception.
√(x + 2) = x : élever au carré donne x = 2 ou x = −1, mais x = −1 ne convient pas. Élever au carré n'est qu'une implication.
Pour E = {1, 2, 3}, 1 ∈ E et {1} ⊂ E, mais « 1 ⊂ E » et « {1} ∈ E » sont fausses. On ne confond pas élément et partie.
A ∪ B = A ∪ C n'entraîne pas B = C : A = {1}, B = {1}, C = ∅. On ne « simplifie » pas une réunion.
« Si 1 = 2 alors 3 = 4 » est une implication vraie : une implication à hypothèse fausse est toujours vraie.
Le « ou » mathématique est inclusif : « x ≥ 0 ou x ≤ 0 » est vraie pour tout réel, et les deux membres sont vrais en 0.

Techniques du chapitre

Technique 1, nier mécaniquement. Mini-exercice : nier « ∀ε > 0, ∃N ∈ N, ∀n ≥ N, |u_n − l| ≤ ε ». Réponse : « ∃ε > 0, ∀N ∈ N, ∃n ≥ N, |u_n − l| > ε ». On a échangé les trois quantificateurs dans l'ordre et remplacé ≤ par >.

Technique 2, double inclusion. Mini-exercice : montrer A ∩ (A ∪ B) = A. Si x ∈ A ∩ (A ∪ B) alors x ∈ A. Réciproquement si x ∈ A alors x ∈ A ∪ B, donc x ∈ A ∩ (A ∪ B). Les deux inclusions sont établies.

Technique 3, contraposée. Mini-exercice : soit x ≥ 0, montrer que si x ∉ Q alors √x ∉ Q. Contraposée : si √x ∈ Q alors x = (√x)² est un quotient d'entiers, donc x ∈ Q. Réflexe : quand la conclusion commence par « non », contraposer.

Technique 4, contre-exemple. Mini-exercice : l'assertion « ∀n ∈ N, n² + n + 41 est premier » est-elle vraie ? Non, pour n = 41 le nombre 41² + 41 + 41 = 41 × 43 n'est pas premier. Un seul contre-exemple suffit, quarante exemples ne prouvent rien.

Technique 5, implication puis vérification. Mini-exercice : résoudre √(x + 1) = x − 1. Si x convient, alors x + 1 = (x − 1)², soit x² − 3x = 0, soit x ∈ {0, 3}. Vérification : x = 0 donne 1 = −1, faux. x = 3 donne 2 = 2, vrai. Une seule solution, 3.

Technique 6, récurrence pour encadrer une suite. Mini-exercice : u₀ = 0 et u_n+1 = √(2 + u_n). Montrer 0 ≤ u_n ≤ 2. Initialisation vraie. Si 0 ≤ u_n ≤ 2 alors 2 ≤ 2 + u_n ≤ 4, donc √2 ≤ u_n+1 ≤ 2 par croissance de la racine, donc 0 ≤ u_n+1 ≤ 2. Conclusion par récurrence.

Technique 7, disjonction des cas. Mini-exercice : montrer que n(n + 1) est pair pour tout entier n. Ou bien n est pair et le produit l'est, ou bien n est impair, alors n + 1 est pair et le produit l'est. Les deux cas couvrent tous les entiers.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1

Classiques de khôlle et concours · Khôlle

Nier les trois assertions suivantes, pour f définie sur un intervalle I et M réel : (a) ∀x ∈ I, f(x) ≤ M. (b) ∃M ∈ R, ∀x ∈ I, f(x) ≤ M. (c) ∀x ∈ I, ∀y ∈ I, (x ≤ y ⇒ f(x) ≤ f(y)).

Technique négation mécanique.

Voir le corrigé

(a) devient ∃x ∈ I, f(x) > M. En mots, M ne majore pas f.
(b) devient ∀M ∈ R, ∃x ∈ I, f(x) > M. En mots, f n'est pas majorée.
(c) devient ∃x ∈ I, ∃y ∈ I, (x ≤ y et f(x) > f(y)). En mots, f n'est pas croissante.

piège : Écrire pour (c) « f est décroissante ». Ne pas être croissante n'est pas être décroissante.

Exercice 2

Classiques de khôlle et concours · Khôlle

A et B parties d'un ensemble E. Montrer que le complémentaire de A ∩ B est Ā ∪ B̄. Traduire en probabilités.

Technique traduction logique puis double inclusion.

Voir le corrigé

Soit x ∈ E. x est dans le complémentaire de A ∩ B si et seulement si non (x ∈ A et x ∈ B).
Par De Morgan, cela équivaut à x ∉ A ou x ∉ B, c'est-à-dire x ∈ Ā ∪ B̄.
Chaque étape est une équivalence, donc les deux ensembles ont les mêmes éléments.
Traduction : « l'événement A et B n'est pas réalisé » est « A n'est pas réalisé ou B n'est pas réalisé ».

piège : Conclure après une seule inclusion, ou nier « et » par « et ».

Exercice 3. Soient A et B deux parties de E telles que A ∪ B = A ∩ B. Montrer A = B

Classiques de khôlle et concours · Khôlle

Technique double inclusion avec chaîne d'inclusions.

Voir le corrigé

On a toujours A ⊂ A ∪ B et A ∩ B ⊂ B.
Donc A ⊂ A ∪ B = A ∩ B ⊂ B, soit A ⊂ B.
Par symétrie des rôles, B ⊂ A. Donc A = B.

piège : Prendre un exemple et le croire général, ou oublier de dire que les rôles de A et B sont symétriques.

Exercice 4. Soient a et b réels tels que pour tout ε > 0, a ≤ b + ε. Montrer a ≤ b

Classiques de khôlle et concours · Khôlle

Technique contraposée, ou absurde.

Voir le corrigé

Supposons a > b. Posons ε = (a − b)/2, qui est strictement positif.
Alors b + ε = (a + b)/2 < a, ce qui contredit a ≤ b + ε.
Donc a ≤ b.

piège : Prendre ε = a − b, ce qui donne b + ε = a et ne contredit rien. Il faut un ε strictement plus petit que l'écart.

Exercice 5. Pour n ≥ 1, montrer 1² + 2² + … + n² = n(n + 1)(2n + 1)/6

Classiques de khôlle et concours · Khôlle

Technique récurrence simple sur une somme.

Voir le corrigé

Initialisation, n = 1 : la somme vaut 1, la formule donne 1 × 2 × 3/6 = 1.
Hérédité : soit n ≥ 1 tel que la formule vaut. La somme jusqu'à n + 1 vaut n(n + 1)(2n + 1)/6 + (n + 1)².
On factorise par (n + 1) : (n + 1)[n(2n + 1) + 6(n + 1)]/6 = (n + 1)(2n² + 7n + 6)/6.
Or 2n² + 7n + 6 = (n + 2)(2n + 3). On obtient (n + 1)(n + 2)(2n + 3)/6, qui est la formule au rang n + 1.
Conclusion par récurrence.

piège : Développer tout au lieu de factoriser par (n + 1), et se perdre dans le calcul.

Exercice 6. Reprendre u₀ = 0, u_n+1 = √(2 + u_n). Montrer que (u_n) est croissante

Classiques de khôlle et concours · Khôlle vers écrit

Technique récurrence sur une inégalité entre termes consécutifs.

Voir le corrigé

Propriété P(n) : u_n ≤ u_n+1. Initialisation : u₀ = 0 ≤ √2 = u₁.
Hérédité : si u_n ≤ u_n+1, alors 2 + u_n ≤ 2 + u_n+1, et ces deux nombres sont positifs d'après la technique 6. La racine carrée étant croissante sur R₊, u_n+1 ≤ u_n+2.
Conclusion : (u_n) est croissante et majorée par 2, elle converge (théorème de la limite monotone, chapitre suites).

piège : Écrire « la fonction racine est croissante donc la suite est croissante » sans récurrence.

Exercice 7

Classiques de khôlle et concours · Écrit, type Agro-Véto

Soit (u_n) définie par u₀ = 1 et, pour n ≥ 0, u_n+1 = u₀ + u₁ + … + u_n. Montrer que pour tout n ≥ 1, u_n = 2ⁿ⁻¹. On pourra raisonner par récurrence forte avec l'hypothèse « pour tout k entre 1 et n, u_k = 2^k−1 ».

Technique récurrence forte, l'hypothèse étant fournie.

Voir le corrigé

Initialisation : u₁ = u₀ = 1 = 2⁰.
Hérédité : soit n ≥ 1 tel que u_k = 2^k−1 pour tout k entre 1 et n.
Alors u_n+1 = u₀ + Σ_k=1ⁿ 2^k−1 = 1 + (2ⁿ − 1) = 2ⁿ, par la somme géométrique 1 + 2 + … + 2ⁿ⁻¹ = 2ⁿ − 1.
C'est la formule au rang n + 1. Conclusion par récurrence forte.

piège : N'utiliser que u_n = 2ⁿ⁻¹ alors que la définition de u_n+1 fait intervenir tous les termes précédents. L'hypothèse simple ne suffit pas.

Exercice 8

Classiques de khôlle et concours · Écrit, type G2E

Soit (u_n) définie par u₀ = 2, u₁ = 5 et u_n+2 = 5u_n+1 − 6u_n. Montrer que u_n = 2ⁿ + 3ⁿ pour tout n. On formulera une hypothèse portant sur deux rangs consécutifs.

Technique récurrence à deux pas.

Voir le corrigé

Propriété P(n) : u_n = 2ⁿ + 3ⁿ et u_n+1 = 2ⁿ⁺¹ + 3ⁿ⁺¹. Initialisation : u₀ = 2 = 1 + 1 et u₁ = 5 = 2 + 3.
Hérédité : supposons P(n). Alors u_n+2 = 5(2ⁿ⁺¹ + 3ⁿ⁺¹) − 6(2ⁿ + 3ⁿ) = 2ⁿ(10 − 6) + 3ⁿ(15 − 6) = 4 × 2ⁿ + 9 × 3ⁿ = 2ⁿ⁺² + 3ⁿ⁺².
Avec u_n+1 déjà connu, P(n + 1) est vraie. Conclusion.

piège : Initialiser avec un seul rang. Une relation à deux pas exige deux vérifications initiales.

Exercice 9. Inégalité de Bernoulli : pour x ≥ −1 et n ∈ N, (1 + x)ⁿ ≥ 1 + nx

Classiques de khôlle et concours · Écrit

Technique récurrence avec multiplication par un facteur positif.

Voir le corrigé

Initialisation : n = 0, les deux membres valent 1.
Hérédité : si (1 + x)ⁿ ≥ 1 + nx, on multiplie par 1 + x qui est positif ou nul car x ≥ −1. D'où (1 + x)ⁿ⁺¹ ≥ (1 + nx)(1 + x) = 1 + (n + 1)x + nx².
Comme nx² ≥ 0, on obtient (1 + x)ⁿ⁺¹ ≥ 1 + (n + 1)x. Conclusion.

piège : Multiplier une inégalité par 1 + x sans avoir dit où l'on utilise x ≥ −1. C'est le seul endroit où l'hypothèse sert, il faut le montrer.

Exercice 10

Classiques de khôlle et concours · Écrit, plus délicat

Pour A et B parties de E, montrer P(A ∩ B) = P(A) ∩ P(B), puis montrer que P(A ∪ B) = P(A) ∪ P(B) est fausse en général.

Technique double inclusion sur des ensembles d'ensembles, puis contre-exemple.

Voir le corrigé

Soit X ∈ P(A ∩ B), c'est-à-dire X ⊂ A ∩ B. Alors X ⊂ A et X ⊂ B, donc X ∈ P(A) ∩ P(B).
Réciproquement, si X ⊂ A et X ⊂ B, tout élément de X est dans A et dans B, donc X ⊂ A ∩ B.
Contre-exemple : A = {1}, B = {2}. L'ensemble {1, 2} appartient à P(A ∪ B) mais n'est ni inclus dans A ni dans B.
On a seulement l'inclusion P(A) ∪ P(B) ⊂ P(A ∪ B).

piège : Écrire x ∈ P(A) pour un élément x de A. Les éléments de P(A) sont des parties, pas des éléments.

Erreurs fréquentes

Enchaîner des ⇔ quand une étape n'est qu'une implication (carré, produit par une quantité pouvant être nulle). Faire la synthèse.
Écrire « supposons P(n) vraie pour tout n » dans l'hérédité : c'est la conclusion, pas l'hypothèse. On fixe un n.
Nier « ∀ » par « ∀ non » au lieu de « ∃ non », ou nier une inégalité stricte par une inégalité stricte.
Confondre réciproque et contraposée, et croire une réciproque démontrée quand l'implication l'est.
Utiliser des quantificateurs dans une phrase française (« ∀ les échantillons ») ou oublier l'ensemble de quantification. Le programme le proscrit.

Fiche de cours rédigée à partir du programme officiel de BCPST 1ère année (2021), partie « Outils 1 – Logique, ensembles et raisonnement ». Elle couvre la logique élémentaire, le vocabulaire des ensembles et le raisonnement par récurrence.

Logique, ensembles et raisonnement

Résumé en cinq points

1Logique élémentaire

1.1Assertion

1.2Négation

1.3Les connecteurs « et » et « ou »

1.4Implication

1.5Réciproque, contraposée

1.6Équivalence

2Vocabulaire des ensembles

2.1Ensemble, élément, appartenance

2.2Inclusion et égalité

2.3Réunion, intersection, complémentaire

2.4Couples, p-uplets, produit cartésien

3Quantificateurs

3.1Les deux quantificateurs

3.2Négation d'une assertion quantifiée

3.3L'ordre des quantificateurs

3.4Règles d'écriture

4Raisonnement par récurrence

4.1Le principe

4.2Récurrence forte

4.3Erreurs classiques

Méthodes

Ce qu'il faut savoir refaire en khôlle

Les résultats à connaître

Clés de démonstration

Exemples et contre-exemples à connaître

Techniques du chapitre

Exercices classiques corrigés

Exercice 1

Exercice 2

Exercice 3. Soient A et B deux parties de E telles que A ∪ B = A ∩ B. Montrer A = B

Exercice 4. Soient a et b réels tels que pour tout ε > 0, a ≤ b + ε. Montrer a ≤ b

Exercice 5. Pour n ≥ 1, montrer 1² + 2² + … + n² = n(n + 1)(2n + 1)/6

Exercice 6. Reprendre u₀ = 0, un+1 = √(2 + un). Montrer que (un) est croissante

Exercice 7

Exercice 8

Exercice 9. Inégalité de Bernoulli : pour x ≥ −1 et n ∈ N, (1 + x)ⁿ ≥ 1 + nx

Exercice 10

Erreurs fréquentes

Exercice 6. Reprendre u₀ = 0, u_n+1 = √(2 + u_n). Montrer que (u_n) est croissante