ECG approfondies · Chapitre 01 · Premier semestre

Raisonnement et vocabulaire ensembliste

1re année

Logique, récurrence, sommes et produits, ensembles et parties, applications, injectivité, surjectivité, bijectivité.

Sommaire

Ce qu'il faut savoir faire

Ce chapitre ouvre l'année, et ce n'est pas un hasard. Au lycée, on vous demandait surtout de calculer : résoudre une équation, dériver une fonction, déterminer une probabilité. En classe préparatoire, on vous demandera de démontrer, c'est-à-dire d'établir qu'un énoncé est vrai par un enchaînement d'arguments que le lecteur peut contrôler ligne à ligne. Cela suppose de savoir exactement ce que l'on affirme, ce que l'on suppose, et ce qu'il reste à établir. Nous allons donc commencer par préciser le sens des mots « ou », « si ... alors », « pour tout », « il existe », puis recenser les grandes manières de conduire une démonstration, avant de mettre en place le vocabulaire des ensembles et des applications. Rien de ce chapitre n'est spectaculaire, et pourtant tout y est essentiel : c'est la langue dans laquelle seront écrits les chapitres suivants. En probabilités, un événement sera une partie d'un univers, et les opérations sur les événements seront exactement la réunion, l'intersection et le passage au complémentaire. En algèbre linéaire, une application linéaire sera d'abord une application, et l'injectivité comme la surjectivité seront des énoncés quantifiés. Un étudiant qui manipule mal les quantificateurs ne pourra pas rédiger correctement une démonstration au second semestre, quelle que soit sa virtuosité calculatoire.

Les notations suivantes sont fixées une fois pour toutes et ne changeront plus dans ce chapitre. Les lettres $E$ , $F$ , $G$ désignent des ensembles ; les lettres $A$ , $B$ , $C$ désignent des parties d'un ensemble ; $P (E)$ est l'ensemble des parties de $E$ ; $\overline{A}$ est le complémentaire de $A$ dans un ensemble de référence ; $A ∖ B$ est la différence de $A$ et $B$ ; $A Δ B$ est leur différence symétrique ; $1_{A}$ est la fonction indicatrice de $A$ ; $f : E \to F$ est une application de $E$ dans $F$ ; ${i d}_{E}$ est l'application identité de $E$ ; $f_{∣ A}$ est la restriction de $f$ à une partie $A$ ; $f (A)$ est l'image directe de $A$ par $f$ ; $f^{- 1} (B)$ est l'image réciproque de $B$ par $f$ ; $F (E, F)$ est l'ensemble des applications de $E$ dans $F$ ; $\emptyset$ est l'ensemble vide. L'ensemble des entiers compris entre $1$ et $n$ sera toujours noté ${1, 2, \dots, n}$ : certains ouvrages utilisent des doubles crochets pour le désigner, nous ne les emploierons pas, afin que toutes les notations de ce cours restent lisibles sans convention supplémentaire. Enfin, du côté de la logique, $\forall$ se lit « pour tout », $\exists$ se lit « il existe », $\exists!$ se lit « il existe un unique », $\neg P$ désigne la négation de l'assertion $P$ , le symbole $⟹$ note l'implication, le symbole $⟺$ note l'équivalence, et le symbole $□$ marque la fin d'une démonstration.

Éléments de logique

Cette première section n'a pas pour but de faire de la logique pour elle-même, ce qui serait hors de propos, mais de fixer le sens précis d'un petit nombre de mots que nous emploierons chaque jour. Il faut la lire lentement : presque toutes les erreurs de rédaction commises en première année viennent d'un flottement sur l'un de ces mots.

Assertions et connecteurs

Définition

Une assertion (on dit aussi une proposition) est un énoncé mathématique dont on peut affirmer sans ambiguïté qu'il est vrai ou qu'il est faux. On appelle valeur de vérité de l'assertion le fait qu'elle soit vraie (on note $V$ ) ou fausse (on note $F$ ). Une assertion ne peut pas être à la fois vraie et fausse, et il n'existe pas de troisième valeur possible.

Voici quelques assertions, avec leur valeur de vérité.

a. « $2 + 2 = 4$ » : vraie.

b. « $3 ⩽ 5$ » : vraie.

c. « $\sqrt{2} \in Q$ » : fausse.

d. « $(- 3)^{2} = 9$ » : vraie.

e. « $0 \in \emptyset$ » : fausse.

f. « $N \subset R$ » : vraie.

Remarque

L'énoncé « $x > 0$ » n'est pas une assertion tant que $x$ n'a pas été fixé : sa valeur de vérité dépend de $x$ . Un tel énoncé, dont la vérité dépend d'une ou de plusieurs variables, s'appelle un prédicat et se note $P (x)$ , ou $P (x, y)$ s'il dépend de deux variables. Un prédicat devient une assertion de deux façons : soit en fixant la variable (« pour $x = 3$ , l'énoncé $x > 0$ est vrai »), soit en quantifiant la variable, ce que nous verrons dans la sous-section consacrée aux quantificateurs.

À partir d'assertions déjà construites, on en fabrique de nouvelles à l'aide des connecteurs logiques.

Définition

Soient $P$ et $Q$ deux assertions.

La négation de $P$ , notée $\neg P$ et lue « non $P$ », est l'assertion qui est vraie lorsque $P$ est fausse, et fausse lorsque $P$ est vraie.
La conjonction de $P$ et $Q$ , notée « $P$ et $Q$ », est l'assertion qui est vraie lorsque $P$ et $Q$ sont toutes les deux vraies, et fausse dans tous les autres cas.
La disjonction de $P$ et $Q$ , notée « $P$ ou $Q$ », est l'assertion qui est vraie lorsque l'une au moins des deux assertions est vraie, et fausse lorsque les deux sont fausses.

Ces trois définitions se résument dans une table de vérité, c'est-à-dire un tableau qui énumère tous les cas possibles pour les assertions de départ et donne, pour chacun d'eux, la valeur de vérité de l'assertion construite. Avec deux assertions $P$ et $Q$ , il y a quatre cas.

\begin{array}{ccccc} P & Q & \neg P & P et Q & P ou Q \\ V & V & F & V & V \\ V & F & F & F & V \\ F & V & V & F & V \\ F & F & V & F & F \end{array}

Une table de vérité est un outil de démonstration à part entière : deux assertions construites à partir de $P$ et $Q$ sont interchangeables dès que leurs colonnes coïncident ligne à ligne. Nous dirons alors qu'elles ont la même valeur de vérité, quelles que soient les valeurs de vérité de $P$ et de $Q$ .

Remarque

Le « ou » mathématique est inclusif : l'assertion « $P$ ou $Q$ » n'exclut pas que $P$ et $Q$ soient vraies en même temps. C'est une différence avec l'usage courant du français, où « fromage ou dessert » signifie en général « l'un des deux, mais pas les deux ». Ainsi, l'assertion « $2$ est pair ou $2 < 3$ » est vraie, bien que ses deux membres soient vrais simultanément. Lorsque l'on veut exprimer un « ou » exclusif, on l'écrit explicitement, par exemple sous la forme « $P$ ou $Q$ , et pas les deux ».

Remarque

Un point de vocabulaire qui déroute souvent : dire « $x = 2$ ou $x = 3$ » ne signifie pas que l'on hésite, ni que l'on n'a pas terminé le travail. C'est une assertion parfaitement précise, qui décrit exactement la situation où $x$ prend l'une de ces deux valeurs. De même, l'ensemble des solutions de l'équation $(x - 2) (x - 3) = 0$ est ${2, 3}$ , et non « $2$ , ou bien $3$ , selon les cas ».

Propriété

Soient $P$ , $Q$ , $R$ trois assertions. Dans chacun des cas suivants, les deux assertions citées ont la même valeur de vérité, quelles que soient les valeurs de vérité de $P$ , $Q$ et $R$ .

Double négation : $\neg (\neg P)$ et $P$ .
Commutativité : « $P$ et $Q$ » et « $Q$ et $P$ » ; « $P$ ou $Q$ » et « $Q$ ou $P$ ».
Loi de De Morgan, négation d'une conjonction : $\neg (P et Q)$ et « $\neg P$ ou $\neg Q$ ».
Loi de De Morgan, négation d'une disjonction : $\neg (P ou Q)$ et « $\neg P$ et $\neg Q$ ».
Distributivité de « et » sur « ou » : « $P$ et $(Q$ ou $R)$ » et « $(P$ et $Q)$ ou $(P$ et $R)$ ».
Distributivité de « ou » sur « et » : « $P$ ou $(Q$ et $R)$ » et « $(P$ ou $Q)$ et $(P$ ou $R)$ ».

Démonstration. Le principe est toujours le même : on écrit une table de vérité comportant une colonne pour chacune des deux assertions à comparer, et on constate que ces deux colonnes coïncident ligne à ligne. Traitons complètement les points 3, 4 et 5.

Pour le point 3, la table est la suivante.

\begin{array}{ccccccc} P & Q & P et Q & \neg (P et Q) & \neg P & \neg Q & \neg P ou \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 \end{array}

La quatrième colonne et la septième colonne sont identiques : elles valent successivement $F$ , $V$ , $V$ , $V$ . Les assertions $\neg (P et Q)$ et « $\neg P$ ou $\neg Q$ » ont donc bien la même valeur de vérité dans les quatre cas possibles.

Pour le point 4, on procède de même.

\begin{array}{ccccccc} P & Q & P ou Q & \neg (P ou Q) & \neg P & \neg Q & \neg P et \neg Q \\ V & V & V & F & F & F & F \\ V & F & V & F & F & V & F \\ F & V & V & F & V & F & F \\ F & F & F & V & V & V & V \end{array}

Là encore, la quatrième et la septième colonne coïncident : elles valent $F$ , $F$ , $F$ , $V$ .

Pour le point 5, il y a trois assertions de départ, donc huit cas à examiner. Afin d'alléger l'écriture du tableau, notons $S$ l'assertion « $P$ et $(Q$ ou $R)$ », et $T$ l'assertion « $(P$ et $Q)$ ou $(P$ et $R)$ ».

\begin{array}{cccccccc} P & Q & R & Q ou R & S & P et Q & P et R & T \\ 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 \end{array}

Les colonnes de $S$ et de $T$ sont identiques dans les huit lignes. Les points 1, 2 et 6 se démontrent exactement de la même manière, en écrivant la table correspondante ; nous laissons ce travail au lecteur, qui a tout intérêt à le faire au moins une fois lui-même. $□$

Exemple

Appliquons ces règles à des énoncés concrets.

a. Soit $x$ un réel. La négation de l'assertion « $x ⩾ 0$ et $x ⩽ 1$ », c'est-à-dire de « $x$ appartient à l'intervalle $[0, 1]$ », est l'assertion « $x < 0$ ou $x > 1$ ». Remarquez que la négation d'un « et » produit bien un « ou » : un réel qui n'est pas dans $[0, 1]$ manque à l'une des deux conditions, mais pas nécessairement aux deux.

b. Soit $x$ un réel. La négation de l'assertion « $x = 2$ ou $x = 3$ » est l'assertion « $x \neq 2$ et $x \neq 3$ ».

c. Soit $n$ un entier. La négation de l'assertion « $n$ est pair et $n ⩾ 10$ » est l'assertion « $n$ est impair ou $n < 10$ ».

d. Soit $x$ un réel. D'après la distributivité, l'assertion « $x ⩾ 0$ et $(x = 1$ ou $x = - 1)$ » a la même valeur de vérité que l'assertion « $(x ⩾ 0$ et $x = 1)$ ou $(x ⩾ 0$ et $x = - 1)$ ». Comme la seconde parenthèse est toujours fausse, le tout se réduit à l'assertion « $x = 1$ ».

Remarque

Ces règles ne sont pas à étudier pour elles-mêmes. Elles servent en permanence, souvent sans qu'on les cite : chaque fois que vous écrivez la négation d'une hypothèse pour raisonner par l'absurde, chaque fois que vous traduisez « ce nombre n'est ni positif ni nul », vous appliquez une loi de De Morgan. Les mêmes formules réapparaîtront d'ailleurs presque mot pour mot dans la section consacrée aux ensembles, avec le complémentaire à la place de la négation, la réunion à la place du « ou » et l'intersection à la place du « et ». Ce n'est pas une coïncidence.

Implication, réciproque, contraposée

L'implication est le connecteur le plus important du cours, et aussi celui qui donne lieu au plus grand nombre de malentendus.

Définition

Soient $P$ et $Q$ deux assertions. L'assertion « $P ⟹ Q$ », lue « $P$ implique $Q$ » ou « si $P$ , alors $Q$ », est par définition l'assertion « $\neg P$ ou $Q$ ». Elle est donc fausse dans le seul cas où $P$ est vraie et $Q$ est fausse, et vraie dans les trois autres cas.

Lorsque l'implication $P ⟹ Q$ est vraie, on dit que $P$ est une condition suffisante pour $Q$ , et que $Q$ est une condition nécessaire pour $P$ .

La table de vérité de l'implication mérite d'être connue par cœur.

\begin{array}{ccccc} P & Q & \neg P & \neg P ou Q & P ⟹ Q \\ V & V & F & V & V \\ V & F & F & F & F \\ F & V & V & V & V \\ F & F & V & V & V \end{array}

Remarque

Une implication dont l'hypothèse est fausse est vraie, quelle que soit sa conclusion. L'assertion « si $1 = 2$ , alors $3 = 4$ » est donc vraie, et l'assertion « si $1 = 2$ , alors $3 = 3$ » l'est également. Cette convention surprend toujours au début, mais elle est indispensable. Considérez en effet l'énoncé « pour tout réel $x$ , si $x ⩾ 2$ alors $x^{2} ⩾ 4$ », que chacun souhaite déclarer vrai. Cet énoncé parle de tous les réels, y compris de $x = 0$ , pour lequel l'hypothèse $x ⩾ 2$ est fausse. Si une implication à hypothèse fausse n'était pas vraie, l'énoncé serait faux, ce qui n'aurait aucun sens.

On parle d'implication vide lorsque l'hypothèse n'est jamais réalisée. Ce cas resservira dans la section sur les ensembles, pour établir que l'ensemble vide est inclus dans n'importe quel ensemble.

Remarque

L'implication est une assertion, pas une déduction en cours d'écriture. Le symbole $⟹$ ne doit jamais être employé à la place du mot « donc » dans une phrase rédigée. Écrire « $x = 3 ⟹ x^{2} = 9 ⟹$ conclusion » est une suite de symboles, pas une rédaction. On écrit : « Comme $x = 3$ , on a $x^{2} = 9$ , donc ... ». Le symbole $⟹$ est réservé aux énoncés que l'on manipule en tant que tels, par exemple pour en former la contraposée ou la négation.

Définition

Soit une implication $P ⟹ Q$ .

Sa réciproque est l'implication $Q ⟹ P$ .
Sa contraposée est l'implication $\neg Q ⟹ \neg P$ .

Propriété

Soient $P$ et $Q$ deux assertions.

L'implication $P ⟹ Q$ et sa contraposée $\neg Q ⟹ \neg P$ ont toujours la même valeur de vérité.
La négation de $P ⟹ Q$ est l'assertion « $P$ et $\neg Q$ ».

Démonstration. Pour le point 1, écrivons la table de vérité des deux implications.

\begin{array}{cccccc} P & Q & P ⟹ Q & \neg P & \neg Q & \neg Q ⟹ \neg P \\ V & V & V & F & F & V \\ V & F & F & F & V & F \\ F & V & V & V & F & V \\ F & F & V & V & V & V \end{array}

Détaillons la dernière colonne, qui est celle où l'on se trompe. À la première ligne, $\neg Q$ est fausse, donc l'implication $\neg Q ⟹ \neg P$ est vraie. À la deuxième ligne, $\neg Q$ est vraie et $\neg P$ est fausse : c'est l'unique configuration qui rend une implication fausse. Aux troisième et quatrième lignes, $\neg P$ est vraie, donc l'implication est vraie. La troisième colonne et la sixième colonne valent toutes deux $V$ , $F$ , $V$ , $V$ : elles coïncident.

Pour le point 2, écrivons de même la table.

\begin{array}{cccccc} P & Q & P ⟹ Q & \neg (P ⟹ Q) & \neg Q & P et \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 \end{array}

La quatrième et la sixième colonne coïncident : elles valent $F$ , $V$ , $F$ , $F$ .

On peut aussi obtenir ces deux résultats sans tableau, en revenant à la définition. L'implication $P ⟹ Q$ est l'assertion « $\neg P$ ou $Q$ » ; sa négation est donc, par la loi de De Morgan, l'assertion « $\neg (\neg P)$ et $\neg Q$ », c'est-à-dire « $P$ et $\neg Q$ » par double négation, ce qui redonne le point 2. Quant à la contraposée $\neg Q ⟹ \neg P$ , elle est par définition l'assertion « $\neg (\neg Q)$ ou $\neg P$ », c'est-à-dire « $Q$ ou $\neg P$ », qui est bien la même que « $\neg P$ ou $Q$ » par commutativité de la disjonction. $□$

Remarque

Piège classique : la contraposée et la réciproque n'ont rien à voir. La contraposée d'une implication a toujours la même valeur de vérité que cette implication : la démontrer, c'est démontrer l'implication de départ, ni plus ni moins. La réciproque, elle, est une assertion nouvelle, qui peut parfaitement être fausse alors que l'implication de départ est vraie. Confondre les deux est l'une des fautes les plus fréquentes en début d'année, et elle est lourdement sanctionnée, car elle revient à démontrer autre chose que ce qui était demandé.

Exemple

Considérons, pour un entier relatif $n$ , l'implication « si $n^{2}$ est pair, alors $n$ est pair ».

Sa réciproque est : « si $n$ est pair, alors $n^{2}$ est pair ». Elle est vraie, et immédiate : si $n = 2 k$ avec $k$ entier, alors $n^{2} = 4 k^{2} = 2 \times (2 k^{2})$ , qui est pair.
Sa contraposée est : « si $n$ n'est pas pair, alors $n^{2}$ n'est pas pair », autrement dit « si $n$ est impair, alors $n^{2}$ est impair ». Elle est vraie, et c'est précisément par elle que nous démontrerons l'implication de départ, dans la sous-section consacrée au raisonnement par contraposée.
Sa négation est : « $n^{2}$ est pair et $n$ est impair ». Pour réfuter l'implication de départ, il faudrait exhiber un entier vérifiant ces deux conditions à la fois. Nous verrons que c'est impossible, puisque l'implication est vraie.

Définition

Soient $P$ et $Q$ deux assertions. L'assertion « $P ⟺ Q$ », lue « $P$ équivaut à $Q$ », ou « $P$ si et seulement si $Q$ », est vraie lorsque $P$ et $Q$ ont la même valeur de vérité, et fausse sinon. On dit alors que $P$ est une condition nécessaire et suffisante pour $Q$ , et réciproquement.

Propriété

Pour toutes assertions $P$ et $Q$ , l'assertion $P ⟺ Q$ a la même valeur de vérité que l'assertion « $(P ⟹ Q)$ et $(Q ⟹ P)$ ».

Démonstration. Écrivons la table de vérité.

\begin{array}{cccccc} P & Q & P ⟺ Q & P ⟹ Q & Q ⟹ P & (P ⟹ Q) et (Q ⟹ P) \\ V & V & V & V & V & V \\ V & F & F & F & V & F \\ F & V & F & V & F & F \\ F & F & V & V & V & V \end{array}

La troisième et la sixième colonne coïncident : elles valent $V$ , $F$ , $F$ , $V$ . $□$

C'est ce résultat, et lui seul, qui justifie la méthode de démonstration par double implication : pour établir une équivalence, il suffit d'établir deux implications.

Le vocabulaire « nécessaire » et « suffisant » est constamment employé dans les énoncés de concours. Il faut être capable de le traduire instantanément.

a. Pour qu'un réel $x$ vérifie $x^{2} = 4$ , il suffit que $x = 2$ . Autrement dit, $x = 2 ⟹ x^{2} = 4$ . La condition $x = 2$ n'est en revanche pas nécessaire, puisque $x = - 2$ convient aussi.

b. Pour qu'un réel $x$ vérifie $x = 2$ , il faut que $x^{2} = 4$ . Autrement dit, $x = 2 ⟹ x^{2} = 4$ , lue dans l'autre sens : la condition $x^{2} = 4$ est nécessaire, mais elle n'est pas suffisante.

Remarquez que les deux phrases précédentes traduisent la même implication. Une condition suffisante figure à gauche de la flèche, une condition nécessaire à sa droite : voilà tout ce qu'il faut retenir.

Méthode

Comment démontrer une implication $P ⟹ Q$ . Trois stratégies, à choisir selon la forme des assertions.

Directement : on suppose $P$ vraie, et on en déduit $Q$ par une suite de déductions. Rédaction type : « Supposons $P$ . Alors ... Donc $Q$ . »
Par contraposée : on démontre $\neg Q ⟹ \neg P$ , ce qui revient au même. On y pense lorsque l'hypothèse $\neg Q$ est plus exploitable que l'hypothèse $P$ .
Par l'absurde : on suppose $P$ vraie et $Q$ fausse en même temps, et on cherche une contradiction.

Dans les trois cas, la première phrase de la démonstration annonce la stratégie choisie. Un correcteur doit savoir dès la première ligne ce que vous supposez.

Méthode

Comment démontrer une équivalence $P ⟺ Q$ . Deux stratégies.

Par double implication : on démontre séparément $P ⟹ Q$ , puis $Q ⟹ P$ . On annonce clairement chaque sens, par exemple par les symboles $(⟹)$ et $(⟸)$ , ou par les mots « sens direct » et « réciproque ». C'est la méthode par défaut, celle qui ne trompe jamais.
Par équivalences successives : on enchaîne des assertions reliées par le symbole $⟺$ . Cette rédaction est plus courte, mais elle engage à ce que chaque étape soit réversible, ce qui doit être vrai et pas seulement souhaité.

Mise en garde : élever au carré n'est pas une opération réversible. L'égalité $a = b$ entraîne $a^{2} = b^{2}$ , mais la réciproque est fausse, comme le montre le couple $a = 1$ et $b = - 1$ . De même, multiplier les deux membres d'une équation par une quantité qui peut être nulle, ou appliquer une fonction qui n'est pas injective, brise l'équivalence. Au moindre doute, revenez à la double implication, ou bien menez le calcul par implications simples et vérifiez ensuite les candidats obtenus.

Quantificateurs

Un prédicat $P (x)$ n'est pas une assertion. Pour en faire une, on peut fixer la variable, ou bien la quantifier.

Définition

Soit $P (x)$ un prédicat portant sur les éléments d'un ensemble $E$ .

Quantificateur universel : l'assertion $\forall x \in E, P (x)$ , lue « pour tout $x$ appartenant à $E$ , $P (x)$ », est vraie lorsque $P (x)$ est vraie pour chacun des éléments $x$ de $E$ , et fausse sinon.
Quantificateur existentiel : l'assertion $\exists x \in E, P (x)$ , lue « il existe un élément $x$ de $E$ tel que $P (x)$ », est vraie lorsqu'au moins un élément $x$ de $E$ rend $P (x)$ vraie, et fausse sinon.
Quantificateur d'existence et d'unicité : l'assertion $\exists! x \in E, P (x)$ , lue « il existe un unique élément $x$ de $E$ tel que $P (x)$ », est vraie lorsqu'exactement un élément $x$ de $E$ rend $P (x)$ vraie.

Remarque

La variable quantifiée est muette : les assertions $\forall x \in R, x^{2} ⩾ 0$ et $\forall t \in R, t^{2} ⩾ 0$ sont exactement la même assertion, écrite avec des lettres différentes. En revanche, une lettre libre, c'est-à-dire non quantifiée, doit toujours avoir été introduite auparavant. Écrire « $x^{2} ⩾ 0$ » sans avoir dit qui est $x$ n'a aucun sens, pas plus que d'écrire « $u_{n} ⩽ M$ » sans avoir précisé ni $n$ , ni $M$ .

Remarque

Le domaine du quantificateur ne s'oublie jamais. L'assertion $\forall x, x^{2} ⩾ x$ n'a pas de sens tant que l'on n'a pas dit où vit $x$ : elle est vraie si $x$ décrit $N$ , et fausse si $x$ décrit $R$ , puisque ${(\frac{1}{2})}^{2} = \frac{1}{4} < \frac{1}{2}$ . On écrit donc systématiquement $\forall x \in E$ , et jamais $\forall x$ tout seul.

Remarque

Les quantificateurs ne sont pas des abréviations de français. Dans un texte rédigé, on écrit « pour tout réel $x$ » ou « il existe un entier $n$ tel que », en toutes lettres. Les symboles $\forall$ et $\exists$ sont réservés à l'écriture formelle d'un énoncé que l'on veut manipuler, typiquement pour le nier. Une copie où l'on lit « $\forall$ solution $x$ , $\exists$ une racine donc $x > 0$ » est une copie mal rédigée : ces symboles ne remplacent ni un verbe, ni le mot « donc ».

Remarque

L'assertion $\exists! x \in E, P (x)$ se démontre toujours en deux temps, qui sont deux démonstrations distinctes : d'abord l'existence d'un élément convenable, ensuite l'unicité, c'est-à-dire le fait que deux éléments convenables sont nécessairement égaux. Pour l'unicité, la rédaction correcte consiste à se donner $x$ et $x^{'}$ dans $E$ vérifiant tous deux $P$ , puis à démontrer que $x = x^{'}$ .

Exemple

Démontrons l'assertion $\exists! x \in R, 3 x + 2 = 5$ , afin de voir à quoi ressemble une rédaction en deux temps.

Existence. Posons $x = 1$ . Ce nombre est bien un réel, et $3 \times 1 + 2 = 5$ : il convient.

Unicité. Soient $x$ et $x^{'}$ deux réels vérifiant $3 x + 2 = 5$ et $3 x^{'} + 2 = 5$ . En retranchant ces deux égalités membre à membre, on obtient $3 x - 3 x^{'} = 0$ , c'est-à-dire $3 (x - x^{'}) = 0$ , donc $x - x^{'} = 0$ puisque $3 \neq 0$ , et finalement $x = x^{'}$ .

Il existe donc un unique réel $x$ tel que $3 x + 2 = 5$ , à savoir $x = 1$ . Notez la structure de la partie unicité : on ne suppose pas connaître la solution, on se donne deux solutions éventuelles et on démontre qu'elles sont égales. $□$

L'ordre dans lequel on écrit deux quantificateurs de natures différentes change le sens de l'énoncé. C'est le point le plus délicat de cette sous-section, et il faut y consacrer le temps nécessaire.

Propriété

Deux quantificateurs de même nature peuvent être échangés sans changer le sens : les assertions $\forall x \in E, \forall y \in E, P (x, y)$ et $\forall y \in E, \forall x \in E, P (x, y)$ ont la même valeur de vérité, et il en va de même pour deux quantificateurs existentiels consécutifs. En revanche, on ne peut jamais échanger un $\forall$ et un $\exists$ : cela produit en général une assertion de sens différent.

Exemple

Comparons deux énoncés qui ne diffèrent que par l'ordre de leurs quantificateurs. Le premier est

\forall x \in R, \exists y \in R, x + y = 0.

Cet énoncé est vrai. En effet, soit $x$ un réel quelconque. Posons $y = - x$ : ce nombre est bien un réel, et $x + y = x - x = 0$ . L'élément $y$ dépend de $x$ , ce qui est parfaitement licite, puisqu'il est choisi après $x$ .

Le second énoncé est

\exists y \in R, \forall x \in R, x + y = 0.

Cet énoncé est faux. Il réclame en effet un réel $y$ , choisi avant $x$ , donc unique et valable pour tous les $x$ à la fois. Un tel $y$ devrait vérifier $0 + y = 0$ en prenant $x = 0$ , donc $y = 0$ , et aussi $1 + y = 0$ en prenant $x = 1$ , donc $y = - 1$ . Comme $0 \neq - 1$ , un tel réel n'existe pas.

La règle à retenir tient en une phrase : dans un énoncé quantifié, chaque objet ne peut dépendre que de ceux qui ont été introduits avant lui.

Exemple

Voici un second exemple, tout aussi parlant. L'assertion

\forall x \in R, \exists y \in R, y > x

est vraie : $x$ étant donné, le réel $y = x + 1$ convient. L'assertion obtenue en échangeant les deux quantificateurs,

\exists y \in R, \forall x \in R, y > x,

affirme au contraire qu'il existe un réel plus grand que tous les réels. Elle est fausse : un tel $y$ vérifierait en particulier $y > y$ en prenant $x = y$ , ce qui est absurde.

Propriété

Soit $P (x)$ un prédicat portant sur les éléments d'un ensemble $E$ . Alors :

l'assertion $\neg (\forall x \in E, P (x))$ a la même valeur de vérité que l'assertion $\exists x \in E, \neg P (x)$ ;
l'assertion $\neg (\exists x \in E, P (x))$ a la même valeur de vérité que l'assertion $\forall x \in E, \neg P (x)$ .

Démonstration. Traitons la première règle, en raisonnant sur le sens des énoncés, puisqu'un ensemble $E$ quelconque ne permet pas d'écrire une table de vérité à un nombre fini de lignes.

Supposons d'abord que $\neg (\forall x \in E, P (x))$ soit vraie. Cela signifie que l'assertion « tous les éléments de $E$ vérifient $P$ » est fausse. Or, pour qu'un énoncé universel soit faux, il faut et il suffit qu'au moins un élément de $E$ le mette en défaut, c'est-à-dire qu'il existe un élément $x_{0}$ de $E$ pour lequel $P (x_{0})$ est fausse. C'est exactement dire que $\exists x \in E, \neg P (x)$ est vraie.

Réciproquement, supposons que $\exists x \in E, \neg P (x)$ soit vraie, et notons $x_{0}$ un élément de $E$ tel que $P (x_{0})$ soit fausse. Alors l'assertion $\forall x \in E, P (x)$ ne peut pas être vraie, puisqu'elle affirmerait en particulier que $P (x_{0})$ est vraie. Donc sa négation est vraie.

Les deux assertions sont donc simultanément vraies, et par conséquent simultanément fausses : elles ont bien la même valeur de vérité.

La seconde règle se déduit de la première appliquée au prédicat $\neg P$ , en utilisant la double négation. On peut aussi la lire directement : dire qu'il n'existe aucun élément de $E$ vérifiant $P$ , c'est dire que tous les éléments de $E$ vérifient $\neg P$ . $□$

Méthode

Nier une assertion quantifiée. On procède mécaniquement, de la gauche vers la droite, sans jamais changer l'ordre des quantificateurs.

Remplacer chaque $\forall$ par un $\exists$ et chaque $\exists$ par un $\forall$ , en conservant l'ordre et les ensembles.
Nier la propriété finale, celle qui ne contient plus de quantificateur.
Pour cette dernière étape, appliquer les règles usuelles : la négation de « et » est « ou », celle de « ou » est « et », celle de $P ⟹ Q$ est « $P$ et $\neg Q$ », celle de $⩽$ est $>$ , celle de $<$ est $⩾$ , celle de $=$ est $\neq$ .
Relire l'assertion obtenue en français, pour vérifier qu'elle a un sens.

L'erreur à ne jamais commettre est de nier « $\forall x \in E$ » en « $\forall x \notin E$ », ou en « $\exists x \notin E$ ». L'ensemble sur lequel on quantifie n'est jamais modifié par la négation.

Exemple

Nions quelques assertions courantes.

a. « Tout réel est positif ou nul », c'est-à-dire $\forall x \in R, x ⩾ 0$ . Sa négation est $\exists x \in R, x < 0$ . Cette négation est vraie, comme le montre $x = - 1$ : l'assertion de départ est donc fausse.

b. « L'équation $x^{2} + 1 = 0$ possède une solution réelle », c'est-à-dire $\exists x \in R, x^{2} + 1 = 0$ . Sa négation est $\forall x \in R, x^{2} + 1 \neq 0$ . Cette négation est vraie, car pour tout réel $x$ on a $x^{2} ⩾ 0$ , donc $x^{2} + 1 ⩾ 1 > 0$ .

c. Soit $f : R \to R$ . L'assertion « $f$ s'annule » s'écrit $\exists x \in R, f (x) = 0$ , et sa négation est $\forall x \in R, f (x) \neq 0$ .

d. Soient $E$ un ensemble et $f : E \to R$ . L'assertion « $f$ est constante » s'écrit

\exists c \in R, \forall x \in E, f (x) = c,

et sa négation est

\forall c \in R, \exists x \in E, f (x) \neq c .

Exemple

Un exemple à connaître : une suite majorée. Soit $(u_{n})_{n \in N}$ une suite réelle. Dire que la suite $(u_{n})$ est majorée signifie qu'il existe un réel qui est supérieur ou égal à tous ses termes, ce qui s'écrit

\exists M \in R, \forall n \in N, u_{n} ⩽ M .

L'ordre des quantificateurs est ici essentiel : le majorant $M$ est choisi avant l'indice $n$ , donc il ne dépend pas de $n$ . Écrire $\forall n \in N, \exists M \in R, u_{n} ⩽ M$ ne signifierait rien d'intéressant, car un tel $M$ existe toujours pour un terme donné : il suffit de prendre $M = u_{n}$ .

En appliquant la méthode, la négation de « la suite $(u_{n})$ est majorée » est

\forall M \in R, \exists n \in N, u_{n} > M .

En français : quelle que soit la barre $M$ que l'on se fixe, il se trouve au moins un terme de la suite qui la dépasse strictement.

Vérifions ces deux écritures sur des exemples. La suite définie par $u_{n} = 1 - \frac{1}{n + 1}$ est majorée : pour tout entier naturel $n$ , on a $\frac{1}{n + 1} > 0$ , donc $u_{n} < 1$ , et le réel $M = 1$ convient. À l'inverse, la suite définie par $u_{n} = n^{2}$ n'est pas majorée. Soit en effet $M$ un réel quelconque. Comme $N$ n'est pas majoré dans $R$ , propriété que nous admettons, il existe un entier naturel $n$ tel que $n > M$ et $n ⩾ 1$ ; pour un tel $n$ , on a $u_{n} = n^{2} = n \times n ⩾ n > M$ .

Il reste un cas à traiter, qui revient constamment : celui d'une implication placée sous un quantificateur.

Propriété

Soient $E$ un ensemble et $P (x)$ , $Q (x)$ deux prédicats sur $E$ . La négation de l'assertion

\forall x \in E, (P (x) ⟹ Q (x))

est l'assertion

\exists x \in E, (P (x) et \neg Q (x)) .

Démonstration. D'après la règle de négation d'un quantificateur universel, la négation de l'assertion de départ est $\exists x \in E, \neg (P (x) ⟹ Q (x))$ . Or la négation d'une implication est la conjonction de son hypothèse et de la négation de sa conclusion, d'après la propriété démontrée dans la sous-section précédente. On obtient donc bien $\exists x \in E, (P (x) et \neg Q (x))$ . $□$

Exemple

Considérons l'assertion

\forall x \in R, (x^{2} = 1 ⟹ x = 1) .

Sa négation est

\exists x \in R, (x^{2} = 1 et x \neq 1) .

Cette négation est vraie : le réel $x = - 1$ vérifie $(- 1)^{2} = 1$ et $- 1 \neq 1$ . L'assertion de départ est donc fausse. Notez bien que la négation n'est pas « $\exists x \in R, (x^{2} = 1 ⟹ x \neq 1)$ » : la négation d'une implication n'est jamais une implication.

Méthode

Que faire selon la forme de l'assertion à démontrer. Ce tableau de conduite doit devenir un réflexe.

Pour démontrer $\forall x \in E, P (x)$ : on écrit « Soit $x \in E$ », on démontre $P (x)$ sans jamais rien supposer de particulier sur $x$ , puis on conclut. Le mot « Soit » signifie précisément : je prends un élément quelconque, fixé mais arbitraire. Le raisonnement doit rester valable pour n'importe quel autre élément.
Pour démontrer $\exists x \in E, P (x)$ : il suffit d'exhiber un élément convenable, puis de vérifier qu'il convient. On n'est jamais tenu d'expliquer comment on l'a trouvé, et la vérification n'est jamais facultative.
Pour démontrer $\exists! x \in E, P (x)$ : on démontre l'existence, puis l'unicité, dans deux paragraphes distincts.
Pour réfuter $\forall x \in E, P (x)$ : il suffit d'exhiber un seul contre-exemple, c'est-à-dire un élément $x_{0}$ de $E$ tel que $P (x_{0})$ soit fausse.
Pour réfuter $\exists x \in E, P (x)$ : il faut démontrer que tous les éléments de $E$ vérifient $\neg P$ , ce qui est un travail complet, et non l'exhibition d'un exemple.

Les modes de raisonnement

Savoir ce qu'est une implication ne dit pas encore comment la démontrer. Cette section recense les stratégies dont vous disposez. Le choix de la bonne stratégie représente souvent la moitié du travail : une démonstration qui n'avance pas est très souvent une démonstration menée dans le mauvais sens.

Méthode

Choisir son mode de raisonnement. Avant de commencer, lisez la forme de l'énoncé : elle suggère presque toujours la méthode.

L'énoncé est une implication dont l'hypothèse se prête au calcul : raisonnement direct.
La conclusion est une négation, du type « n'est pas », « est différent de », « n'appartient pas à » : contraposée, ou raisonnement par l'absurde.
L'énoncé affirme une impossibilité ou une non-existence : raisonnement par l'absurde.
L'objet étudié est quelconque, mais on peut le classer selon un critère simple, par exemple pair ou impair, positif ou négatif : disjonction de cas.
L'énoncé est universel et vous le soupçonnez faux : cherchez un contre-exemple.
On demande de déterminer tous les objets vérifiant une condition, ou d'établir une existence assortie d'une unicité : analyse-synthèse.
L'énoncé porte sur tous les entiers à partir d'un certain rang : récurrence, étudiée dans la section suivante.
L'énoncé est une égalité de deux ensembles : double inclusion.

Le raisonnement direct (et les équivalences successives)

Méthode

Raisonnement direct. Pour démontrer une implication $P ⟹ Q$ , on suppose $P$ vraie, et on en déduit $Q$ par une suite de déductions dont chacune est justifiée. Rédaction type : « Supposons $P$ . Alors ... Donc $Q$ . »

Pour démontrer une égalité entre deux expressions, on part de l'une et on aboutit à l'autre, ou bien on transforme les deux séparément jusqu'à une expression commune. On n'écrit jamais l'égalité à démontrer comme point de départ d'un calcul, comme si elle était déjà acquise.

Lorsque le raisonnement direct est mené par une chaîne de $⟺$ , on parle d'équivalences successives ; chaque étape doit alors être réversible. Si l'une d'elles ne l'est pas, la chaîne devient une chaîne d'implications, et il faut impérativement conclure par une vérification des candidats obtenus.

Exemple

Résolvons dans $R$ l'équation $\sqrt{2 x + 3} = x$ . Nous allons la traiter deux fois, pour bien distinguer les deux rédactions possibles.

Première rédaction : par implications, puis vérification. Soit $x$ un réel solution de l'équation. En élevant les deux membres au carré, on obtient $2 x + 3 = x^{2}$ , c'est-à-dire $x^{2} - 2 x - 3 = 0$ . Cette équation du second degré se factorise en $(x - 3) (x + 1) = 0$ , comme on le vérifie en développant : $(x - 3) (x + 1) = x^{2} + x - 3 x - 3 = x^{2} - 2 x - 3$ . Une solution éventuelle vérifie donc $x = 3$ ou $x = - 1$ . Ce raisonnement, purement descendant, ne prouve pas que ces deux nombres sont solutions : il prouve seulement que ce sont les seuls candidats possibles. C'est la phase d'analyse.

Passons à la vérification. Pour $x = 3$ : $\sqrt{2 \times 3 + 3} = \sqrt{9} = 3$ , et le second membre vaut $3$ ; ce nombre est bien solution. Pour $x = - 1$ : $\sqrt{2 \times (- 1) + 3} = \sqrt{1} = 1$ , alors que le second membre vaut $- 1$ ; comme $1 \neq - 1$ , ce nombre n'est pas solution. L'ensemble des solutions est donc ${3}$ .

Seconde rédaction : par équivalences successives. Le nombre $\sqrt{2 x + 3}$ , lorsqu'il est défini, est positif ou nul ; une solution est donc nécessairement positive ou nulle. Pour tout réel $x$ tel que $2 x + 3 ⩾ 0$ :

\begin{aligned} \sqrt{2 x + 3} = x & ⟺ (x ⩾ 0 et 2 x + 3 = x^{2}) \\ ⟺ (x ⩾ 0 et x^{2} - 2 x - 3 = 0) \\ ⟺ (x ⩾ 0 et (x - 3) (x + 1) = 0) \\ ⟺ x = 3. \end{aligned}

La condition $x ⩾ 0$ , transportée à chaque ligne, est exactement ce qui rend l'élévation au carré réversible : deux nombres positifs ou nuls sont égaux si et seulement si leurs carrés le sont. Sans elle, la chaîne d'équivalences aurait été fausse, et aurait produit la solution parasite $x = - 1$ .

Remarque

Les deux rédactions sont également acceptables, et il faut savoir les mener toutes les deux. La première est plus sûre, car elle n'exige aucune précaution pendant le calcul : toute la vigilance est reportée sur la vérification finale, qui ne doit jamais être omise. La seconde est plus élégante, mais elle demande de contrôler la réversibilité à chaque ligne. Ce qui est en revanche inacceptable, c'est d'écrire une chaîne de symboles $⟺$ sans avoir vérifié qu'ils sont légitimes, puis de conclure sans vérification : c'est la faute qui produit les fameuses solutions parasites.

Le raisonnement par contraposée

Méthode

Raisonnement par contraposée. Pour démontrer une implication $P ⟹ Q$ , on démontre à la place sa contraposée $\neg Q ⟹ \neg P$ , ce qui revient exactement au même d'après la propriété établie plus haut. On y pense chaque fois que l'hypothèse $\neg Q$ est plus maniable que l'hypothèse $P$ , typiquement lorsque $Q$ est une assertion négative, ou lorsque l'hypothèse $P$ ne se prête à aucun calcul.

Rédaction type : « Montrons la contraposée : supposons $\neg Q$ . Alors ... donc $\neg P$ . Par contraposition, l'implication $P ⟹ Q$ est démontrée. »

Exemple

Soit $n$ un entier relatif. Montrons que si $n^{2}$ est pair, alors $n$ est pair.

Rappelons qu'un entier $m$ est dit pair s'il existe un entier $k$ tel que $m = 2 k$ , et impair s'il existe un entier $k$ tel que $m = 2 k + 1$ . Tout entier est pair ou impair, et jamais les deux à la fois : c'est la division par $2$ , que nous utiliserons librement.

L'hypothèse « $n^{2}$ est pair » fournit un entier $k$ tel que $n^{2} = 2 k$ , ce qui ne renseigne guère sur $n$ lui-même. Démontrons plutôt la contraposée, à savoir : si $n$ est impair, alors $n^{2}$ est impair.

Supposons donc $n$ impair. Il existe alors un entier $k$ tel que $n = 2 k + 1$ . On calcule

n^{2} = (2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1.

Comme $2 k^{2} + 2 k$ est un entier, l'entier $n^{2}$ s'écrit sous la forme $2 k^{'} + 1$ avec $k^{'} = 2 k^{2} + 2 k$ entier : il est donc impair.

La contraposée est établie. Par contraposition, si $n^{2}$ est pair, alors $n$ est pair. $□$

Remarque

Le résultat qui vient d'être démontré, ainsi que celui de sa réciproque, servira à plusieurs reprises dans la suite du chapitre. Retenez la forme la plus utile : un entier et son carré ont toujours la même parité.

Le raisonnement par l'absurde

Méthode

Raisonnement par l'absurde. Pour démontrer une assertion $P$ , on suppose que $\neg P$ est vraie, et l'on aboutit à une contradiction, c'est-à-dire à une assertion à la fois vraie et fausse. On en conclut que $\neg P$ est fausse, donc que $P$ est vraie.

Rédaction type : « Supposons par l'absurde que ... Alors ... , ce qui est absurde. Par conséquent, ... »

Pour démontrer une implication $P ⟹ Q$ par l'absurde, on suppose à la fois $P$ et $\neg Q$ , et on cherche une contradiction. On dispose donc de deux hypothèses au lieu d'une, ce qui est confortable ; c'est la différence avec la contraposée, où l'on part de la seule hypothèse $\neg Q$ .

Exemple

Montrons que $\sqrt{2}$ n'est pas un nombre rationnel.

Rappelons d'abord que $\sqrt{2}$ désigne l'unique réel positif dont le carré vaut $2$ , et qu'un nombre rationnel est un réel qui s'écrit comme quotient de deux entiers, le dénominateur étant non nul.

Supposons par l'absurde que $\sqrt{2}$ soit rationnel. Il existe alors deux entiers $p$ et $q$ , avec $q \neq 0$ , tels que

\sqrt{2} = \frac{p}{q} .

Nous pouvons de plus supposer que $p$ et $q$ ne sont pas tous les deux pairs. En effet, s'ils l'étaient, nous pourrions écrire $p = 2 p_{1}$ et $q = 2 q_{1}$ et remplacer la fraction $\frac{p}{q}$ par $\frac{p_{1}}{q_{1}}$ , qui a la même valeur ; en répétant l'opération tant que les deux termes sont pairs, on obtient bien une écriture où ils ne le sont plus. Ce procédé s'arrête nécessairement, car le dénominateur, qui est un entier strictement positif quitte à changer les signes de $p$ et de $q$ , diminue strictement à chaque étape.

Élevons l'égalité au carré. Comme $(\sqrt{2})^{2} = 2$ , nous obtenons $2 = \frac{p^{2}}{q^{2}}$ , c'est-à-dire, en multipliant les deux membres par $q^{2}$ qui est non nul,

p^{2} = 2 q^{2} .

L'entier $p^{2}$ est donc pair. D'après le résultat démontré par contraposée dans la sous-section précédente, l'entier $p$ est lui aussi pair : il existe un entier $p_{1}$ tel que $p = 2 p_{1}$ .

Reportons cette écriture dans l'égalité $p^{2} = 2 q^{2}$ . Il vient $(2 p_{1})^{2} = 2 q^{2}$ , soit $4 p_{1}^{2} = 2 q^{2}$ , soit encore, en divisant les deux membres par $2$ ,

q^{2} = 2 p_{1}^{2} .

L'entier $q^{2}$ est donc pair, et pour la même raison que précédemment, l'entier $q$ est pair.

Nous avons ainsi établi que $p$ et $q$ sont tous les deux pairs, ce qui contredit l'hypothèse faite au début, selon laquelle ils ne le sont pas tous les deux. Cette contradiction montre que notre supposition initiale était fausse : le nombre $\sqrt{2}$ n'est pas rationnel. $□$

Remarque

Cette démonstration est un classique absolu, et elle est exigible. Observez qu'elle n'utilise aucune théorie arithmétique : uniquement la notion de nombre pair, le fait qu'un entier et son carré ont la même parité, et la possibilité de simplifier une fraction tant que ses deux termes sont pairs. Observez aussi qu'elle démontre un résultat négatif, c'est-à-dire une non-existence, ce qui est la situation typique du raisonnement par l'absurde : il est en effet impossible de parcourir un par un tous les couples d'entiers pour vérifier qu'aucun ne convient.

Remarque

Le raisonnement par l'absurde est puissant, mais il est souvent employé à tort. Si votre contradiction finale se réduit à « ... ce qui contredit l'hypothèse $\neg Q$ que nous avons faite », c'est que vous avez en réalité démontré $P ⟹ Q$ directement, et que le détour par l'absurde n'ajoute que du bruit. Réservez cette méthode aux cas où l'hypothèse supplémentaire $\neg Q$ est réellement utilisée dans le calcul, et où la contradiction porte sur un fait acquis indépendamment.

Le raisonnement par disjonction de cas

Méthode

Disjonction de cas. Pour démontrer une assertion, on partage la situation en un nombre fini de cas qui couvrent toutes les possibilités, et on démontre l'assertion dans chacun d'eux.

Deux exigences de rédaction : annoncer la liste des cas avant de les traiter, et justifier qu'elle est exhaustive. Que deux cas se recouvrent partiellement n'est en revanche pas gênant. Chaque cas est traité dans un paragraphe séparé, et une phrase de conclusion rassemble le tout.

Exemple

Montrons que pour tout entier naturel $n$ , l'entier $n (n + 1)$ est pair.

Soit $n$ un entier naturel. Tout entier est pair ou impair : ces deux cas couvrent bien toutes les possibilités.

Cas 1 : $n$ est pair. Il existe alors un entier $k$ tel que $n = 2 k$ . On obtient

n (n + 1) = 2 k (2 k + 1) = 2 \times (k (2 k + 1)),

et $k (2 k + 1)$ est un entier, donc $n (n + 1)$ est pair.

Cas 2 : $n$ est impair. Il existe alors un entier $k$ tel que $n = 2 k + 1$ . Dans ce cas, $n + 1 = 2 k + 2 = 2 (k + 1)$ , donc

n (n + 1) = (2 k + 1) \times 2 (k + 1) = 2 \times ((2 k + 1) (k + 1)),

et $(2 k + 1) (k + 1)$ est un entier, donc $n (n + 1)$ est pair.

Dans les deux cas, l'entier $n (n + 1)$ est pair, ce qui achève la démonstration. $□$

Remarque

Ce résultat, qui affirme que le produit de deux entiers consécutifs est toujours pair, resservira souvent, notamment pour justifier que $\frac{n (n + 1)}{2}$ est bien un entier. Nous le retrouverons dans la section consacrée aux sommes.

Exemple

Voici une seconde disjonction de cas, avec des cas qui se recouvrent. Montrons que pour tous réels $x$ et $y$ , on a $∣ x + y ∣ ⩽ ∣ x ∣ + ∣ y ∣$ , où $∣ x ∣$ désigne la valeur absolue de $x$ , c'est-à-dire $x$ si $x ⩾ 0$ et $- x$ sinon.

Soient $x$ et $y$ deux réels. Par définition de la valeur absolue, on a $- ∣ x ∣ ⩽ x ⩽ ∣ x ∣$ et $- ∣ y ∣ ⩽ y ⩽ ∣ y ∣$ . En additionnant ces encadrements membre à membre, il vient

- (∣ x ∣ + ∣ y ∣) ⩽ x + y ⩽ ∣ x ∣ + ∣ y ∣ .

Distinguons maintenant deux cas, selon le signe de $x + y$ .

Cas 1 : $x + y ⩾ 0$ . Alors $∣ x + y ∣ = x + y ⩽ ∣ x ∣ + ∣ y ∣$ d'après l'inégalité de droite.

Cas 2 : $x + y ⩽ 0$ . Alors $∣ x + y ∣ = - (x + y) ⩽ ∣ x ∣ + ∣ y ∣$ d'après l'inégalité de gauche, que l'on multiplie par $- 1$ en changeant le sens.

Dans les deux cas, l'inégalité annoncée est vérifiée. Remarquez que les deux cas se recouvrent lorsque $x + y = 0$ , ce qui ne pose aucun problème : l'inégalité y est démontrée deux fois. $□$

Le contre-exemple

Méthode

Contre-exemple. Pour démontrer qu'une assertion universelle $\forall x \in E, P (x)$ est fausse, il suffit, d'après la règle de négation, d'exhiber un seul élément $x_{0}$ de $E$ tel que $P (x_{0})$ soit fausse. Un contre-exemple ne se discute pas : il se vérifie par le calcul, entièrement.

Inversement, aucune accumulation d'exemples, si nombreux soient-ils, ne démontre une assertion universelle. Vérifier une formule pour $n = 1$ , $n = 2$ et $n = 3$ ne prouve rien du tout : cela permet seulement de conjecturer.

Exemple

Réfutons l'assertion : « pour tous réels $x$ et $y$ , $\sqrt{x^{2} + y^{2}} = x + y$ ».

Prenons $x = 1$ et $y = 1$ . Le membre de gauche vaut $\sqrt{1^{2} + 1^{2}} = \sqrt{2}$ , et le membre de droite vaut $1 + 1 = 2$ . Ces deux nombres sont distincts : en effet, $(\sqrt{2})^{2} = 2$ tandis que $2^{2} = 4$ , et deux nombres positifs égaux auraient des carrés égaux. L'assertion est donc fausse.

Un second contre-exemple, encore plus expéditif, consiste à prendre $x = - 1$ et $y = 0$ : le membre de gauche vaut $\sqrt{1 + 0} = 1$ , tandis que le membre de droite vaut $- 1$ . Ici, le membre de gauche est positif ou nul par définition de la racine carrée, alors que le membre de droite peut être strictement négatif : l'égalité annoncée n'avait aucune chance d'être toujours vraie.

Notez enfin que l'égalité est vraie pour certains couples, par exemple pour $x = 3$ et $y = 0$ , puisque $\sqrt{9 + 0} = 3$ . Cela n'a aucune importance : une assertion universelle qui échoue en un seul point est fausse, quel que soit le nombre de points où elle réussit. $□$

Remarque

Un contre-exemple doit être exhibé et vérifié, jamais décrit vaguement. Écrire « c'est faux, il suffit de prendre $x$ et $y$ bien choisis » ne vaut aucun point. Écrire « c'est faux : pour $x = 1$ et $y = 1$ , le membre de gauche vaut $\sqrt{2}$ et le membre de droite vaut $2$ » constitue en revanche une démonstration complète, à laquelle il n'y a rien à ajouter.

Le raisonnement par analyse-synthèse

Méthode

Analyse-synthèse. C'est la méthode à employer lorsque l'on cherche tous les objets vérifiant une certaine condition, sans en connaître aucun au départ. Elle se déroule en deux phases, qui doivent être annoncées et clairement séparées.

Analyse. On suppose qu'un objet convient, et on en tire des conditions nécessaires, jusqu'à le déterminer complètement, ou jusqu'à obtenir une courte liste de candidats. Cette phase ne démontre rien d'autre que : « s'il existe une solution, c'est nécessairement celle-là ». Elle règle donc l'unicité.
Synthèse. On prend le candidat obtenu et l'on vérifie qu'il convient réellement. Cette phase règle l'existence. Elle n'est jamais facultative, puisque l'analyse n'a produit que des conditions nécessaires.

Rédaction type : « Analyse. Supposons que $x$ convienne. Alors ... donc nécessairement $x = \dots$ Synthèse. Réciproquement, posons $x = \dots$ et vérifions qu'il convient : ... Conclusion. Il existe une unique solution, à savoir ... »

Exemple

Montrons que toute fonction $f : R \to R$ s'écrit de manière unique comme somme d'une fonction paire et d'une fonction impaire.

Rappelons les définitions. Une fonction $g : R \to R$ est dite paire si $g (- x) = g (x)$ pour tout réel $x$ , et impaire si $g (- x) = - g (x)$ pour tout réel $x$ .

Soit $f : R \to R$ . Il s'agit de démontrer qu'il existe un unique couple $(g, h)$ de fonctions de $R$ dans $R$ , avec $g$ paire et $h$ impaire, tel que $f = g + h$ .

Analyse. Supposons qu'un tel couple $(g, h)$ existe, c'est-à-dire que $g$ soit paire, que $h$ soit impaire, et que $f = g + h$ . Soit $x$ un réel. En évaluant l'égalité $f = g + h$ au point $x$ , puis au point $- x$ , nous obtenons

\begin{aligned} f (x) & = g (x) + h (x), \\ f (- x) & = g (- x) + h (- x) = g (x) - h (x), \end{aligned}

la seconde ligne utilisant la parité de $g$ et l'imparité de $h$ . Additionnons ces deux égalités : il vient $f (x) + f (- x) = 2 g (x)$ . Soustrayons-les : il vient $f (x) - f (- x) = 2 h (x)$ . Par conséquent, nécessairement,

g (x) = \frac{f (x) + f (- x)}{2} et h (x) = \frac{f (x) - f (- x)}{2} .

Ces égalités valant pour tout réel $x$ , les fonctions $g$ et $h$ sont entièrement déterminées par $f$ . Il y a donc au plus un couple convenable.

Synthèse. Réciproquement, définissons deux fonctions $g$ et $h$ de $R$ dans $R$ en posant, pour tout réel $x$ ,

g (x) = \frac{f (x) + f (- x)}{2} et h (x) = \frac{f (x) - f (- x)}{2} .

Ces deux fonctions sont bien définies sur $R$ tout entier, car $f$ l'est. Vérifions les trois propriétés attendues. Soit $x$ un réel.

D'une part,

g (- x) = \frac{f (- x) + f (- (- x))}{2} = \frac{f (- x) + f (x)}{2} = g (x),

donc $g$ est paire. D'autre part,

h (- x) = \frac{f (- x) - f (- (- x))}{2} = \frac{f (- x) - f (x)}{2} = - \frac{f (x) - f (- x)}{2} = - h (x),

donc $h$ est impaire. Enfin,

g (x) + h (x) = \frac{f (x) + f (- x)}{2} + \frac{f (x) - f (- x)}{2} = \frac{2 f (x)}{2} = f (x),

donc $f = g + h$ . Le couple $(g, h)$ convient : il en existe au moins un.

Conclusion. Il existe un unique couple $(g, h)$ formé d'une fonction paire et d'une fonction impaire tel que $f = g + h$ , à savoir celui donné par les deux formules ci-dessus. $□$

Remarque

Cet exemple illustre parfaitement le partage des rôles : l'analyse a fourni l'unicité, la synthèse a fourni l'existence, et aucune des deux phases ne pouvait être supprimée. Une copie qui s'arrêterait à la fin de l'analyse en écrivant « donc $f = g + h$ » n'aurait rien démontré du tout : elle aurait seulement montré que, si une décomposition existe, elle est donnée par ces formules. Rien ne garantissait a priori que les fonctions ainsi construites soient effectivement paire et impaire ; c'est le calcul de la synthèse qui l'établit.

Remarque

On applique la même méthode pour chercher les solutions d'une équation fonctionnelle, pour décomposer une fraction, ou encore pour déterminer les coefficients d'une expression dont on connaît la forme. Nous en verrons une application immédiate dans la sous-section consacrée à la récurrence double, où l'analyse servira à deviner les deux coefficients d'une formule explicite, avant que la récurrence ne joue le rôle de la synthèse.

Le raisonnement par double inclusion

Il reste un mode de raisonnement fondamental, spécifique aux ensembles : pour démontrer que deux ensembles $A$ et $B$ sont égaux, on démontre séparément que $A$ est inclus dans $B$ , puis que $B$ est inclus dans $A$ . Nous l'énoncerons précisément et nous l'illustrerons dans la section consacrée aux ensembles, une fois définie l'inclusion.

Le raisonnement par récurrence

Le raisonnement par récurrence permet de démontrer une infinité d'assertions $P (0)$ , $P (1)$ , $P (2)$ , ... en un nombre fini de lignes. Il repose sur une propriété fondamentale de l'ensemble $N$ , que nous admettons sans démonstration : c'est une propriété caractéristique des entiers naturels, et non un théorème que l'on démontrerait à partir d'autre chose.

Dans toute cette section, nous utiliserons la notation $\sum$ pour désigner une somme, avec le sens vu au lycée : $\sum_{k = 1}^{n} a_{k} = a_{1} + a_{2} + \dots + a_{n}$ . Cette notation sera reprise et étudiée pour elle-même dans la section consacrée aux sommes et aux produits.

Le principe de récurrence

Propriété

Principe de récurrence (admis). Soit $n_{0}$ un entier naturel, et soit, pour tout entier $n ⩾ n_{0}$ , une assertion $P (n)$ . On suppose que les deux conditions suivantes sont réalisées.

Initialisation : l'assertion $P (n_{0})$ est vraie.
Hérédité : pour tout entier $n ⩾ n_{0}$ , si $P (n)$ est vraie, alors $P (n + 1)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ .

Remarque

Observez la forme exacte de l'hérédité : c'est une assertion universelle portant sur une implication, à savoir $\forall n ⩾ n_{0}, (P (n) ⟹ P (n + 1))$ . On ne suppose donc jamais que $P (n)$ est vraie : on suppose que si elle l'est, alors $P (n + 1)$ l'est aussi. Cette nuance, qui semble anodine, est exactement ce qui distingue une récurrence correcte d'un raisonnement circulaire.

Méthode

Rédiger une récurrence. La rédaction est très codifiée, et toute variante est perçue comme une maladresse. Voici le modèle à recopier, dans cet ordre et sans rien omettre.

Énoncer l'assertion. « Pour tout entier $n ⩾ n_{0}$ , notons $P (n)$ l'assertion : ... ». L'assertion $P (n)$ doit être une phrase mathématique complète, dépendant de $n$ , et surtout pas un nombre ni une expression. On n'écrit jamais « posons $P (n) = \frac{n (n + 1)}{2}$ ».
Initialisation. « Vérifions $P (n_{0})$ . » On calcule séparément les deux membres, et on constate qu'ils coïncident. Cette étape prend deux lignes, elle n'est jamais expédiée par « c'est évident ».
Hérédité. « Soit $n ⩾ n_{0}$ . Supposons $P (n)$ vraie. Montrons que $P (n + 1)$ est vraie. » On écrit explicitement ce que l'on suppose, ce qui s'appelle l'hypothèse de récurrence, et ce que l'on veut obtenir. Puis on mène le calcul, en signalant l'endroit précis où l'hypothèse de récurrence est utilisée.
Conclusion. « L'assertion $P (n_{0})$ est vraie et l'assertion $P$ est héréditaire à partir du rang $n_{0}$ ; par récurrence, $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ . »

Deux fautes doivent être bannies dès maintenant : supposer « $P (n)$ vraie pour tout $n$ » au début de l'hérédité, ce qui revient à supposer ce que l'on veut démontrer, et oublier l'initialisation.

Exemple

Une récurrence rédigée intégralement. Montrons que pour tout entier $n ⩾ 1$ ,

\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2} .

Pour tout entier $n ⩾ 1$ , notons $P (n)$ l'assertion : « $\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}$ ».

Initialisation. Pour $n = 1$ , le membre de gauche vaut $\sum_{k = 1}^{1} k = 1$ , et le membre de droite vaut $\frac{1 \times 2}{2} = 1$ . Les deux membres coïncident, donc $P (1)$ est vraie.

Hérédité. Soit $n ⩾ 1$ un entier. Supposons $P (n)$ vraie, c'est-à-dire

\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2} .

Montrons que $P (n + 1)$ est vraie, c'est-à-dire que $\sum_{k = 1}^{n + 1} k = \frac{(n + 1) (n + 2)}{2}$ . Isolons le dernier terme de la somme, qui vaut $n + 1$ :

\begin{aligned} \sum_{k = 1}^{n + 1} k & = (\sum_{k = 1}^{n} k) + (n + 1) \\ = \frac{n (n + 1)}{2} + (n + 1) par hypoth \overset{ˋ}{e} se de r \overset{ˊ}{e} currence \\ = (n + 1) \times (\frac{n}{2} + 1) \\ = (n + 1) \times \frac{n + 2}{2} \\ = \frac{(n + 1) (n + 2)}{2} . \end{aligned}

Nous avons bien obtenu l'expression attendue au rang $n + 1$ , donc $P (n + 1)$ est vraie.

Conclusion. L'assertion $P (1)$ est vraie et l'assertion $P$ est héréditaire à partir du rang $1$ ; par récurrence, pour tout entier $n ⩾ 1$ ,

\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2} . □

Remarque

Deux détails de rédaction méritent d'être soulignés dans l'exemple précédent. D'abord, l'hérédité commence par écrire noir sur blanc ce que l'on veut obtenir au rang $n + 1$ : sans cela, on ne sait pas vers quoi diriger le calcul, et l'on prend le risque de partir du résultat. Ensuite, la mention « par hypothèse de récurrence » est placée exactement sur la ligne où l'hypothèse est utilisée. Un correcteur doit pouvoir pointer du doigt l'endroit précis où elle sert ; si elle ne sert nulle part, c'est que la récurrence était inutile.

Exemple

Une récurrence portant sur une inégalité. Montrons que pour tout entier naturel $n$ , on a $2^{n} ⩾ n + 1$ .

Pour tout entier naturel $n$ , notons $P (n)$ l'assertion : « $2^{n} ⩾ n + 1$ ».

Initialisation. Pour $n = 0$ , on a $2^{0} = 1$ et $0 + 1 = 1$ , donc $2^{0} ⩾ 0 + 1$ : l'assertion $P (0)$ est vraie.

Hérédité. Soit $n$ un entier naturel. Supposons $P (n)$ vraie, c'est-à-dire $2^{n} ⩾ n + 1$ . Montrons que $2^{n + 1} ⩾ n + 2$ . En multipliant l'hypothèse de récurrence par $2$ , qui est strictement positif, donc sans changer le sens de l'inégalité, il vient

2^{n + 1} = 2 \times 2^{n} ⩾ 2 (n + 1) = 2 n + 2.

Or $n ⩾ 0$ , donc $2 n + 2 ⩾ n + 2$ . Par transitivité, $2^{n + 1} ⩾ n + 2$ , c'est-à-dire que $P (n + 1)$ est vraie.

Conclusion. Par récurrence, pour tout entier naturel $n$ , on a $2^{n} ⩾ n + 1$ . $□$

Remarque

Une récurrence portant sur une inégalité se conduit exactement comme une récurrence portant sur une égalité, à une différence près : on ne peut plus enchaîner des égalités jusqu'au résultat, il faut majorer ou minorer en allant dans le bon sens. La faute typique consiste à obtenir $2^{n + 1} ⩾ 2 n + 2$ et à s'arrêter là, sans faire le lien avec la quantité $n + 2$ que l'on visait. Une récurrence ne s'achève que lorsque l'assertion $P (n + 1)$ est écrite telle qu'elle a été annoncée.

Récurrence double

Certaines suites sont définies par une relation faisant intervenir les deux termes précédents. L'hypothèse $P (n)$ seule ne suffit alors pas à obtenir $P (n + 1)$ , et il faut adapter le principe.

Propriété

Principe de récurrence double (admis). Soit $n_{0}$ un entier naturel, et soit, pour tout entier $n ⩾ n_{0}$ , une assertion $P (n)$ . On suppose que :

les assertions $P (n_{0})$ et $P (n_{0} + 1)$ sont vraies ;
pour tout entier $n ⩾ n_{0}$ , si $P (n)$ et $P (n + 1)$ sont vraies, alors $P (n + 2)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ .

Méthode

Rédiger une récurrence double. Le schéma est le même que pour une récurrence simple, avec deux différences.

L'initialisation comporte deux vérifications, aux rangs $n_{0}$ et $n_{0} + 1$ , faites séparément.
L'hérédité s'énonce ainsi : « Soit $n ⩾ n_{0}$ . Supposons $P (n)$ et $P (n + 1)$ vraies. Montrons que $P (n + 2)$ est vraie. » On dispose donc de deux hypothèses de récurrence, et il faut en général les utiliser toutes les deux.

La conclusion mentionne explicitement qu'il s'agit d'une récurrence double.

Exemple

Une récurrence double rédigée intégralement. Soit $(u_{n})_{n \in N}$ la suite définie par $u_{0} = 2$ , $u_{1} = 5$ , et par la relation

u_{n + 2} = 5 u_{n + 1} - 6 u_{n} pour tout entier naturel n .

Montrons que pour tout entier naturel $n$ , on a $u_{n} = 2^{n} + 3^{n}$ .

Recherche préalable de la formule. Cette étape ne fait pas partie de la démonstration, mais elle explique d'où sort l'énoncé. Cherchons s'il existe des réels $α$ et $β$ tels que $u_{n} = α \cdot 2^{n} + β \cdot 3^{n}$ pour tout $n$ . En écrivant cette égalité aux rangs $0$ et $1$ , on obtient le système

\begin{aligned} α + β & = 2, \\ 2 α + 3 β & = 5. \end{aligned}

En multipliant la première ligne par $2$ et en la retranchant à la seconde, il vient $β = 5 - 4 = 1$ , puis $α = 2 - 1 = 1$ . Les candidats sont donc $α = 1$ et $β = 1$ , ce qui donne la formule annoncée. Cette recherche est une phase d'analyse : elle ne prouve rien, car elle n'a utilisé que deux valeurs de $n$ . La récurrence qui suit joue le rôle de la synthèse.

Calcul des premiers termes, à titre de contrôle. On a $u_{2} = 5 u_{1} - 6 u_{0} = 25 - 12 = 13$ , et $2^{2} + 3^{2} = 4 + 9 = 13$ . Puis $u_{3} = 5 u_{2} - 6 u_{1} = 65 - 30 = 35$ , et $2^{3} + 3^{3} = 8 + 27 = 35$ . La formule est cohérente sur ces deux rangs, ce qui est rassurant sans rien démontrer.

Démonstration. Pour tout entier naturel $n$ , notons $P (n)$ l'assertion : « $u_{n} = 2^{n} + 3^{n}$ ».

Initialisation. Pour $n = 0$ : $2^{0} + 3^{0} = 1 + 1 = 2 = u_{0}$ , donc $P (0)$ est vraie. Pour $n = 1$ : $2^{1} + 3^{1} = 2 + 3 = 5 = u_{1}$ , donc $P (1)$ est vraie.

Hérédité. Soit $n$ un entier naturel. Supposons $P (n)$ et $P (n + 1)$ vraies, c'est-à-dire

u_{n} = 2^{n} + 3^{n} et u_{n + 1} = 2^{n + 1} + 3^{n + 1} .

Montrons que $u_{n + 2} = 2^{n + 2} + 3^{n + 2}$ . En utilisant la relation de récurrence, puis les deux hypothèses :

\begin{aligned} u_{n + 2} & = 5 u_{n + 1} - 6 u_{n} \\ = 5 (2^{n + 1} + 3^{n + 1}) - 6 (2^{n} + 3^{n}) \\ = 5 \times 2 \times 2^{n} + 5 \times 3 \times 3^{n} - 6 \times 2^{n} - 6 \times 3^{n} \\ = (10 - 6) \times 2^{n} + (15 - 6) \times 3^{n} \\ = 4 \times 2^{n} + 9 \times 3^{n} \\ = 2^{2} \times 2^{n} + 3^{2} \times 3^{n} \\ = 2^{n + 2} + 3^{n + 2} . \end{aligned}

Donc $P (n + 2)$ est vraie.

Conclusion. Les assertions $P (0)$ et $P (1)$ sont vraies, et l'hérédité est établie ; par récurrence double, pour tout entier naturel $n$ , on a $u_{n} = 2^{n} + 3^{n}$ . $□$

Remarque

Les deux initialisations sont indispensables. L'hérédité d'une récurrence double ne dit rien tant que l'on ne dispose pas de deux rangs consécutifs pour la mettre en route : c'est un moteur à deux temps. Nous verrons dans la sous-section consacrée aux pièges ce qui se passe exactement lorsque l'on n'en vérifie qu'un seul.

Récurrence forte

Il arrive que l'obtention de $P (n + 1)$ réclame non pas le rang précédent, ni les deux rangs précédents, mais tous les rangs antérieurs à la fois. Le principe suivant s'applique alors.

Propriété

Principe de récurrence forte (admis). Soit $n_{0}$ un entier naturel, et soit, pour tout entier $n ⩾ n_{0}$ , une assertion $P (n)$ . On suppose que :

l'assertion $P (n_{0})$ est vraie ;
pour tout entier $n ⩾ n_{0}$ , si $P (k)$ est vraie pour tout entier $k$ tel que $n_{0} ⩽ k ⩽ n$ , alors $P (n + 1)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ .

Méthode

Reconnaître une situation de récurrence forte. On y pense dès que le passage au rang suivant fait intervenir des rangs antérieurs que l'on ne maîtrise pas à l'avance : une relation où $u_{n + 1}$ dépend de la somme de tous les termes précédents, une propriété où l'on doit couper un objet en deux morceaux de tailles inconnues, un raisonnement où l'on redescend d'un rang variable.

L'hypothèse de récurrence s'énonce alors ainsi : « Soit $n ⩾ n_{0}$ . Supposons que $P (k)$ soit vraie pour tout entier $k$ compris entre $n_{0}$ et $n$ . » On dit que l'on suppose la propriété vraie jusqu'au rang $n$ . Attention à la formulation : on ne suppose pas la propriété vraie pour tout entier, mais seulement jusqu'à un rang $n$ fixé.

Exemple

Une récurrence forte rédigée intégralement. Soit $(u_{n})_{n \in N}$ la suite définie par $u_{0} = 1$ et, pour tout entier $n ⩾ 1$ ,

u_{n} = \frac{2}{n} \sum_{k = 0}^{n - 1} u_{k} .

Chaque terme est ainsi défini à partir de tous les termes qui le précèdent, et non du seul terme précédent : une récurrence simple serait impuissante ici.

Calcul des premiers termes. On obtient successivement

u_{1} = \frac{2}{1} \times u_{0} = 2, u_{2} = \frac{2}{2} (u_{0} + u_{1}) = 1 + 2 = 3, u_{3} = \frac{2}{3} (u_{0} + u_{1} + u_{2}) = \frac{2}{3} \times 6 = 4.

Puis $u_{4} = \frac{2}{4} (1 + 2 + 3 + 4) = \frac{10}{2} = 5$ . Ces valeurs suggèrent la formule $u_{n} = n + 1$ , que nous allons démontrer.

Démonstration. Pour tout entier naturel $n$ , notons $P (n)$ l'assertion : « $u_{n} = n + 1$ ».

Initialisation. Pour $n = 0$ , on a $u_{0} = 1$ et $0 + 1 = 1$ , donc $P (0)$ est vraie.

Hérédité. Soit $n$ un entier naturel. Supposons que $P (k)$ soit vraie pour tout entier $k$ tel que $0 ⩽ k ⩽ n$ , c'est-à-dire que $u_{k} = k + 1$ pour tous ces entiers. Montrons que $P (n + 1)$ est vraie, c'est-à-dire que $u_{n + 1} = n + 2$ .

Comme $n + 1 ⩾ 1$ , la définition de la suite s'applique au rang $n + 1$ et donne

u_{n + 1} = \frac{2}{n + 1} \sum_{k = 0}^{n} u_{k} .

Tous les indices $k$ de cette somme vérifient $0 ⩽ k ⩽ n$ : l'hypothèse de récurrence s'applique donc à chacun d'eux, et permet de remplacer $u_{k}$ par $k + 1$ . Il vient

u_{n + 1} = \frac{2}{n + 1} \sum_{k = 0}^{n} (k + 1) .

Or la somme $\sum_{k = 0}^{n} (k + 1)$ est la somme des entiers de $1$ à $n + 1$ , c'est-à-dire $\sum_{j = 1}^{n + 1} j$ , qui vaut $\frac{(n + 1) (n + 2)}{2}$ d'après la formule démontrée dans la sous-section consacrée au principe de récurrence, appliquée à l'entier $n + 1$ qui est bien supérieur ou égal à $1$ . Par conséquent,

u_{n + 1} = \frac{2}{n + 1} \times \frac{(n + 1) (n + 2)}{2} = n + 2,

après simplification par $2$ et par $n + 1$ , qui est non nul. Ainsi $u_{n + 1} = (n + 1) + 1$ , c'est-à-dire que $P (n + 1)$ est vraie.

Conclusion. L'assertion $P (0)$ est vraie et l'hérédité forte est établie ; par récurrence forte, pour tout entier naturel $n$ , on a $u_{n} = n + 1$ . $□$

Remarque

Observez pourquoi une récurrence simple n'aurait pas suffi. Pour calculer $u_{n + 1}$ , la relation fait intervenir la somme $u_{0} + u_{1} + \dots + u_{n}$ : connaître la seule valeur de $u_{n}$ ne permet pas de la calculer. C'est le signe caractéristique d'une récurrence forte. Notez également que, dans l'hérédité, il a fallu vérifier que la définition de la suite s'appliquait bien au rang $n + 1$ , ce qui exige $n + 1 ⩾ 1$ : cette vérification est toujours nécessaire lorsque la relation de définition n'est valable qu'à partir d'un certain rang.

Remarque

Une récurrence forte peut toujours se ramener à une récurrence simple portant sur l'assertion $Q (n)$ : « $P (k)$ est vraie pour tout entier $k$ tel que $n_{0} ⩽ k ⩽ n$ ». C'est d'ailleurs ainsi que l'on démontrerait le principe de récurrence forte à partir du principe de récurrence simple. Il n'est pas utile de le faire en pratique, mais cette remarque explique pourquoi les trois principes énoncés dans cette section ne sont pas trois axiomes indépendants.

Les pièges de la récurrence

Remarque

Les erreurs commises dans les récurrences sont toujours les mêmes, et elles sont toutes évitables. Voici les cinq principales, avec pour chacune un exemple qui montre ce que l'on risque.

1. Oublier l'initialisation. Une propriété peut parfaitement être héréditaire sans être jamais vraie. Considérons l'assertion $P (n)$ : « $n = n + 1$ ». Elle est héréditaire : si $n = n + 1$ , alors en ajoutant $1$ aux deux membres on obtient $n + 1 = n + 2$ , c'est-à-dire $P (n + 1)$ . Pourtant $P (n)$ est fausse pour tout entier $n$ , car aucune initialisation ne peut être vérifiée. Une propriété héréditaire mais jamais initialisée ne démarre jamais, et l'hérédité seule ne prouve rigoureusement rien.

Voici un second exemple, moins caricatural. Notons $P (n)$ l'assertion : « l'entier $10^{n} + 1$ est divisible par $9$ », où « divisible par $9$ » signifie qu'il existe un entier $m$ tel que le nombre considéré s'écrive $9 m$ . Cette assertion est héréditaire. En effet, supposons $10^{n} + 1 = 9 m$ pour un certain entier $m$ . Alors

10^{n + 1} + 1 = 10 \times 10^{n} + 1 = 10 (10^{n} + 1) - 9 = 10 \times 9 m - 9 = 9 (10 m - 1),

et $10 m - 1$ est un entier, donc $10^{n + 1} + 1$ est divisible par $9$ . L'hérédité est parfaite, et pourtant l'assertion est fausse pour tout entier $n$ : par exemple $10^{0} + 1 = 2$ et $10^{1} + 1 = 11$ ne sont pas divisibles par $9$ . Une hérédité impeccable ne compense jamais une initialisation absente.

2. Confondre l'hypothèse de récurrence et la conclusion. On n'écrit jamais « supposons la propriété vraie pour tout $n$ », ni « supposons que $P (n)$ soit vraie pour tout entier naturel $n$ , et montrons $P (n + 1)$ ». Cette formulation suppose exactement ce que l'on cherche à démontrer : c'est un raisonnement circulaire, et la démonstration ne vaut plus rien. La formulation correcte est : « Soit $n ⩾ n_{0}$ un entier fixé. Supposons $P (n)$ vraie. Montrons $P (n + 1)$ . » L'entier $n$ est fixé le temps de l'hérédité, et l'on ne suppose la propriété qu'à ce rang-là.

3. L'hérédité qui ne démarre pas au bon rang. L'hérédité doit être valable pour tout entier $n ⩾ n_{0}$ , sans exception. Considérons l'assertion « $2^{n} ⩾ n^{2}$ ». Elle est vraie pour $n = 0$ , $n = 1$ et $n = 2$ , puisque $1 ⩾ 0$ , $2 ⩾ 1$ et $4 ⩾ 4$ . Elle est fausse pour $n = 3$ , puisque $8 < 9$ . Elle redevient vraie à partir de $n = 4$ : en effet, $16 ⩾ 16$ , et si $2^{n} ⩾ n^{2}$ avec $n ⩾ 3$ , alors $2^{n + 1} = 2 \times 2^{n} ⩾ 2 n^{2}$ , et l'inégalité $2 n^{2} ⩾ (n + 1)^{2}$ équivaut à $n^{2} - 2 n - 1 ⩾ 0$ , c'est-à-dire à $(n - 1)^{2} ⩾ 2$ , qui est vraie dès que $n ⩾ 3$ . Une récurrence initialisée au rang $0$ serait donc absurde ici : c'est au rang $4$ qu'il faut initialiser, et il faut vérifier que l'hérédité vaut bien pour tous les rangs à partir de là.

Le célèbre paradoxe des crayons relève du même défaut, dissimulé dans une phrase apparemment innocente. Notons $P (n)$ l'assertion : « dans tout ensemble de $n$ crayons, tous les crayons ont la même couleur ». L'assertion $P (1)$ est vraie. Voici la fausse hérédité : donnons-nous $n + 1$ crayons numérotés de $1$ à $n + 1$ ; les $n$ premiers ont la même couleur par hypothèse de récurrence, les $n$ derniers aussi, et comme les deux paquets ont un crayon en commun, tous les crayons auraient la même couleur. L'erreur est que pour $n = 1$ , les deux paquets sont ${c_{1}}$ et ${c_{2}}$ , qui n'ont aucun crayon commun : l'argument tombe précisément à ce rang. Une hérédité fausse pour un seul entier ruine la totalité de la récurrence.

4. La récurrence double dont on n'initialise qu'un seul rang. Soit $(v_{n})_{n \in N}$ la suite définie par $v_{0} = 1$ , $v_{1} = 3$ et $v_{n + 2} = 3 v_{n + 1} - 2 v_{n}$ . Notons $P (n)$ l'assertion : « $v_{n} = 2^{n}$ ». L'assertion $P (0)$ est vraie, puisque $v_{0} = 1 = 2^{0}$ . L'hérédité double est vraie elle aussi : si $v_{n} = 2^{n}$ et $v_{n + 1} = 2^{n + 1}$ , alors

v_{n + 2} = 3 \times 2^{n + 1} - 2 \times 2^{n} = 6 \times 2^{n} - 2 \times 2^{n} = 4 \times 2^{n} = 2^{n + 2} .

Et pourtant la conclusion est fausse : $v_{1} = 3$ alors que $2^{1} = 2$ , et $v_{2} = 3 \times 3 - 2 \times 1 = 7$ alors que $2^{2} = 4$ . Tout vient de l'initialisation manquante au rang $1$ . Dans une récurrence double, une seule initialisation ne suffit pas, car l'hérédité a besoin de deux rangs consécutifs pour se déclencher.

5. Énoncer une assertion qui n'en est pas une. L'assertion $P (n)$ doit être une phrase mathématique, susceptible d'être vraie ou fausse. Écrire « notons $P (n) = \frac{n (n + 1)}{2}$ » est une faute : ceci définit un nombre, pas une assertion, et l'on ne peut ni l'initialiser, ni la supposer vraie. De même, « notons $P (n)$ : la suite $(u_{n})$ » ne veut rien dire. La bonne rédaction énonce une égalité, une inégalité ou une propriété complète, par exemple « $P (n)$ : $u_{n} = 2^{n} + 3^{n}$ ».

Méthode

Contrôle final d'une récurrence. Avant de considérer qu'une récurrence est achevée, vérifiez les six points suivants.

L'assertion $P (n)$ est énoncée explicitement, et c'est bien une assertion, pas un nombre.
Le rang initial est le bon, et l'initialisation est effectivement vérifiée par le calcul, membre par membre.
L'hérédité commence par « Soit $n ⩾ n_{0}$ . Supposons $P (n)$ vraie », et non par une supposition portant sur tous les entiers.
Ce que l'on veut démontrer au rang $n + 1$ est écrit avant de commencer le calcul.
L'hypothèse de récurrence est utilisée, et l'endroit où elle sert est signalé.
La conclusion rappelle le type de récurrence employé, ainsi que l'ensemble des entiers pour lesquels la propriété est démontrée.

Sommes et produits

Les sections précédentes nous ont donné une langue et des modes de raisonnement. Nous allons maintenant les faire travailler sur le premier objet vraiment calculatoire de l'année : les sommes et les produits d'un nombre fini de termes. Ce n'est pas un chapitre de calcul mental, c'est un chapitre de rédaction. Une somme mal indexée, un indice muet confondu avec un paramètre, un nombre de termes mal compté, et c'est tout un exercice qui s'effondre. Les techniques mises en place ici (changement d'indice, télescopage, interversion de deux symboles) reviendront dans l'étude des suites, en algèbre linéaire, et surtout en probabilités, où presque tout calcul d'espérance est une somme à manipuler.

Le symbole somme

Définition

Soient $p$ et $q$ deux entiers relatifs tels que $p ⩽ q$ , et soient $u_{p}, u_{p + 1}, \dots, u_{q}$ des nombres réels. On note

\sum_{k = p}^{q} u_{k} = u_{p} + u_{p + 1} + \dots + u_{q} .

L'entier $k$ s'appelle l'indice de sommation, l'entier $p$ la borne inférieure et l'entier $q$ la borne supérieure.

Lorsque $p > q$ , la somme est dite vide et l'on convient que

\sum_{k = p}^{q} u_{k} = 0.

La convention de somme vide n'est pas un caprice de notation. Elle permet d'écrire des formules valables sans avoir à distinguer un cas particulier, par exemple dans une récurrence dont l'initialisation porte sur $n = 0$ . Nous la retrouverons systématiquement.

Définition

Plus généralement, si $I$ est un ensemble fini d'indices et si $(u_{i})_{i \in I}$ est une famille de réels indexée par $I$ , on note

\sum_{i \in I} u_{i}

la somme de tous les $u_{i}$ pour $i$ parcourant $I$ . Cette somme ne dépend pas de l'ordre dans lequel on additionne les termes, l'addition des réels étant commutative et associative. Si $I = \emptyset$ , la somme vaut $0$ .

Propriété

L'indice de sommation est muet. Pour tous entiers $p ⩽ q$ ,

\sum_{k = p}^{q} u_{k} = \sum_{i = p}^{q} u_{i} = \sum_{j = p}^{q} u_{j} .

La lettre choisie pour l'indice n'a aucune influence sur la valeur de la somme : elle disparaît une fois la somme calculée.

Remarque

Une conséquence pratique de ce point : l'indice de sommation ne doit jamais apparaître dans le résultat. Si vous écrivez

\sum_{k = 1}^{n} k = \frac{k (k + 1)}{2},

c'est faux, et c'est faux d'une manière qui montre que la notation n'est pas comprise : le membre de gauche ne dépend que de $n$ , le membre de droite dépend de $k$ . De même, une lettre déjà utilisée à l'extérieur de la somme ne doit pas être reprise comme indice. Écrire $\sum_{n = 1}^{n} u_{n}$ n'a aucun sens.

Propriété

Nombre de termes. Pour $p ⩽ q$ , la somme $\sum_{k = p}^{q} u_{k}$ comporte exactement

q - p + 1

termes. En particulier, pour toute constante réelle $c$ ,

\sum_{k = p}^{q} c = (q - p + 1) c .

Démonstration. Les indices parcourus sont les entiers $p, p + 1, \dots, q$ , c'est-à-dire les entiers $k$ vérifiant $p ⩽ k ⩽ q$ . En posant $j = k - p + 1$ , un tel entier $k$ correspond exactement à un entier $j$ vérifiant $1 ⩽ j ⩽ q - p + 1$ : il y en a donc $q - p + 1$ . La seconde égalité s'obtient en additionnant $q - p + 1$ fois le nombre $c$ . $□$

a. $\sum_{k = 1}^{n} 1 = n$ .

b. $\sum_{k = 0}^{n} 1 = n + 1$ .

c. $\sum_{k = 2}^{n} 1 = n - 1$ .

d. $\sum_{k = 1}^{n} 3 = 3 n$ .

e. $\sum_{k = p}^{q} 1 = q - p + 1$ .

f. $\sum_{k = 5}^{4} u_{k} = 0$ .

Propriété

Linéarité de la somme. Soient $p ⩽ q$ deux entiers, $(u_{k})$ et $(v_{k})$ deux familles de réels indexées par ${p, p + 1, \dots, q}$ , et $λ$ , $μ$ deux réels. Alors

\sum_{k = p}^{q} (λ u_{k} + μ v_{k}) = λ \sum_{k = p}^{q} u_{k} + μ \sum_{k = p}^{q} v_{k} .

Démonstration. Il s'agit uniquement de la commutativité et de l'associativité de l'addition, jointes à la distributivité de la multiplication sur l'addition. On peut le rédiger par récurrence sur le nombre de termes. Notons, pour $n ⩾ p - 1$ , l'assertion

H (n) : \sum_{k = p}^{n} (λ u_{k} + μ v_{k}) = λ \sum_{k = p}^{n} u_{k} + μ \sum_{k = p}^{n} v_{k} .

Initialisation. Pour $n = p - 1$ , les trois sommes sont vides et l'égalité s'écrit $0 = λ \times 0 + μ \times 0$ , ce qui est vrai.

Hérédité. Soit $n ⩾ p - 1$ tel que $H (n)$ soit vraie. Alors

\begin{aligned} \sum_{k = p}^{n + 1} (λ u_{k} + μ v_{k}) & = \sum_{k = p}^{n} (λ u_{k} + μ v_{k}) + (λ u_{n + 1} + μ v_{n + 1}) \\ = λ \sum_{k = p}^{n} u_{k} + μ \sum_{k = p}^{n} v_{k} + λ u_{n + 1} + μ v_{n + 1} \\ = λ (\sum_{k = p}^{n} u_{k} + u_{n + 1}) + μ (\sum_{k = p}^{n} v_{k} + v_{n + 1}) \\ = λ \sum_{k = p}^{n + 1} u_{k} + μ \sum_{k = p}^{n + 1} v_{k}, \end{aligned}

ce qui est $H (n + 1)$ .

Conclusion. Par récurrence, $H (n)$ est vraie pour tout entier $n ⩾ p - 1$ , et en particulier pour $n = q$ . $□$

Propriété

Relation de Chasles. Soient $p ⩽ q$ deux entiers et $m$ un entier tel que $p - 1 ⩽ m ⩽ q$ . Alors

\sum_{k = p}^{q} u_{k} = \sum_{k = p}^{m} u_{k} + \sum_{k = m + 1}^{q} u_{k} .

Remarque

Les cas extrêmes $m = p - 1$ et $m = q$ sont bien couverts grâce à la convention de somme vide : dans le premier, la première somme du membre de droite est vide, dans le second, c'est la seconde. En pratique, on utilise Chasles dans les deux sens : pour découper une somme (par exemple isoler les termes d'indice pair), et pour recoller deux sommes consécutives.

Exemple

Isolons le premier et le dernier terme d'une somme. Pour $n ⩾ 2$ ,

\sum_{k = 0}^{n} u_{k} = u_{0} + \sum_{k = 1}^{n - 1} u_{k} + u_{n} .

C'est exactement Chasles appliqué deux fois, avec $m = 0$ puis $m = n - 1$ . Ce découpage est le premier réflexe lorsqu'on veut comparer $\sum_{k = 0}^{n + 1} u_{k}$ et $\sum_{k = 0}^{n} u_{k}$ dans une récurrence.

Remarque

Les cinq erreurs classiques sur le symbole somme. Elles coûtent chaque année beaucoup de points, et elles sont toutes évitables.

Sortir un facteur qui dépend de l'indice. On a le droit d'écrire $\sum_{k = 1}^{n} λ u_{k} = λ \sum_{k = 1}^{n} u_{k}$ uniquement si $λ$ ne dépend pas de $k$ . En revanche $\sum_{k = 1}^{n} k u_{k}$ ne vaut pas $k \sum_{k = 1}^{n} u_{k}$ : cette dernière écriture n'a même pas de sens.
Se tromper sur le nombre de termes. La somme $\sum_{k = 0}^{n} u_{k}$ possède $n + 1$ termes, pas $n$ . La somme $\sum_{k = 3}^{n} u_{k}$ en possède $n - 2$ .
Croire que la somme d'un produit est le produit des sommes. En général $\sum_{k = 1}^{n} u_{k} v_{k} \neq (\sum_{k = 1}^{n} u_{k}) (\sum_{k = 1}^{n} v_{k})$ . La formule correcte fait intervenir une somme double, nous la verrons plus loin.
Passer à l'inverse ou à la racine terme à terme. On n'a ni $\sum \frac{1}{u_{k}} = \frac{1}{\sum u_{k}}$ , ni $\sum \sqrt{u_{k}} = \sqrt{\sum u_{k}}$ .
Oublier que l'indice est muet. Le résultat d'une somme d'indice $k$ ne contient jamais la lettre $k$ .

Changement d'indice

Un changement d'indice consiste à renommer les indices d'une somme, sans en changer les termes. La valeur de la somme est donc inchangée : ce n'est pas un calcul, c'est une réécriture. Deux changements suffisent en pratique.

Définition

Soient $p ⩽ q$ deux entiers et $c$ un entier fixé.

La translation d'indice consiste à poser $j = k + c$ , de sorte que

\sum_{k = p}^{q} u_{k} = \sum_{j = p + c}^{q + c} u_{j - c} .

Le retournement d'indice consiste à poser $j = p + q - k$ , de sorte que

\sum_{k = p}^{q} u_{k} = \sum_{j = p}^{q} u_{p + q - j} .

Dans les deux cas, l'application qui à $k$ associe $j$ est une bijection de l'ensemble des indices de départ sur l'ensemble des indices d'arrivée. C'est la seule chose à vérifier : on somme exactement les mêmes termes, dans un autre ordre.

Méthode

Effectuer un changement d'indice sans se tromper.

Annoncer le changement : « posons $j = k + 1$ » ou « posons $j = n - k$ ».
Exprimer l'ancien indice en fonction du nouveau : $k = j - 1$ , ou $k = n - j$ .
Recalculer les deux bornes en substituant les valeurs extrêmes de $k$ . Attention au retournement, qui échange le rôle des bornes : la borne inférieure de $j$ vient de la borne supérieure de $k$ .
Réécrire le terme général en remplaçant partout $k$ par son expression en $j$ .
Contrôler le nombre de termes avant et après. S'il a changé, le changement d'indice est faux.

Exemple

Translation. Calculons $A = \sum_{k = 1}^{n} (k + 1)^{2}$ pour $n ⩾ 1$ .

Posons $j = k + 1$ , c'est-à-dire $k = j - 1$ . Quand $k = 1$ , on a $j = 2$ ; quand $k = n$ , on a $j = n + 1$ . Le terme général $(k + 1)^{2}$ devient $j^{2}$ . Donc

A = \sum_{j = 2}^{n + 1} j^{2} .

Contrôle du nombre de termes : la somme de départ en avait $n - 1 + 1 = n$ , la nouvelle en a $(n + 1) - 2 + 1 = n$ . C'est cohérent.

Il reste à se ramener à une somme usuelle en réintégrant le terme d'indice $1$ , grâce à la relation de Chasles :

A = \sum_{j = 1}^{n + 1} j^{2} - 1^{2} = \frac{(n + 1) (n + 2) (2 n + 3)}{6} - 1.

Vérification pour $n = 2$ : la somme vaut $(1 + 1)^{2} + (2 + 1)^{2} = 4 + 9 = 13$ , et la formule donne $\frac{3 \times 4 \times 7}{6} - 1 = 14 - 1 = 13$ .

Exemple

Retournement. Retrouvons la somme des $n$ premiers entiers sans récurrence. Posons $S = \sum_{k = 1}^{n} k$ et effectuons le changement d'indice $j = n + 1 - k$ , c'est-à-dire $k = n + 1 - j$ . Quand $k = 1$ , on a $j = n$ ; quand $k = n$ , on a $j = 1$ . L'ensemble des indices parcourus est donc encore ${1, 2, \dots, n}$ , et

S = \sum_{j = 1}^{n} (n + 1 - j) .

Par linéarité, et puisque $n + 1$ ne dépend pas de $j$ ,

S = \sum_{j = 1}^{n} (n + 1) - \sum_{j = 1}^{n} j = n (n + 1) - S .

D'où $2 S = n (n + 1)$ , puis

S = \frac{n (n + 1)}{2} .

C'est le procédé attribué à Gauss : on additionne la somme à elle-même écrite à l'envers, ce qui apparie le premier terme avec le dernier. $□$

Sommes usuelles

Propriété

Pour tout entier $n ⩾ 1$ :

\sum_{k = 1}^{n} 1 = n, \sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}, \sum_{k = 1}^{n} k^{2} = \frac{n (n + 1) (2 n + 1)}{6}, \sum_{k = 1}^{n} k^{3} = {(\frac{n (n + 1)}{2})}^{⁣ 2} .

Ces quatre formules doivent être sues par cœur et restituées instantanément.

Propriété

Somme géométrique. Soient $q$ un réel et $n$ un entier naturel. Dans cette propriété, et dans elle seule, la lettre $q$ désigne la raison de la somme, et non une borne. Alors

\begin{aligned} \sum_{k = 0}^{n} q^{k} & = \frac{1 - q^{n + 1}}{1 - q} si q \neq 1, \\ \sum_{k = 0}^{n} q^{k} & = n + 1 si q = 1. \end{aligned}

Démonstration. Si $q = 1$ , tous les termes valent $1$ et la somme comporte $n + 1$ termes, donc elle vaut $n + 1$ .

Supposons $q \neq 1$ et posons $S = \sum_{k = 0}^{n} q^{k}$ . Multiplions $S$ par $1 - q$ et utilisons la linéarité :

(1 - q) S = \sum_{k = 0}^{n} (q^{k} - q^{k + 1}) .

Reconnaissons une somme télescopique : en posant $a_{k} = q^{k}$ , le terme général s'écrit $a_{k} - a_{k + 1}$ , donc

(1 - q) S = \sum_{k = 0}^{n} (a_{k} - a_{k + 1}) = a_{0} - a_{n + 1} = 1 - q^{n + 1} .

Comme $q \neq 1$ , le facteur $1 - q$ est non nul et l'on peut diviser :

S = \frac{1 - q^{n + 1}}{1 - q} . □

Remarque

Retenez la somme géométrique sous forme parlée, elle s'adapte alors à toutes les bornes :

somme = premier terme \times \frac{1 - {raison}^{nombre de termes}}{1 - raison} .

Ainsi, pour $q \neq 1$ et $p ⩽ n$ ,

\sum_{k = p}^{n} q^{k} = q^{p} \frac{1 - q^{n - p + 1}}{1 - q},

ce que l'on obtient en factorisant par $q^{p}$ puis en posant $j = k - p$ .

Propriété

Somme arithmétique. Pour tous entiers $p$ et $n$ tels que $1 ⩽ p ⩽ n$ ,

\sum_{k = p}^{n} k = \frac{(p + n) (n - p + 1)}{2},

autrement dit la demi-somme des termes extrêmes multipliée par le nombre de termes.

Démonstration. Par la relation de Chasles puis par la formule de la somme des $n$ premiers entiers,

\sum_{k = p}^{n} k = \sum_{k = 1}^{n} k - \sum_{k = 1}^{p - 1} k = \frac{n (n + 1)}{2} - \frac{(p - 1) p}{2} = \frac{n^{2} + n - p^{2} + p}{2} = \frac{(n - p) (n + p) + (n + p)}{2} = \frac{(p + n) (n - p + 1)}{2} . □

Démontrons maintenant intégralement la formule donnant la somme des carrés. La méthode employée, le télescopage d'une différence de puissances, est celle qui permet de retrouver toutes les formules de ce type, y compris celle des cubes.

Propriété

Pour tout entier $n ⩾ 1$ ,

\sum_{k = 1}^{n} k^{2} = \frac{n (n + 1) (2 n + 1)}{6} .

Démonstration. Partons de l'identité, valable pour tout entier $k$ ,

(k + 1)^{3} - k^{3} = k^{3} + 3 k^{2} + 3 k + 1 - k^{3} = 3 k^{2} + 3 k + 1.

Sommons cette égalité pour $k$ allant de $1$ à $n$ . Le membre de gauche est une somme télescopique : en posant $a_{k} = k^{3}$ , il s'écrit $\sum_{k = 1}^{n} (a_{k + 1} - a_{k}) = a_{n + 1} - a_{1} = (n + 1)^{3} - 1$ . Le membre de droite se traite par linéarité :

\sum_{k = 1}^{n} (3 k^{2} + 3 k + 1) = 3 \sum_{k = 1}^{n} k^{2} + 3 \sum_{k = 1}^{n} k + \sum_{k = 1}^{n} 1 = 3 \sum_{k = 1}^{n} k^{2} + \frac{3 n (n + 1)}{2} + n .

En identifiant les deux membres, et en notant $T = \sum_{k = 1}^{n} k^{2}$ :

(n + 1)^{3} - 1 = 3 T + \frac{3 n (n + 1)}{2} + n .

Or $(n + 1)^{3} - 1 = n^{3} + 3 n^{2} + 3 n$ . On en tire

\begin{aligned} 3 T & = n^{3} + 3 n^{2} + 3 n - \frac{3 n (n + 1)}{2} - n \\ = n^{3} + 3 n^{2} + 2 n - \frac{3 n^{2} + 3 n}{2} \\ = \frac{2 n^{3} + 6 n^{2} + 4 n - 3 n^{2} - 3 n}{2} \\ = \frac{2 n^{3} + 3 n^{2} + n}{2} \\ = \frac{n (2 n^{2} + 3 n + 1)}{2} \\ = \frac{n (n + 1) (2 n + 1)}{2}, \end{aligned}

la dernière ligne utilisant la factorisation $2 n^{2} + 3 n + 1 = (n + 1) (2 n + 1)$ , que l'on vérifie en développant. En divisant par $3$ :

T = \frac{n (n + 1) (2 n + 1)}{6} .

Vérification pour $n = 3$ : la somme vaut $1 + 4 + 9 = 14$ , et la formule donne $\frac{3 \times 4 \times 7}{6} = 14$ . $□$

Remarque

La même technique, appliquée à l'identité $(k + 1)^{4} - k^{4} = 4 k^{3} + 6 k^{2} + 4 k + 1$ , donne la formule des cubes en utilisant celle des carrés que l'on vient d'établir. C'est un excellent exercice de rédaction, à faire une fois pour toutes. On remarquera au passage l'égalité surprenante

\sum_{k = 1}^{n} k^{3} = {(\sum_{k = 1}^{n} k)}^{⁣ 2},

qui n'a rien de général : c'est une particularité des cubes, il ne faut surtout pas en déduire une règle.

Sommes télescopiques

Propriété

Télescopage. Soient $p ⩽ q$ deux entiers et $(a_{k})_{p ⩽ k ⩽ q + 1}$ une famille de réels. Alors

\sum_{k = p}^{q} (a_{k + 1} - a_{k}) = a_{q + 1} - a_{p} .

Démonstration. Par récurrence sur $q$ , à $p$ fixé. Pour $q ⩾ p - 1$ , notons

H (q) : \sum_{k = p}^{q} (a_{k + 1} - a_{k}) = a_{q + 1} - a_{p} .

Initialisation. Pour $q = p - 1$ , la somme est vide donc nulle, et le membre de droite vaut $a_{p} - a_{p} = 0$ . L'assertion $H (p - 1)$ est vraie.

Hérédité. Soit $q ⩾ p - 1$ tel que $H (q)$ soit vraie. En isolant le dernier terme grâce à la relation de Chasles,

\sum_{k = p}^{q + 1} (a_{k + 1} - a_{k}) = \sum_{k = p}^{q} (a_{k + 1} - a_{k}) + (a_{q + 2} - a_{q + 1}) = (a_{q + 1} - a_{p}) + a_{q + 2} - a_{q + 1} = a_{q + 2} - a_{p},

ce qui est exactement $H (q + 1)$ .

Conclusion. Par récurrence, $H (q)$ est vraie pour tout entier $q ⩾ p - 1$ . $□$

Remarque

On rencontre aussi la version « à l'envers » :

\sum_{k = p}^{q} (a_{k} - a_{k + 1}) = a_{p} - a_{q + 1},

qui s'obtient en multipliant l'égalité précédente par $- 1$ . L'important est de reconnaître la structure : il ne reste que les termes des deux extrémités, tous les autres se simplifient deux à deux.

Méthode

Reconnaître et exploiter un télescopage.

On cherche à écrire le terme général $u_{k}$ sous la forme $a_{k + 1} - a_{k}$ (ou $a_{k} - a_{k + 1}$ ) pour une famille $(a_{k})$ bien choisie.
Les signaux à repérer : une différence de deux expressions de même nature dont les indices sont décalés de $1$ ; un quotient dont le dénominateur est un produit de facteurs consécutifs (on décompose alors en éléments simples) ; un logarithme d'un quotient $\ln ⁣ (\frac{k + 1}{k}) = \ln (k + 1) - \ln (k)$ ; une différence de puissances $(k + 1)^{m} - k^{m}$ .
Une fois la forme obtenue, écrire la conclusion en une ligne : la somme vaut $a_{q + 1} - a_{p}$ . Il ne faut pas dérouler les termes avec des points de suspension, c'est une rédaction fragile et mal notée.
Toujours contrôler sur un petit cas, $n = 1$ ou $n = 2$ .

Exemple

Calculons, pour $n ⩾ 1$ ,

S_{n} = \sum_{k = 1}^{n} \frac{1}{k (k + 1)} .

Décomposition du terme général. Cherchons deux réels $α$ et $β$ tels que, pour tout entier $k ⩾ 1$ ,

\frac{1}{k (k + 1)} = \frac{α}{k} + \frac{β}{k + 1} .

En réduisant au même dénominateur, le membre de droite vaut $\frac{α (k + 1) + β k}{k (k + 1)} = \frac{(α + β) k + α}{k (k + 1)}$ . L'égalité pour tout $k$ impose $α = 1$ et $α + β = 0$ , donc $β = - 1$ . On vérifie effectivement que

\frac{1}{k} - \frac{1}{k + 1} = \frac{(k + 1) - k}{k (k + 1)} = \frac{1}{k (k + 1)} .

Télescopage. En posant $a_{k} = \frac{1}{k}$ , le terme général s'écrit $a_{k} - a_{k + 1}$ , donc

S_{n} = \sum_{k = 1}^{n} (a_{k} - a_{k + 1}) = a_{1} - a_{n + 1} = 1 - \frac{1}{n + 1} = \frac{n}{n + 1} .

Contrôle. Pour $n = 1$ , la somme vaut $\frac{1}{2}$ et la formule donne $\frac{1}{2}$ . Pour $n = 2$ , la somme vaut $\frac{1}{2} + \frac{1}{6} = \frac{2}{3}$ et la formule donne $\frac{2}{3}$ . $□$

Exemple

Une factorisation utile obtenue par télescopage. Soient $a$ et $b$ deux réels et $n ⩾ 1$ . Posons $c_{k} = a^{k} b^{n - k}$ pour $0 ⩽ k ⩽ n$ . Alors

c_{k + 1} - c_{k} = a^{k + 1} b^{n - k - 1} - a^{k} b^{n - k} = a^{k} b^{n - 1 - k} (a - b) .

En sommant pour $k$ allant de $0$ à $n - 1$ , le membre de gauche est télescopique et vaut $c_{n} - c_{0} = a^{n} - b^{n}$ . Le membre de droite se factorise par $a - b$ , qui ne dépend pas de $k$ . D'où

a^{n} - b^{n} = (a - b) \sum_{k = 0}^{n - 1} a^{k} b^{n - 1 - k} .

Pour $b = 1$ , on retrouve $a^{n} - 1 = (a - 1) \sum_{k = 0}^{n - 1} a^{k}$ , c'est-à-dire la somme géométrique. Pour $n = 2$ et $n = 3$ , on retrouve les identités du lycée $a^{2} - b^{2} = (a - b) (a + b)$ et $a^{3} - b^{3} = (a - b) (a^{2} + a b + b^{2})$ .

Le symbole produit et la factorielle

Définition

Soient $p$ et $q$ deux entiers relatifs tels que $p ⩽ q$ , et soient $u_{p}, \dots, u_{q}$ des réels. On note

\prod_{k = p}^{q} u_{k} = u_{p} \times u_{p + 1} \times \dots \times u_{q} .

Lorsque $p > q$ , le produit est dit vide et l'on convient que

\prod_{k = p}^{q} u_{k} = 1.

Remarque

La convention est ici $1$ et non $0$ , car $1$ est l'élément neutre de la multiplication comme $0$ l'est de l'addition. Elle est indispensable pour que la formule $n! = \prod_{k = 1}^{n} k$ reste valable en $n = 0$ .

Propriété

Soient $p ⩽ q$ deux entiers, $(u_{k})$ et $(v_{k})$ deux familles de réels et $λ$ un réel.

$\prod_{k = p}^{q} (u_{k} v_{k}) = (\prod_{k = p}^{q} u_{k}) (\prod_{k = p}^{q} v_{k})$ .
$\prod_{k = p}^{q} (λ u_{k}) = λ^{q - p + 1} \prod_{k = p}^{q} u_{k}$ .
Si tous les $u_{k}$ sont non nuls, $\prod_{k = p}^{q} \frac{1}{u_{k}} = \frac{1}{\prod_{k = p}^{q} u_{k}}$ .
Si tous les $u_{k}$ sont strictement positifs, $\ln (\prod_{k = p}^{q} u_{k}) = \sum_{k = p}^{q} \ln (u_{k})$ .

Remarque

Le point 2 est un piège fréquent : le facteur constant $λ$ ne « sort » pas du produit tel quel, il en sort élevé à la puissance égale au nombre de facteurs. C'est l'analogue multiplicatif de la formule $\sum_{k = p}^{q} λ = (q - p + 1) λ$ .

Le point 4 est le pont entre les deux symboles : le logarithme transforme un produit en somme. On s'en sert dès qu'un produit résiste, à condition de vérifier la stricte positivité des facteurs.

Définition

Pour tout entier naturel $n$ , on appelle factorielle de $n$ le nombre

n! = \prod_{k = 1}^{n} k = 1 \times 2 \times \dots \times n,

avec la convention $0! = 1$ (produit vide).

a. $0! = 1$ .

b. $1! = 1$ .

c. $2! = 2$ .

d. $3! = 6$ .

e. $4! = 24$ .

f. $5! = 120$ .

Propriété

Pour tout entier naturel $n$ ,

(n + 1)! = (n + 1) \times n! .

Plus généralement, pour tous entiers $0 ⩽ m ⩽ n$ ,

\frac{n!}{m!} = \prod_{k = m + 1}^{n} k .

Démonstration. La première égalité est la relation de Chasles multiplicative : $\prod_{k = 1}^{n + 1} k = (\prod_{k = 1}^{n} k) \times (n + 1)$ . Pour la seconde, on écrit de même $\prod_{k = 1}^{n} k = (\prod_{k = 1}^{m} k) \times (\prod_{k = m + 1}^{n} k)$ , soit $n! = m! \times \prod_{k = m + 1}^{n} k$ , et l'on divise par $m!$ , qui est non nul. $□$

Propriété

Produit télescopique. Soient $p ⩽ q$ deux entiers et $(a_{k})_{p ⩽ k ⩽ q + 1}$ une famille de réels tous non nuls. Alors

\prod_{k = p}^{q} \frac{a_{k + 1}}{a_{k}} = \frac{a_{q + 1}}{a_{p}} .

Démonstration. Par récurrence sur $q$ , à $p$ fixé, exactement comme pour les sommes télescopiques. Pour $q = p - 1$ , le produit est vide et vaut $1$ , tandis que le membre de droite vaut $\frac{a_{p}}{a_{p}} = 1$ . Si l'égalité est vraie au rang $q$ , alors

\prod_{k = p}^{q + 1} \frac{a_{k + 1}}{a_{k}} = (\prod_{k = p}^{q} \frac{a_{k + 1}}{a_{k}}) \times \frac{a_{q + 2}}{a_{q + 1}} = \frac{a_{q + 1}}{a_{p}} \times \frac{a_{q + 2}}{a_{q + 1}} = \frac{a_{q + 2}}{a_{p}},

ce qui est l'égalité au rang $q + 1$ . $□$

Exemple

Calculons, pour $n ⩾ 1$ ,

P_{n} = \prod_{k = 1}^{n} \frac{k + 1}{k} .

En posant $a_{k} = k$ , qui est bien non nul pour $k ⩾ 1$ , le facteur général s'écrit $\frac{a_{k + 1}}{a_{k}}$ . Le produit est donc télescopique et

P_{n} = \frac{a_{n + 1}}{a_{1}} = \frac{n + 1}{1} = n + 1.

Contrôle : pour $n = 3$ , le produit vaut $\frac{2}{1} \times \frac{3}{2} \times \frac{4}{3} = 4$ , et la formule donne $4$ . $□$

Exemple

Calculons, pour $n ⩾ 2$ ,

Q_{n} = \prod_{k = 2}^{n} (1 - \frac{1}{k^{2}}) .

Le facteur général se factorise :

1 - \frac{1}{k^{2}} = \frac{k^{2} - 1}{k^{2}} = \frac{(k - 1) (k + 1)}{k^{2}} = \frac{k - 1}{k} \times \frac{k + 1}{k} .

Par la propriété du produit d'un produit, on sépare en deux produits télescopiques :

Q_{n} = (\prod_{k = 2}^{n} \frac{k - 1}{k}) (\prod_{k = 2}^{n} \frac{k + 1}{k}) .

Pour le premier, posons $a_{k} = \frac{1}{k}$ : le facteur $\frac{k - 1}{k}$ vaut $\frac{a_{k}}{a_{k - 1}}$ , et un télescopage direct donne $\prod_{k = 2}^{n} \frac{k - 1}{k} = \frac{1}{n}$ (le numérateur du facteur d'indice $k$ se simplifie avec le dénominateur du facteur d'indice $k - 1$ , seuls survivent le numérateur $1$ du premier facteur et le dénominateur $n$ du dernier). Pour le second, la même méthode que dans l'exemple précédent donne $\prod_{k = 2}^{n} \frac{k + 1}{k} = \frac{n + 1}{2}$ (cette fois seuls survivent le numérateur $n + 1$ du dernier facteur et le dénominateur $2$ du premier). Finalement

Q_{n} = \frac{1}{n} \times \frac{n + 1}{2} = \frac{n + 1}{2 n} .

Contrôle pour $n = 3$ : $(1 - \frac{1}{4}) (1 - \frac{1}{9}) = \frac{3}{4} \times \frac{8}{9} = \frac{2}{3}$ , et la formule donne $\frac{4}{6} = \frac{2}{3}$ . $□$

Sommes doubles

Définition

Soit $I$ un ensemble fini de couples d'entiers et soit $(a_{i, j})_{(i, j) \in I}$ une famille de réels indexée par $I$ . On note

\sum_{(i, j) \in I} a_{i, j}

la somme de tous les termes $a_{i, j}$ pour $(i, j)$ parcourant $I$ . Cette somme est bien définie, indépendamment de l'ordre choisi pour additionner les termes.

Lorsque $I = {1, 2, \dots, n} \times {1, 2, \dots, m}$ , on parle de somme rectangulaire, et on la note aussi $\sum_{1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m} a_{i, j}$ .

Une famille à deux indices se visualise comme un tableau, l'indice $i$ repérant la ligne et l'indice $j$ la colonne :

\begin{array}{cccc} a_{1, 1} & a_{1, 2} & \dots & a_{1, m} \\ a_{2, 1} & a_{2, 2} & \dots & a_{2, m} \\ ⋮ & ⋮ & ⋮ \\ a_{n, 1} & a_{n, 2} & \dots & a_{n, m} \end{array}

Sommer tous les termes du tableau peut se faire de deux manières : ligne par ligne, ou colonne par colonne. C'est exactement le contenu du théorème qui suit.

Propriété

Interversion dans une somme rectangulaire. Soient $n ⩾ 1$ et $m ⩾ 1$ deux entiers et $(a_{i, j})$ une famille de réels indexée par ${1, 2, \dots, n} \times {1, 2, \dots, m}$ . Alors

\sum_{i = 1}^{n} (\sum_{j = 1}^{m} a_{i, j}) = \sum_{j = 1}^{m} (\sum_{i = 1}^{n} a_{i, j}) = \sum_{1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m} a_{i, j} .

Démonstration. Démontrons l'égalité des deux sommes itérées par récurrence sur $n$ , l'entier $m$ étant fixé. Notons

H (n) : \sum_{i = 1}^{n} (\sum_{j = 1}^{m} a_{i, j}) = \sum_{j = 1}^{m} (\sum_{i = 1}^{n} a_{i, j}) .

Initialisation. Pour $n = 1$ , le membre de gauche vaut $\sum_{j = 1}^{m} a_{1, j}$ , et le membre de droite vaut $\sum_{j = 1}^{m} a_{1, j}$ également, puisque la somme intérieure ne comporte qu'un terme. L'assertion $H (1)$ est vraie.

Hérédité. Soit $n ⩾ 1$ tel que $H (n)$ soit vraie. En isolant le terme d'indice $n + 1$ dans la somme extérieure du membre de gauche, puis en appliquant $H (n)$ :

\begin{aligned} \sum_{i = 1}^{n + 1} (\sum_{j = 1}^{m} a_{i, j}) & = \sum_{i = 1}^{n} (\sum_{j = 1}^{m} a_{i, j}) + \sum_{j = 1}^{m} a_{n + 1, j} \\ = \sum_{j = 1}^{m} (\sum_{i = 1}^{n} a_{i, j}) + \sum_{j = 1}^{m} a_{n + 1, j} \\ = \sum_{j = 1}^{m} (\sum_{i = 1}^{n} a_{i, j} + a_{n + 1, j}) \\ = \sum_{j = 1}^{m} (\sum_{i = 1}^{n + 1} a_{i, j}) . \end{aligned}

La troisième égalité utilise la linéarité de la somme d'indice $j$ , la quatrième la relation de Chasles appliquée à la somme d'indice $i$ . C'est $H (n + 1)$ .

Conclusion. Par récurrence, $H (n)$ est vraie pour tout $n ⩾ 1$ . Enfin, chacune des deux sommes itérées additionne une fois et une seule chaque terme $a_{i, j}$ du tableau : elles valent donc la somme de tous les termes, c'est-à-dire $\sum_{1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m} a_{i, j}$ . $□$

Remarque

Insistons sur un point qui sera décisif plus tard dans l'année : cette liberté d'interversion vaut parce que les sommes sont finies. Rien de tel ne va de soi pour des sommes infinies, où l'interversion demande des hypothèses précises.

Notez également que, dans la somme $\sum_{j = 1}^{m} a_{i, j}$ , l'indice $i$ joue le rôle d'une constante : il est fixé par la somme extérieure. C'est la clé de tous les calculs qui suivent.

Propriété

Produit de deux sommes. Soient $(a_{i})_{1 ⩽ i ⩽ n}$ et $(b_{j})_{1 ⩽ j ⩽ m}$ deux familles de réels. Alors

(\sum_{i = 1}^{n} a_{i}) (\sum_{j = 1}^{m} b_{j}) = \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i} b_{j} .

Démonstration. Posons $B = \sum_{j = 1}^{m} b_{j}$ . C'est un réel fixé, qui ne dépend pas de l'indice $i$ . La linéarité de la somme d'indice $i$ permet donc de faire entrer $B$ dans cette somme :

(\sum_{i = 1}^{n} a_{i}) B = \sum_{i = 1}^{n} (a_{i} B) .

Fixons maintenant $i$ . Le réel $a_{i}$ ne dépend pas de $j$ , donc une nouvelle application de la linéarité, cette fois pour la somme d'indice $j$ , donne

a_{i} B = a_{i} \sum_{j = 1}^{m} b_{j} = \sum_{j = 1}^{m} a_{i} b_{j} .

En reportant dans l'égalité précédente, on obtient le résultat annoncé. $□$

Remarque

Cette formule est la version correcte de l'erreur classique signalée plus haut. Le produit de deux sommes n'est pas la somme des produits terme à terme : c'est la somme de tous les produits croisés. Sur deux termes chacune,

(a_{1} + a_{2}) (b_{1} + b_{2}) = a_{1} b_{1} + a_{1} b_{2} + a_{2} b_{1} + a_{2} b_{2},

soit quatre termes et non deux.

Exemple

Calculons $U_{n} = \sum_{i = 1}^{n} \sum_{j = 1}^{n} (i + j)$ .

Fixons $i$ et sommons d'abord sur $j$ . Comme $i$ est une constante vis-à-vis de $j$ , la linéarité donne

\sum_{j = 1}^{n} (i + j) = \sum_{j = 1}^{n} i + \sum_{j = 1}^{n} j = n i + \frac{n (n + 1)}{2} .

Il reste à sommer ce résultat sur $i$ :

U_{n} = \sum_{i = 1}^{n} (n i + \frac{n (n + 1)}{2}) = n \sum_{i = 1}^{n} i + n \times \frac{n (n + 1)}{2} = \frac{n^{2} (n + 1)}{2} + \frac{n^{2} (n + 1)}{2} = n^{2} (n + 1) .

Contrôle pour $n = 2$ : les quatre termes sont $1 + 1 = 2$ , $1 + 2 = 3$ , $2 + 1 = 3$ et $2 + 2 = 4$ , de somme $12$ , et la formule donne $4 \times 3 = 12$ . Contrôle pour $n = 3$ : la formule donne $9 \times 4 = 36$ , et l'énumération des neuf termes donne $2 + 3 + 4 + 3 + 4 + 5 + 4 + 5 + 6 = 36$ . $□$

Passons aux sommes dont l'ensemble d'indices n'est plus un rectangle mais un triangle. Ce sont elles qui posent le plus de difficultés en début d'année, et c'est un passage obligé.

Définition

Soit $(a_{i, j})$ une famille de réels indexée par ${1, 2, \dots, n}^{2}$ . On note

\sum_{1 ⩽ i ⩽ j ⩽ n} a_{i, j}

la somme des termes $a_{i, j}$ pour lesquels le couple $(i, j)$ vérifie $1 ⩽ i ⩽ j ⩽ n$ , c'est-à-dire la somme des cases du tableau situées sur la diagonale ou au-dessus. On définit de même

\sum_{1 ⩽ i < j ⩽ n} a_{i, j},

où la diagonale est cette fois exclue.

Propriété

Interversion dans une somme triangulaire. Avec les notations précédentes,

\sum_{1 ⩽ i ⩽ j ⩽ n} a_{i, j} = \sum_{j = 1}^{n} (\sum_{i = 1}^{j} a_{i, j}) = \sum_{i = 1}^{n} (\sum_{j = i}^{n} a_{i, j}),

\sum_{1 ⩽ i < j ⩽ n} a_{i, j} = \sum_{j = 2}^{n} (\sum_{i = 1}^{j - 1} a_{i, j}) = \sum_{i = 1}^{n - 1} (\sum_{j = i + 1}^{n} a_{i, j}) .

Démonstration. Traitons le cas large, le cas strict étant identique. Notons

T = {(i, j) \in {1, 2, \dots, n}^{2}; i ⩽ j}

l'ensemble d'indices concerné, et $S = \sum_{(i, j) \in T} a_{i, j}$ .

Première écriture. Regroupons les couples de $T$ selon la valeur de leur seconde composante. Pour $j$ fixé dans ${1, 2, \dots, n}$ , les couples de $T$ dont la seconde composante vaut $j$ sont exactement les couples $(i, j)$ avec $1 ⩽ i ⩽ j$ . Ces $n$ paquets sont deux à deux disjoints et leur réunion est $T$ tout entier : chaque couple de $T$ appartient à un paquet et à un seul, celui de sa seconde composante. En additionnant les termes paquet par paquet,

S = \sum_{j = 1}^{n} (\sum_{i = 1}^{j} a_{i, j}) .

Seconde écriture. Regroupons cette fois selon la première composante. Pour $i$ fixé dans ${1, 2, \dots, n}$ , les couples de $T$ dont la première composante vaut $i$ sont exactement les couples $(i, j)$ avec $i ⩽ j ⩽ n$ . Pour la même raison que ci-dessus,

S = \sum_{i = 1}^{n} (\sum_{j = i}^{n} a_{i, j}) .

Contrôle. Comptons les termes des deux côtés en prenant $a_{i, j} = 1$ pour tout couple. La première écriture donne $\sum_{j = 1}^{n} j = \frac{n (n + 1)}{2}$ . La seconde donne $\sum_{i = 1}^{n} (n - i + 1) = \sum_{i = 1}^{n} (n + 1) - \sum_{i = 1}^{n} i = n (n + 1) - \frac{n (n + 1)}{2} = \frac{n (n + 1)}{2}$ . Les deux comptages coïncident. $□$

Méthode

Intervertir deux symboles somme sans se tromper.

Écrire l'ensemble d'indices sous forme d'une condition unique. Une somme itérée $\sum_{i = 1}^{n} \sum_{j = i}^{n}$ porte sur les couples vérifiant $1 ⩽ i ⩽ n$ et $i ⩽ j ⩽ n$ , ce qui se résume en $1 ⩽ i ⩽ j ⩽ n$ .
Choisir le nouvel indice extérieur, celui que l'on va fixer en premier.
Décrire, à cet indice fixé, l'ensemble exact des valeurs de l'autre indice. C'est l'unique étape où l'on peut se tromper : on relit la condition globale en considérant l'indice extérieur comme une constante. Avec $1 ⩽ i ⩽ j ⩽ n$ et $j$ extérieur, la condition sur $i$ est $1 ⩽ i ⩽ j$ .
Vérifier que les bornes de l'indice extérieur sont les bonnes. Elles doivent couvrir toutes les valeurs pour lesquelles la somme intérieure est non vide. Pour $\sum_{1 ⩽ i < j ⩽ n}$ avec $j$ extérieur, on part de $j = 2$ , car pour $j = 1$ il n'existe aucun $i$ tel que $1 ⩽ i < 1$ .
Contrôler le nombre de termes en remplaçant tous les $a_{i, j}$ par $1$ : les deux écritures doivent donner le même total, à savoir $\frac{n (n + 1)}{2}$ pour le triangle large et $\frac{n (n - 1)}{2}$ pour le triangle strict.

Exemple

Calculons, pour $n ⩾ 1$ ,

V_{n} = \sum_{1 ⩽ i ⩽ j ⩽ n} i .

Le terme général ne dépend que de $i$ , ce qui ne change rien à la méthode.

Première méthode : sommer d'abord sur $i$ , à $j$ fixé. La condition $1 ⩽ i ⩽ j ⩽ n$ s'écrit, à $j$ fixé dans ${1, 2, \dots, n}$ , sous la forme $1 ⩽ i ⩽ j$ . Donc

V_{n} = \sum_{j = 1}^{n} (\sum_{i = 1}^{j} i) = \sum_{j = 1}^{n} \frac{j (j + 1)}{2} = \frac{1}{2} \sum_{j = 1}^{n} (j^{2} + j) .

Par linéarité et grâce aux sommes usuelles,

\begin{aligned} V_{n} & = \frac{1}{2} (\frac{n (n + 1) (2 n + 1)}{6} + \frac{n (n + 1)}{2}) \\ = \frac{n (n + 1)}{2} \times \frac{1}{2} (\frac{2 n + 1}{3} + 1) \\ = \frac{n (n + 1)}{4} \times \frac{2 n + 4}{3} \\ = \frac{n (n + 1) (n + 2)}{6} . \end{aligned}

Seconde méthode : sommer d'abord sur $j$ , à $i$ fixé. Cette fois la condition s'écrit $i ⩽ j ⩽ n$ , et le terme général $i$ est constant vis-à-vis de $j$ . La somme intérieure comporte $n - i + 1$ termes, donc

V_{n} = \sum_{i = 1}^{n} (\sum_{j = i}^{n} i) = \sum_{i = 1}^{n} i (n - i + 1) = (n + 1) \sum_{i = 1}^{n} i - \sum_{i = 1}^{n} i^{2} .

D'où

V_{n} = (n + 1) \times \frac{n (n + 1)}{2} - \frac{n (n + 1) (2 n + 1)}{6} = \frac{n (n + 1)}{6} (3 (n + 1) - (2 n + 1)) = \frac{n (n + 1) (n + 2)}{6} .

Les deux méthodes donnent bien le même résultat, ce qui constitue déjà une vérification sérieuse.

Contrôle numérique. Pour $n = 3$ , les couples $(i, j)$ tels que $1 ⩽ i ⩽ j ⩽ 3$ sont $(1, 1)$ , $(1, 2)$ , $(1, 3)$ , $(2, 2)$ , $(2, 3)$ et $(3, 3)$ . Les valeurs de $i$ correspondantes sont $1, 1, 1, 2, 2, 3$ , de somme $10$ . La formule donne $\frac{3 \times 4 \times 5}{6} = 10$ . Pour $n = 2$ , l'énumération donne $1 + 1 + 2 = 4$ , et la formule $\frac{2 \times 3 \times 4}{6} = 4$ . $□$

Propriété

Découpage d'un carré d'indices. Soit $(a_{i, j})$ une famille indexée par ${1, 2, \dots, n}^{2}$ . Alors

\sum_{1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n} a_{i, j} = \sum_{1 ⩽ i < j ⩽ n} a_{i, j} + \sum_{i = 1}^{n} a_{i, i} + \sum_{1 ⩽ j < i ⩽ n} a_{i, j} .

Démonstration. Soit $(i, j)$ un couple d'éléments de ${1, 2, \dots, n}$ . L'ordre sur les entiers étant total, exactement l'un des trois cas $i < j$ , $i = j$ ou $i > j$ se produit. Les trois sommes du membre de droite portent donc sur trois parties deux à deux disjointes du carré d'indices, dont la réunion est le carré tout entier. Chaque terme $a_{i, j}$ est ainsi compté une fois et une seule dans chacun des deux membres. $□$

Propriété

Carré d'une somme. Soit $(a_{i})_{1 ⩽ i ⩽ n}$ une famille de réels. Alors

{(\sum_{i = 1}^{n} a_{i})}^{⁣ 2} = \sum_{i = 1}^{n} a_{i}^{2} + 2 \sum_{1 ⩽ i < j ⩽ n} a_{i} a_{j},

et par conséquent

\sum_{1 ⩽ i ⩽ j ⩽ n} a_{i} a_{j} = \frac{1}{2} [{(\sum_{i = 1}^{n} a_{i})}^{⁣ 2} + \sum_{i = 1}^{n} a_{i}^{2}] .

Démonstration. Appliquons la formule du produit de deux sommes, avec la même famille pour les deux facteurs :

{(\sum_{i = 1}^{n} a_{i})}^{⁣ 2} = \sum_{1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n} a_{i} a_{j} .

Découpons ce carré d'indices selon les trois cas $i < j$ , $i = j$ et $i > j$ :

\sum_{1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n} a_{i} a_{j} = \sum_{1 ⩽ i < j ⩽ n} a_{i} a_{j} + \sum_{i = 1}^{n} a_{i} a_{i} + \sum_{1 ⩽ j < i ⩽ n} a_{i} a_{j} .

La somme du milieu vaut $\sum_{i = 1}^{n} a_{i}^{2}$ . Quant à la dernière, échangeons les noms des deux indices, qui sont muets : elle s'écrit $\sum_{1 ⩽ i < j ⩽ n} a_{j} a_{i}$ , et comme le produit de deux réels ne dépend pas de l'ordre des facteurs, elle est égale à $\sum_{1 ⩽ i < j ⩽ n} a_{i} a_{j}$ . Les deux sommes triangulaires strictes sont donc égales, d'où le facteur $2$ .

Pour la seconde formule, on part du découpage du triangle large en triangle strict et diagonale :

\sum_{1 ⩽ i ⩽ j ⩽ n} a_{i} a_{j} = \sum_{1 ⩽ i < j ⩽ n} a_{i} a_{j} + \sum_{i = 1}^{n} a_{i}^{2} .

Or la première égalité donne $\sum_{1 ⩽ i < j ⩽ n} a_{i} a_{j} = \frac{1}{2} [{(\sum_{i = 1}^{n} a_{i})}^{⁣ 2} - \sum_{i = 1}^{n} a_{i}^{2}]$ . En reportant, on obtient

\sum_{1 ⩽ i ⩽ j ⩽ n} a_{i} a_{j} = \frac{1}{2} {(\sum_{i = 1}^{n} a_{i})}^{⁣ 2} - \frac{1}{2} \sum_{i = 1}^{n} a_{i}^{2} + \sum_{i = 1}^{n} a_{i}^{2} = \frac{1}{2} [{(\sum_{i = 1}^{n} a_{i})}^{⁣ 2} + \sum_{i = 1}^{n} a_{i}^{2}] . □

Exemple

Contrôlons ces deux formules sur un cas explicite, avec $n = 2$ , $a_{1} = 1$ et $a_{2} = 2$ .

Le carré de la somme vaut $(1 + 2)^{2} = 9$ . Le membre de droite de la première formule vaut $(1^{2} + 2^{2}) + 2 \times (1 \times 2) = 5 + 4 = 9$ .

Pour la seconde formule, la somme triangulaire large porte sur les couples $(1, 1)$ , $(1, 2)$ et $(2, 2)$ , donc vaut $1 \times 1 + 1 \times 2 + 2 \times 2 = 7$ . La formule donne $\frac{1}{2} (9 + 5) = 7$ .

Ensembles

Nous quittons le calcul pour le vocabulaire. Tout l'édifice mathématique que vous allez construire cette année repose sur la notion d'ensemble : un espace vectoriel est un ensemble muni d'opérations, une probabilité est une application définie sur un ensemble de parties, une suite est une application définie sur $N$ . Nous ne définirons pas ce qu'est un ensemble, la théorie axiomatique dépassant très largement le programme. Nous adopterons le point de vue intuitif : un ensemble est une collection d'objets, appelés ses éléments, et l'on sait dire d'un objet donné s'il appartient ou non à cette collection.

Appartenance, inclusion, égalité

Définition

Soit $E$ un ensemble.

Si $x$ est un élément de $E$ , on écrit $x \in E$ et on lit « $x$ appartient à $E$ ». Dans le cas contraire, on écrit $x \notin E$ .
Une partie (ou sous-ensemble) $A$ de $E$ est un ensemble dont tous les éléments appartiennent à $E$ . On écrit alors $A \subset E$ et on lit « $A$ est inclus dans $E$ », ce qui signifie

\forall x, (x \in A ⟹ x \in E) .

L'ensemble vide, noté $\emptyset$ , est l'ensemble qui ne possède aucun élément.

Remarque

Ne confondez jamais $\in$ et $\subset$ . Le symbole $\in$ relie un élément à un ensemble ; le symbole $\subset$ relie deux ensembles. Ainsi, pour $E = {1, 2, 3}$ :

$1 \in E$ est vrai, $1 \subset E$ n'a pas de sens.
${1} \subset E$ est vrai, ${1} \in E$ est faux (les éléments de $E$ sont les nombres $1$ , $2$ , $3$ , pas des ensembles).

Cette confusion est la première cause de rédactions incompréhensibles en début d'année. Prenez l'habitude de vous demander, à chaque symbole que vous écrivez, si l'objet situé à gauche est un élément ou un ensemble.

Définition

Un ensemble peut être décrit de deux manières.

En extension : on énumère ses éléments entre accolades, comme dans $A = {- 1, 0, 1}$ . L'ordre et les répétitions n'ont aucune importance : ${1, 2} = {2, 1} = {1, 1, 2}$ .
En compréhension : on décrit ses éléments par une propriété caractéristique, comme dans

A = {x \in R; x^{2} ⩽ 1},

qui se lit « l'ensemble des réels $x$ tels que $x^{2} ⩽ 1$ ».

Exemple

Les deux écritures décrivent parfois le même ensemble. Ainsi

{x \in R; x^{2} = 1} = {- 1, 1}, {x \in R; x^{2} + 1 = 0} = \emptyset, {n \in N; n est pair} = {0, 2, 4, \dots} .

Le deuxième exemple mérite attention : un carré de réel est positif ou nul, donc $x^{2} + 1 ⩾ 1 > 0$ pour tout réel $x$ . Aucun réel ne vérifie l'équation, l'ensemble est bien vide.

Propriété

Soient $A$ , $B$ , $C$ trois parties d'un ensemble $E$ .

$\emptyset \subset A$ et $A \subset A$ .
Si $A \subset B$ et $B \subset C$ , alors $A \subset C$ (transitivité).
$A = B$ si et seulement si $A \subset B$ et $B \subset A$ .

Démonstration. 1. L'inclusion $\emptyset \subset A$ s'écrit « pour tout $x$ , si $x \in \emptyset$ alors $x \in A$ ». L'hypothèse $x \in \emptyset$ n'est jamais réalisée, donc l'implication est vraie pour tout $x$ : c'est une implication vide, comme nous l'avons vu au début du chapitre. L'inclusion $A \subset A$ est immédiate.

2. Soit $x \in A$ . Comme $A \subset B$ , on a $x \in B$ . Comme $B \subset C$ , on a $x \in C$ . Donc tout élément de $A$ appartient à $C$ .

3. Deux ensembles sont égaux lorsqu'ils ont exactement les mêmes éléments, c'est-à-dire lorsque, pour tout $x$ , on a l'équivalence $x \in A ⟺ x \in B$ . Or une équivalence est la conjonction de deux implications : cette condition équivaut à « pour tout $x$ , $x \in A ⟹ x \in B$ » et « pour tout $x$ , $x \in B ⟹ x \in A$ », c'est-à-dire à $A \subset B$ et $B \subset A$ . $□$

Méthode

Démontrer une égalité d'ensembles par double inclusion. C'est le geste le plus important de ce chapitre, et vous l'emploierez tous les jours pendant deux ans. Pour établir $A = B$ :

Écrire explicitement : « Montrons que $A \subset B$ . »
Commencer par « Soit $x \in A$ . » Ne jamais écrire « soit $x$ », il faut dire d'où vient $x$ .
Traduire l'appartenance $x \in A$ en la propriété qui définit $A$ , raisonner, et conclure par « donc $x \in B$ ».
Écrire ensuite : « Montrons que $B \subset A$ . » et recommencer dans l'autre sens.
Conclure : « Par double inclusion, $A = B$ . »

Variante par équivalences. Si chaque étape du raisonnement est une équivalence, on peut écrire une seule chaîne

x \in A ⟺ \dots ⟺ x \in B,

et conclure directement. C'est plus rapide, mais plus dangereux : chaque flèche doit vraiment être une équivalence. En cas de doute, revenez à la double inclusion.

Remarque

Une mise en garde de rédaction : pour montrer une inclusion $A \subset B$ , on part toujours d'un élément quelconque de $A$ . Écrire « on a $A \subset B$ car les éléments de $A$ sont dans $B$ » n'est pas une démonstration, c'est une paraphrase de la définition.

Opérations sur les parties

Dans toute cette section, $E$ désigne un ensemble et $A$ , $B$ , $C$ des parties de $E$ .

Définition

On définit les parties suivantes de $E$ .

La réunion : $A \cup B = {x \in E; x \in A ou x \in B}$ .
L'intersection : $A \cap B = {x \in E; x \in A et x \in B}$ .
La différence : $A ∖ B = {x \in E; x \in A et x \notin B}$ , qui se lit « $A$ privé de $B$ ».
Le complémentaire de $A$ dans $E$ : $\overline{A} = E ∖ A = {x \in E; x \notin A}$ .
La différence symétrique : $A Δ B = (A ∖ B) \cup (B ∖ A)$ .

On dit que $A$ et $B$ sont disjoints lorsque $A \cap B = \emptyset$ .

Remarque

Le « ou » de la réunion est le ou inclusif de la logique : un élément de $A \cap B$ appartient bien à $A \cup B$ . La différence symétrique, elle, correspond au ou exclusif : $A Δ B$ est l'ensemble des éléments qui appartiennent à l'un des deux ensembles mais pas aux deux. On a d'ailleurs

A Δ B = (A \cup B) ∖ (A \cap B),

égalité que l'on démontre par double inclusion ou, plus rapidement, par les indicatrices (voir plus loin).

Attention enfin : la notation $\overline{A}$ n'a de sens que si l'ensemble $E$ dans lequel on prend le complémentaire est fixé sans ambiguïté. Le complémentaire de $N$ dans $Z$ et son complémentaire dans $R$ ne sont évidemment pas les mêmes.

Propriété

Soient $A$ , $B$ , $C$ des parties de $E$ .

Commutativité : $A \cup B = B \cup A$ et $A \cap B = B \cap A$ .
Associativité : $(A \cup B) \cup C = A \cup (B \cup C)$ et $(A \cap B) \cap C = A \cap (B \cap C)$ .
Idempotence et éléments neutres : $A \cup A = A$ , $A \cap A = A$ , $A \cup \emptyset = A$ , $A \cap \emptyset = \emptyset$ , $A \cup E = E$ , $A \cap E = A$ .
Distributivité : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ et $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .
Lois de De Morgan : $\overline{A \cup B} = \overline{A} \cap \overline{B}$ et $\overline{A \cap B} = \overline{A} \cup \overline{B}$ .
Involutivité : $\overline{\overline{A}} = A$ .
Différence : $A ∖ B = A \cap \overline{B}$ .
Croissance : si $A \subset B$ , alors $A \cup C \subset B \cup C$ et $A \cap C \subset B \cap C$ , et $\overline{B} \subset \overline{A}$ .

Ces propriétés ne sont pas à apprendre comme une liste : elles sont le décalque exact des règles de la logique établies au début du chapitre. La réunion correspond au « ou », l'intersection au « et », le complémentaire à la négation. Les lois de De Morgan ensemblistes sont ainsi la traduction des lois de De Morgan logiques. Voici la rédaction modèle attendue, sur deux d'entre elles.

Démonstration de la première loi de De Morgan. Montrons que $\overline{A \cup B} = \overline{A} \cap \overline{B}$ par double inclusion.

Première inclusion : $\overline{A \cup B} \subset \overline{A} \cap \overline{B}$ . Soit $x \in \overline{A \cup B}$ . Par définition du complémentaire, $x \in E$ et $x \notin A \cup B$ . Supposons par l'absurde que $x \in A$ ; alors $x$ appartiendrait à $A \cup B$ , ce qui contredit $x \notin A \cup B$ . Donc $x \notin A$ , c'est-à-dire $x \in \overline{A}$ . Le même raisonnement avec $B$ donne $x \in \overline{B}$ . Ainsi $x \in \overline{A} \cap \overline{B}$ .

Seconde inclusion : $\overline{A} \cap \overline{B} \subset \overline{A \cup B}$ . Soit $x \in \overline{A} \cap \overline{B}$ . Alors $x \in E$ , $x \notin A$ et $x \notin B$ . Supposons par l'absurde que $x \in A \cup B$ . Par définition de la réunion, on aurait $x \in A$ ou $x \in B$ , ce qui est exclu dans les deux cas. Donc $x \notin A \cup B$ , c'est-à-dire $x \in \overline{A \cup B}$ .

Par double inclusion, $\overline{A \cup B} = \overline{A} \cap \overline{B}$ . $□$

Démonstration de la seconde loi de De Morgan. On peut refaire le même travail, mais il est plus élégant de déduire la seconde de la première. Appliquons la loi déjà démontrée aux parties $\overline{A}$ et $\overline{B}$ :

\overline{\overline{A} \cup \overline{B}} = \overline{\overline{A}} \cap \overline{\overline{B}} = A \cap B,

en utilisant $\overline{\overline{A}} = A$ . En passant au complémentaire les deux membres de cette égalité, et en utilisant de nouveau l'involutivité, on obtient

\overline{A} \cup \overline{B} = \overline{A \cap B} . □

Démonstration de la première distributivité. Montrons que $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ par double inclusion.

Première inclusion. Soit $x \in A \cap (B \cup C)$ . Alors $x \in A$ , et $x \in B \cup C$ , c'est-à-dire $x \in B$ ou $x \in C$ . Distinguons deux cas.

Si $x \in B$ : comme on a aussi $x \in A$ , on obtient $x \in A \cap B$ , donc $x \in (A \cap B) \cup (A \cap C)$ .
Si $x \in C$ : comme on a aussi $x \in A$ , on obtient $x \in A \cap C$ , donc $x \in (A \cap B) \cup (A \cap C)$ .

Dans les deux cas, $x \in (A \cap B) \cup (A \cap C)$ , ce qui établit la première inclusion.

Seconde inclusion. Soit $x \in (A \cap B) \cup (A \cap C)$ . Alors $x \in A \cap B$ ou $x \in A \cap C$ . Distinguons de nouveau.

Si $x \in A \cap B$ : alors $x \in A$ , et $x \in B$ donc $x \in B \cup C$ . D'où $x \in A \cap (B \cup C)$ .
Si $x \in A \cap C$ : alors $x \in A$ , et $x \in C$ donc $x \in B \cup C$ . D'où $x \in A \cap (B \cup C)$ .

Dans les deux cas, $x \in A \cap (B \cup C)$ .

Par double inclusion, les deux ensembles sont égaux. $□$

Remarque

Observez la structure de ces deux démonstrations : c'est toujours la même. On part d'un élément quelconque du premier ensemble, on traduit son appartenance en une phrase logique, on manipule cette phrase avec les règles de la logique, puis on retraduit en appartenance. La disjonction de cas apparaît naturellement dès qu'un « ou » figure dans l'hypothèse. C'est cette mécanique qu'il faut automatiser, bien plus que les énoncés eux-mêmes.

Propriété

Caractérisations de l'inclusion. Soient $A$ et $B$ deux parties de $E$ . Les assertions suivantes sont équivalentes.

$A \subset B$ .
$A \cap B = A$ .
$A \cup B = B$ .
$\overline{B} \subset \overline{A}$ .
$A ∖ B = \emptyset$ .

Démonstration. Montrons $1 ⟹ 2 ⟹ 3 ⟹ 1$ , puis l'équivalence de $1$ avec $4$ et avec $5$ .

$1 ⟹ 2$ . L'inclusion $A \cap B \subset A$ est toujours vraie. Réciproquement, si $x \in A$ , alors $x \in B$ par hypothèse, donc $x \in A \cap B$ . D'où l'égalité.

$2 ⟹ 3$ . Supposons $A \cap B = A$ . L'inclusion $B \subset A \cup B$ est toujours vraie. Réciproquement, soit $x \in A \cup B$ . Si $x \in B$ , c'est terminé. Si $x \in A$ , alors $x \in A \cap B$ par hypothèse, donc en particulier $x \in B$ . D'où $A \cup B \subset B$ , puis l'égalité.

$3 ⟹ 1$ . Supposons $A \cup B = B$ et soit $x \in A$ . Alors $x \in A \cup B = B$ , donc $x \in B$ .

$1 ⟺ 4$ . Supposons $A \subset B$ et soit $x \in \overline{B}$ , c'est-à-dire $x \in E$ et $x \notin B$ . Si l'on avait $x \in A$ , on aurait $x \in B$ , ce qui est exclu. Donc $x \notin A$ , soit $x \in \overline{A}$ . Réciproquement, si $\overline{B} \subset \overline{A}$ , le même argument appliqué aux complémentaires donne $\overline{\overline{A}} \subset \overline{\overline{B}}$ , c'est-à-dire $A \subset B$ .

$1 ⟺ 5$ . Si $A \subset B$ , aucun élément de $A$ n'est hors de $B$ , donc $A ∖ B = \emptyset$ . Réciproquement, si $A ∖ B = \emptyset$ et si $x \in A$ , alors $x \notin A ∖ B$ , donc la propriété « $x \in A$ et $x \notin B$ » est fausse ; comme $x \in A$ est vrai, c'est $x \notin B$ qui est faux, donc $x \in B$ . $□$

Ensemble des parties et produit cartésien

Définition

Soit $E$ un ensemble. On appelle ensemble des parties de $E$ , noté $P (E)$ , l'ensemble dont les éléments sont exactement les parties de $E$ :

A \in P (E) ⟺ A \subset E .

Exemple

Prenons $E = {a, b, c}$ , avec $a$ , $b$ , $c$ deux à deux distincts. L'ensemble $P (E)$ possède exactement huit éléments :

P (E) = {\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} .

On les a classés par nombre d'éléments : une partie vide, trois parties à un élément, trois parties à deux éléments, une partie à trois éléments.

Pour $E = \emptyset$ , on a $P (\emptyset) = {\emptyset}$ : cet ensemble n'est pas vide, il possède un élément, à savoir l'ensemble vide.

Remarque

Une confusion à éliminer tout de suite. Si $x$ est un élément de $E$ , alors :

$x \in E$ est vrai, mais $x \in P (E)$ est faux, car $x$ n'est pas une partie de $E$ ;
${x} \subset E$ est vrai, et ${x} \in P (E)$ est vrai également, car ${x}$ est bien une partie de $E$ ;
${x} \in E$ est en général faux.

Le passage aux accolades change la nature de l'objet : $x$ est un élément, ${x}$ est un ensemble à un élément. Le plus simple pour ne pas se perdre est de se dire que $P (E)$ est « d'un étage au-dessus » de $E$ .

Propriété

Soit $E$ un ensemble fini possédant $n$ éléments, avec $n \in N$ . Alors $P (E)$ est fini et possède $2^{n}$ éléments.

Démonstration. Par récurrence sur $n$ . Pour $n \in N$ , notons

H (n) : tout ensemble \overset{ˋ}{a} n \overset{ˊ}{e} l \overset{ˊ}{e} ments poss \overset{ˋ}{e} de exactement 2^{n} parties.

Initialisation. Pour $n = 0$ , le seul ensemble à $0$ élément est $\emptyset$ , et $P (\emptyset) = {\emptyset}$ possède exactement un élément. Or $2^{0} = 1$ : l'assertion $H (0)$ est vraie.

Hérédité. Soit $n \in N$ tel que $H (n)$ soit vraie. Soit $E$ un ensemble possédant $n + 1$ éléments. Comme $n + 1 ⩾ 1$ , l'ensemble $E$ n'est pas vide : fixons un élément $a$ de $E$ et posons $E^{'} = E ∖ {a}$ , qui possède $n$ éléments.

Séparons les parties de $E$ en deux catégories, selon qu'elles contiennent $a$ ou non. Notons

A = {A \in P (E); a \notin A} et B = {A \in P (E); a \in A} .

Ces deux ensembles sont disjoints et leur réunion est $P (E)$ tout entier, puisque toute partie de $E$ contient $a$ ou ne le contient pas, et pas les deux. Le nombre d'éléments de $P (E)$ est donc la somme des nombres d'éléments de $A$ et de $B$ .

Comptons $A$ . Une partie de $E$ ne contenant pas $a$ est exactement une partie de $E^{'}$ , et réciproquement toute partie de $E^{'}$ est une partie de $E$ ne contenant pas $a$ . Donc $A = P (E^{'})$ , qui possède $2^{n}$ éléments par hypothèse de récurrence.

Comptons $B$ . Considérons l'application $φ$ qui, à une partie $A^{'}$ de $E^{'}$ , associe $A^{'} \cup {a}$ . Cette partie contient $a$ et est incluse dans $E$ , donc $φ$ est bien une application de $P (E^{'})$ dans $B$ .

Elle est injective : si $A_{1}^{'} \cup {a} = A_{2}^{'} \cup {a}$ avec $A_{1}^{'}$ et $A_{2}^{'}$ inclus dans $E^{'} = E ∖ {a}$ , alors ni $A_{1}^{'}$ ni $A_{2}^{'}$ ne contient $a$ , et en retirant $a$ des deux membres on obtient

A_{1}^{'} = (A_{1}^{'} \cup {a}) ∖ {a} = (A_{2}^{'} \cup {a}) ∖ {a} = A_{2}^{'} .

Elle est surjective : si $A \in B$ , posons $A^{'} = A ∖ {a}$ . Alors $A^{'} \subset E^{'}$ et, puisque $a \in A$ , on a $A^{'} \cup {a} = A$ , c'est-à-dire $φ (A^{'}) = A$ .

L'application $φ$ est donc bijective, et $B$ possède autant d'éléments que $P (E^{'})$ , soit $2^{n}$ .

Conclusion de l'hérédité. Le nombre d'éléments de $P (E)$ vaut donc $2^{n} + 2^{n} = 2 \times 2^{n} = 2^{n + 1}$ , ce qui est $H (n + 1)$ .

Conclusion. Par récurrence, $H (n)$ est vraie pour tout $n \in N$ . $□$

Remarque

Le contrôle est immédiat sur l'exemple traité plus haut : $E = {a, b, c}$ possède $3$ éléments et $P (E)$ en possède $8 = 2^{3}$ . C'est cette formule qui justifie la notation $2^{E}$ , parfois employée à la place de $P (E)$ , que nous n'utiliserons pas.

Définition

Soient $E$ et $F$ deux ensembles. Le produit cartésien de $E$ par $F$ est l'ensemble des couples formés d'un élément de $E$ et d'un élément de $F$ :

E \times F = {(x, y); x \in E et y \in F} .

Deux couples $(x, y)$ et $(x^{'}, y^{'})$ sont égaux si et seulement si $x = x^{'}$ et $y = y^{'}$ .

Pour $n ⩾ 1$ , on note $E^{n} = E \times E \times \dots \times E$ ( $n$ facteurs) l'ensemble des $n$ -uplets $(x_{1}, x_{2}, \dots, x_{n})$ d'éléments de $E$ .

Remarque

L'ordre compte dans un couple, contrairement à ce qui se passe dans un ensemble : $(1, 2) \neq (2, 1)$ , alors que ${1, 2} = {2, 1}$ . De même, un couple peut avoir ses deux composantes égales : $(1, 1)$ est un couple parfaitement légitime, alors que ${1, 1}$ est simplement l'ensemble ${1}$ .

Le produit cartésien n'est pas commutatif : $E \times F$ et $F \times E$ sont en général différents. Enfin, si $E$ ou $F$ est vide, alors $E \times F$ est vide.

Exemple

Pour $E = {1, 2}$ et $F = {a, b, c}$ ,

E \times F = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)},

qui possède $6$ éléments. Le plan usuel s'identifie à $R^{2} = R \times R$ , et un point du plan de coordonnées $1,2$ et $1,44$ s'écrit $M (1,2; 1,44)$ .

Propriété

Si $E$ possède $n$ éléments et $F$ possède $m$ éléments, alors $E \times F$ possède $n m$ éléments. Plus généralement, $E^{p}$ possède $n^{p}$ éléments pour tout $p ⩾ 1$ .

Démonstration. Rangeons les couples de $E \times F$ dans un tableau à $n$ lignes (indexées par les éléments de $E$ ) et $m$ colonnes (indexées par les éléments de $F$ ). Chaque couple occupe une case et une seule, et chaque case correspond à un couple : il y a donc autant de couples que de cases, soit $n m$ . La seconde affirmation s'obtient par une récurrence immédiate sur $p$ , en écrivant $E^{p + 1} = E^{p} \times E$ . $□$

Recouvrements et partitions

Définition

Soient $E$ un ensemble et $(A_{i})_{i \in I}$ une famille de parties de $E$ , indexée par un ensemble $I$ non vide.

La famille est un recouvrement de $E$ lorsque la réunion de ses membres est $E$ tout entier, c'est-à-dire lorsque tout élément de $E$ appartient à au moins l'un des $A_{i}$ .
Les parties de la famille sont dites deux à deux disjointes lorsque, pour tous indices $i$ et $j$ de $I$ tels que $i \neq j$ , on a $A_{i} \cap A_{j} = \emptyset$ .
La famille est une partition de $E$ lorsque les trois conditions suivantes sont réunies :

chaque $A_{i}$ est non vide ;
les $A_{i}$ sont deux à deux disjoints ;
la réunion des $A_{i}$ est $E$ .

Remarque

Une partition traduit exactement l'idée de « découper $E$ en morceaux sans oubli ni double emploi ». La formulation équivalente à retenir est la suivante : la famille $(A_{i})_{i \in I}$ de parties non vides est une partition de $E$ si et seulement si tout élément de $E$ appartient à un et un seul des $A_{i}$ . La condition d'existence correspond au recouvrement, la condition d'unicité à la disjonction deux à deux.

Attention à la condition « non vide » : certains auteurs l'omettent, mais nous la conservons, car une partition sert à découper, et un morceau vide ne découpe rien.

Exemple

a. Pour $E = {1, 2, 3, 4, 5, 6}$ , la famille formée de $A_{1} = {1, 2}$ , $A_{2} = {3}$ et $A_{3} = {4, 5, 6}$ est une partition de $E$ .

b. Toujours pour ce même $E$ , la famille formée de ${1, 2, 3}$ et ${3, 4, 5, 6}$ est un recouvrement, mais pas une partition : l'élément $3$ appartient aux deux parties.

c. L'ensemble des entiers pairs et l'ensemble des entiers impairs forment une partition de $N$ .

d. Pour toute partie $A$ de $E$ distincte de $\emptyset$ et de $E$ , la famille formée de $A$ et $\overline{A}$ est une partition de $E$ . C'est la partition la plus simple, et la plus utilisée.

Remarque

Cette notion, qui paraît anodine, sera l'un des outils les plus employés de l'année. En probabilités, une partition de l'univers en événements porte un nom particulier, celui de système complet d'événements, et c'est sur elle que reposent la formule des probabilités totales et le conditionnement. En algèbre linéaire, on découpe un espace en sous-espaces. Retenez donc le réflexe : dès qu'un problème se sépare en cas exclusifs et exhaustifs, il y a une partition derrière.

Fonctions indicatrices

Définition

Soient $E$ un ensemble et $A$ une partie de $E$ . On appelle fonction indicatrice de $A$ l'application $1_{A} : E \to {0, 1}$ définie par

\begin{aligned} 1_{A} (x) & = 1 si x \in A, \\ 1_{A} (x) & = 0 si x \notin A . \end{aligned}

Exemple

Pour $E$ quelconque, $1_{\emptyset}$ est l'application nulle et $1_{E}$ est l'application constante égale à $1$ . Pour $E = R$ et $A = [0, 1]$ , l'application $1_{A}$ vaut $1$ sur le segment $[0, 1]$ et $0$ ailleurs.

Propriété

Soient $A$ et $B$ deux parties de $E$ .

$A = B$ si et seulement si $1_{A} = 1_{B}$ .
$A \subset B$ si et seulement si $1_{A} ⩽ 1_{B}$ , au sens où $1_{A} (x) ⩽ 1_{B} (x)$ pour tout $x \in E$ .
$1_{A}^{2} = 1_{A}$ .
$1_{A \cap B} = 1_{A} 1_{B}$ .
$1_{\overline{A}} = 1 - 1_{A}$ .
$1_{A \cup B} = 1_{A} + 1_{B} - 1_{A} 1_{B}$ .
$1_{A ∖ B} = 1_{A} (1 - 1_{B})$ et $1_{A Δ B} = 1_{A} + 1_{B} - 2 1_{A} 1_{B}$ .

Démonstration du point 1. Supposons $A = B$ . Alors, pour tout $x \in E$ , les assertions $x \in A$ et $x \in B$ ont la même valeur de vérité, donc $1_{A} (x)$ et $1_{B} (x)$ sont définis par le même cas et sont égaux. Ainsi $1_{A} = 1_{B}$ .

Réciproquement, supposons $1_{A} = 1_{B}$ et montrons $A = B$ par double inclusion. Soit $x \in A$ . Alors $1_{A} (x) = 1$ , donc $1_{B} (x) = 1$ , ce qui n'est possible que si $x \in B$ (sinon $1_{B} (x)$ vaudrait $0$ ). Donc $A \subset B$ , et le raisonnement symétrique donne $B \subset A$ . $□$

Démonstration du point 4. Soit $x \in E$ . Distinguons deux cas.

Si $x \in A \cap B$ , alors $x \in A$ et $x \in B$ , donc $1_{A \cap B} (x) = 1$ et $1_{A} (x) 1_{B} (x) = 1 \times 1 = 1$ . Les deux membres coïncident.
Si $x \notin A \cap B$ , alors $x \notin A$ ou $x \notin B$ , donc $1_{A} (x) = 0$ ou $1_{B} (x) = 0$ . Dans les deux cas le produit $1_{A} (x) 1_{B} (x)$ est nul, et $1_{A \cap B} (x) = 0$ . Les deux membres coïncident encore.

L'égalité vaut pour tout $x \in E$ , donc les deux applications sont égales. $□$

Démonstration du point 6. Soit $x \in E$ . Écrivons $a = 1_{A} (x)$ et $b = 1_{B} (x)$ , qui valent chacun $0$ ou $1$ , et comparons $1_{A \cup B} (x)$ à $a + b - a b$ dans les quatre cas possibles :

\begin{array}{cccc} a & b & a + b - a b & 1_{A \cup B} (x) \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array}

Justifions la dernière colonne. Le cas $a = b = 0$ correspond à $x \notin A$ et $x \notin B$ , donc $x \notin A \cup B$ et l'indicatrice vaut $0$ . Dans les trois autres cas, $x$ appartient à $A$ ou à $B$ , donc à $A \cup B$ , et l'indicatrice vaut $1$ . Les deux dernières colonnes coïncident ligne à ligne, donc $1_{A \cup B} (x) = a + b - a b$ pour tout $x \in E$ . $□$

Démonstration du point 5. Soit $x \in E$ . Si $x \in A$ , alors $x \notin \overline{A}$ , donc $1_{\overline{A}} (x) = 0 = 1 - 1 = 1 - 1_{A} (x)$ . Si $x \notin A$ , alors $x \in \overline{A}$ , donc $1_{\overline{A}} (x) = 1 = 1 - 0 = 1 - 1_{A} (x)$ . $□$

Méthode

Démontrer une identité ensembliste par les fonctions indicatrices. C'est souvent la voie la plus rapide, et la moins risquée, pour les identités qui font intervenir des complémentaires ou des différences symétriques.

Traduire chaque membre de l'égalité à démontrer en une expression algébrique en $1_{A}$ , $1_{B}$ , $1_{C}$ , à l'aide des formules ci-dessus.
Développer et simplifier les deux expressions, en utilisant sans hésiter la relation $1_{A}^{2} = 1_{A}$ (une indicatrice ne prend que les valeurs $0$ et $1$ , donc son carré vaut elle-même).
Constater que les deux expressions sont égales.
Conclure explicitement en invoquant le point 1 de la propriété : deux parties dont les indicatrices sont égales sont égales. Sans cette phrase, le calcul n'est pas une démonstration.

Limite de la méthode : elle devient vite lourde au-delà de trois parties, et elle demande de traduire l'inclusion en inégalité d'indicatrices, ce qui est moins naturel que la double inclusion.

Exemple

Redémontrons la loi de De Morgan par les indicatrices. Pour tout $x \in E$ , en posant $a = 1_{A} (x)$ et $b = 1_{B} (x)$ :

1_{\overline{A \cup B}} = 1 - 1_{A \cup B} = 1 - (1_{A} + 1_{B} - 1_{A} 1_{B}) = 1 - 1_{A} - 1_{B} + 1_{A} 1_{B} = (1 - 1_{A}) (1 - 1_{B}),

la dernière égalité se vérifiant en développant le produit. Or $(1 - 1_{A}) (1 - 1_{B}) = 1_{\overline{A}} 1_{\overline{B}} = 1_{\overline{A} \cap \overline{B}}$ . Les deux parties $\overline{A \cup B}$ et $\overline{A} \cap \overline{B}$ ont donc la même indicatrice : elles sont égales. $□$

Exemple

Une identité que la double inclusion rendrait pénible. Montrons que, pour toutes parties $A$ , $B$ , $C$ de $E$ ,

A \cap (B Δ C) = (A \cap B) Δ (A \cap C) .

Notons $a = 1_{A}$ , $b = 1_{B}$ et $c = 1_{C}$ . Le membre de gauche a pour indicatrice

1_{A \cap (B Δ C)} = a (b + c - 2 b c) = a b + a c - 2 a b c .

Le membre de droite a pour indicatrice, en appliquant la formule de la différence symétrique aux parties $A \cap B$ et $A \cap C$ :

1_{(A \cap B) Δ (A \cap C)} = a b + a c - 2 (a b) (a c) = a b + a c - 2 a^{2} b c = a b + a c - 2 a b c,

la dernière égalité utilisant $a^{2} = a$ . Les deux indicatrices sont égales, donc les deux parties le sont. $□$

Applications

Nous disposons maintenant d'ensembles. Il nous faut les relier entre eux, et c'est le rôle des applications. Toute la seconde moitié de l'année, des suites aux probabilités, consistera à étudier des applications d'un certain type.

Définitions

Définition

Soient $E$ et $F$ deux ensembles. Une application $f$ de $E$ dans $F$ est un procédé qui associe à chaque élément $x$ de $E$ un unique élément de $F$ , noté $f (x)$ . On écrit

f : E \to F, x \mapsto f (x) .

L'ensemble $E$ s'appelle l'ensemble de départ, l'ensemble $F$ l'ensemble d'arrivée. L'élément $f (x)$ s'appelle l'image de $x$ par $f$ . Si $y = f (x)$ , on dit que $x$ est un antécédent de $y$ par $f$ .

On note $F (E, F)$ l'ensemble des applications de $E$ dans $F$ .

Remarque

Application ou fonction ? Les deux mots ne sont pas synonymes. Une fonction de $E$ dans $F$ associe à certains éléments de $E$ (pas nécessairement tous) au plus un élément de $F$ ; l'ensemble des $x$ pour lesquels $f (x)$ est défini s'appelle son ensemble de définition. Une application est une fonction dont l'ensemble de définition est $E$ tout entier.

Ainsi, $x \mapsto \frac{1}{x}$ est une fonction de $R$ dans $R$ , mais pas une application de $R$ dans $R$ , car elle n'est pas définie en $0$ . En revanche, c'est une application de $R ∖ {0}$ dans $R$ . En pratique, dès qu'on écrit $f : E \to F$ , on affirme implicitement que $f (x)$ existe pour tout $x \in E$ , et cela fait partie de ce qu'il faut vérifier.

Définition

Deux applications $f$ et $g$ sont égales lorsque les trois conditions suivantes sont réunies :

elles ont le même ensemble de départ $E$ ;
elles ont le même ensemble d'arrivée $F$ ;
pour tout $x \in E$ , on a $f (x) = g (x)$ .

Remarque

La condition 2 surprend souvent : pourquoi l'ensemble d'arrivée ferait-il partie de l'identité d'une application, puisqu'il n'intervient pas dans le calcul de $f (x)$ ? Parce que certaines propriétés en dépendent de manière essentielle. Considérons

f : R \to R, x \mapsto x^{2} et g : R \to R_{+}, x \mapsto x^{2} .

Ces deux applications ont la même formule, mais ce ne sont pas les mêmes applications. Et surtout : $g$ est surjective (tout réel positif ou nul est un carré) tandis que $f$ ne l'est pas (le réel $- 1$ n'est le carré d'aucun réel). Une question du type « cette application est-elle surjective ? » est donc dépourvue de sens tant que l'ensemble d'arrivée n'est pas précisé.

Retenez la formule : changer l'ensemble d'arrivée change la surjectivité, changer l'ensemble de départ change l'injectivité.

Définition

Soient $E$ et $F$ deux ensembles.

L'identité de $E$ est l'application ${i d}_{E} : E \to E$ définie par ${i d}_{E} (x) = x$ pour tout $x \in E$ .
Si $f : E \to F$ et si $A$ est une partie de $E$ , la restriction de $f$ à $A$ est l'application

f_{∣ A} : A \to F, x \mapsto f (x) .

Réciproquement, si $g : A \to F$ et si $A \subset E$ , on appelle prolongement de $g$ à $E$ toute application $f : E \to F$ telle que $f_{∣ A} = g$ .

Remarque

Une restriction est unique, un prolongement ne l'est pas : il y a en général beaucoup de manières de prolonger une application, puisqu'on est libre de choisir les valeurs sur $E ∖ A$ . Notez aussi que $f$ et $f_{∣ A}$ ne sont pas la même application dès que $A \neq E$ , puisque leurs ensembles de départ diffèrent. Restreindre peut changer les propriétés : nous verrons que $x \mapsto x^{2}$ n'est pas injective sur $R$ , mais que sa restriction à $R_{+}$ l'est.

Exemple

a. $f : R \to R$ , $x \mapsto 3 x - 5$ .

b. $g : R \to R$ , $x \mapsto ∣ x ∣$ .

c. $h : R \to Z$ , $x \mapsto ⌊ x ⌋$ .

d. $u : N \to R$ , $n \mapsto \frac{1}{n + 1}$ , autrement dit une suite.

e. $1_{A} : E \to {0, 1}$ , l'indicatrice d'une partie $A$ .

f. $φ : P (E) \to P (E)$ , $A \mapsto \overline{A}$ .

Composition

Définition

Soient $f : E \to F$ et $g : F \to G$ deux applications. La composée de $f$ par $g$ est l'application

g \circ f : E \to G, x \mapsto g (f (x)) .

Remarque

Pour que $g \circ f$ ait un sens, il faut que l'ensemble d'arrivée de $f$ soit l'ensemble de départ de $g$ . C'est une contrainte réelle, à vérifier avant tout calcul.

Attention également à l'ordre de lecture : dans $g \circ f$ , c'est $f$ qui agit en premier. La notation se lit de droite à gauche, contrairement au sens de lecture habituel.

Propriété

Associativité. Soient $f : E \to F$ , $g : F \to G$ et $h : G \to H$ . Alors

h \circ (g \circ f) = (h \circ g) \circ f .

On peut donc écrire $h \circ g \circ f$ sans parenthèses.

Démonstration. Vérifions les trois conditions d'égalité de deux applications.

Ensembles de départ : $g \circ f$ va de $E$ dans $G$ , donc $h \circ (g \circ f)$ part de $E$ ; de même, $h \circ g$ va de $F$ dans $H$ , donc $(h \circ g) \circ f$ part de $E$ . Ensembles d'arrivée : les deux composées arrivent dans $H$ .

Images : soit $x \in E$ . Par définition de la composition, appliquée deux fois,

(h \circ (g \circ f)) (x) = h ((g \circ f) (x)) = h (g (f (x))),

((h \circ g) \circ f) (x) = (h \circ g) (f (x)) = h (g (f (x))) .

Les deux valeurs coïncident pour tout $x \in E$ , donc les deux applications sont égales. $□$

Propriété

Pour toute application $f : E \to F$ ,

f \circ {i d}_{E} = f et {i d}_{F} \circ f = f .

Démonstration. Les ensembles de départ et d'arrivée coïncident dans les deux cas. Pour tout $x \in E$ , on a $(f \circ {i d}_{E}) (x) = f ({i d}_{E} (x)) = f (x)$ et $({i d}_{F} \circ f) (x) = {i d}_{F} (f (x)) = f (x)$ . $□$

Remarque

La composition n'est pas commutative. Même lorsque les deux composées $g \circ f$ et $f \circ g$ ont un sens, elles sont en général différentes. Prenons

f : R \to R, x \mapsto x + 1 et g : R \to R, x \mapsto x^{2} .

Alors, pour tout réel $x$ ,

(g \circ f) (x) = g (x + 1) = (x + 1)^{2} et (f \circ g) (x) = f (x^{2}) = x^{2} + 1.

Ces deux applications sont distinctes : en $x = 1$ , la première vaut $4$ et la seconde vaut $2$ . Un seul contre-exemple suffit, c'est le mode de raisonnement vu en début de chapitre.

Image directe et image réciproque

Définition

Soit $f : E \to F$ .

L'image directe d'une partie $A$ de $E$ est la partie de $F$ définie par

f (A) = {y \in F; \exists x \in A, y = f (x)} .

L'image réciproque d'une partie $B$ de $F$ est la partie de $E$ définie par

f^{- 1} (B) = {x \in E; f (x) \in B} .

L'ensemble $f (E)$ s'appelle l'image de $f$ et se note aussi $I m (f)$ .

Propriété

Les deux traductions à connaître. Soit $f : E \to F$ , soit $A \subset E$ et soit $B \subset F$ .

y \in f (A) ⟺ \exists x \in A, y = f (x), x \in f^{- 1} (B) ⟺ f (x) \in B .

Ces deux équivalences ne sont que la relecture des définitions, mais ce sont elles qui résolvent tous les exercices : dès qu'une image directe ou réciproque apparaît, on la remplace immédiatement par sa traduction.

Remarque

Mise en garde majeure : la notation $f^{- 1} (B)$ ne suppose pas $f$ bijective. C'est le piège le plus fréquent du chapitre, et il coûte cher.

L'écriture $f^{- 1} (B)$ a un sens pour n'importe quelle application $f$ et n'importe quelle partie $B$ de $F$ : c'est l'ensemble des éléments de $E$ dont l'image tombe dans $B$ . Elle ne présuppose l'existence d'aucune application réciproque, et le symbole $f^{- 1}$ n'y désigne pas un objet autonome : il n'a de sens que collé à une partie.

Ainsi, pour $f : R \to R$ , $x \mapsto x^{2}$ , qui n'est ni injective ni surjective, on a parfaitement le droit d'écrire $f^{- 1} ({4}) = {- 2, 2}$ et $f^{- 1} ({- 1}) = \emptyset$ .

La règle de lecture : si l'argument de $f^{- 1}$ est une partie de $F$ , il s'agit de l'image réciproque et $f$ peut être quelconque ; si c'est un élément de $F$ , il s'agit de l'application réciproque, et là il faut que $f$ soit bijective.

Propriété

Soit $f : E \to F$ , soient $A$ et $A^{'}$ deux parties de $E$ , soient $B$ et $B^{'}$ deux parties de $F$ .

Si $A \subset A^{'}$ , alors $f (A) \subset f (A^{'})$ . Si $B \subset B^{'}$ , alors $f^{- 1} (B) \subset f^{- 1} (B^{'})$ .
$f^{- 1} (B \cap B^{'}) = f^{- 1} (B) \cap f^{- 1} (B^{'})$ .
$f^{- 1} (B \cup B^{'}) = f^{- 1} (B) \cup f^{- 1} (B^{'})$ .
$f^{- 1} (\overline{B}) = \overline{f^{- 1} (B)}$ , les complémentaires étant pris dans $F$ pour le premier et dans $E$ pour le second.
$f (A \cup A^{'}) = f (A) \cup f (A^{'})$ .
$f (A \cap A^{'}) \subset f (A) \cap f (A^{'})$ , et cette inclusion peut être stricte.
$A \subset f^{- 1} (f (A))$ et $f (f^{- 1} (B)) \subset B$ , ces inclusions pouvant être strictes.

Démonstration du point 2. Soit $x \in E$ . En appliquant deux fois la traduction de l'image réciproque, puis la définition de l'intersection :

\begin{aligned} x \in f^{- 1} (B \cap B^{'}) & ⟺ f (x) \in B \cap B^{'} \\ ⟺ (f (x) \in B et f (x) \in B^{'}) \\ ⟺ (x \in f^{- 1} (B) et x \in f^{- 1} (B^{'})) \\ ⟺ x \in f^{- 1} (B) \cap f^{- 1} (B^{'}) . \end{aligned}

Toutes les étapes sont des équivalences, donc les deux ensembles ont les mêmes éléments : ils sont égaux. $□$

Démonstration du point 5. Procédons par double inclusion.

Inclusion directe. Soit $y \in f (A \cup A^{'})$ . Il existe $x \in A \cup A^{'}$ tel que $y = f (x)$ . Si $x \in A$ , alors $y \in f (A)$ ; si $x \in A^{'}$ , alors $y \in f (A^{'})$ . Dans les deux cas, $y \in f (A) \cup f (A^{'})$ .

Inclusion réciproque. Soit $y \in f (A) \cup f (A^{'})$ . Si $y \in f (A)$ , il existe $x \in A$ tel que $y = f (x)$ ; comme $A \subset A \cup A^{'}$ , cet $x$ appartient à $A \cup A^{'}$ , donc $y \in f (A \cup A^{'})$ . Le cas $y \in f (A^{'})$ se traite de la même manière.

Par double inclusion, $f (A \cup A^{'}) = f (A) \cup f (A^{'})$ . $□$

Démonstration du point 6. Soit $y \in f (A \cap A^{'})$ . Il existe $x \in A \cap A^{'}$ tel que $y = f (x)$ . Comme $x \in A$ , on a $y \in f (A)$ ; comme $x \in A^{'}$ , on a $y \in f (A^{'})$ . Donc $y \in f (A) \cap f (A^{'})$ , ce qui prouve l'inclusion.

Montrons que l'inclusion réciproque est fausse en général, par un contre-exemple. Prenons $f : R \to R$ , $x \mapsto x^{2}$ , puis $A = {- 1}$ et $A^{'} = {1}$ . Alors $A \cap A^{'} = \emptyset$ , donc $f (A \cap A^{'}) = \emptyset$ . En revanche $f (A) = {1}$ et $f (A^{'}) = {1}$ , donc $f (A) \cap f (A^{'}) = {1}$ . L'inclusion est bien stricte. $□$

Remarque

Retenez la dissymétrie de cette liste : l'image réciproque se comporte parfaitement bien (elle respecte la réunion, l'intersection et le complémentaire), tandis que l'image directe ne respecte que la réunion.

L'explication tient aux quantificateurs. L'appartenance $x \in f^{- 1} (B)$ est une condition portant sur le seul élément $x$ , donc elle se combine sans peine avec « et » et « ou ». L'appartenance $y \in f (A)$ , elle, commence par un $\exists$ : elle affirme l'existence d'un antécédent dans $A$ . Si $y \in f (A) \cap f (A^{'})$ , on dispose d'un antécédent dans $A$ et d'un antécédent dans $A^{'}$ , mais rien ne garantit que ce soit le même. C'est exactement ce que montre le contre-exemple ci-dessus.

Exemple

Un exemple entièrement traité. Soit $f : R \to R$ définie par $f (x) = x^{2}$ . Déterminons $f ([- 1, 2])$ , $f^{- 1} ([1, 4])$ et $f^{- 1} ({- 1})$ .

Calcul de $f ([- 1, 2])$ . Montrons que $f ([- 1, 2]) = [0, 4]$ par double inclusion.

Soit $y \in f ([- 1, 2])$ . Il existe $x \in [- 1, 2]$ tel que $y = x^{2}$ . D'une part $y = x^{2} ⩾ 0$ . D'autre part, de $- 1 ⩽ x ⩽ 2$ on tire $∣ x ∣ ⩽ 2$ , donc $y = x^{2} = ∣ x ∣^{2} ⩽ 4$ . Ainsi $y \in [0, 4]$ .

Réciproquement, soit $y \in [0, 4]$ . Posons $x = \sqrt{y}$ , qui est bien défini puisque $y ⩾ 0$ . Comme $0 ⩽ y ⩽ 4$ , on a $0 ⩽ x ⩽ 2$ , donc $x \in [- 1, 2]$ , et $f (x) = y$ . Ainsi $y \in f ([- 1, 2])$ .

Par double inclusion, $f ([- 1, 2]) = [0, 4]$ .

Calcul de $f^{- 1} ([1, 4])$ . Par définition,

f^{- 1} ([1, 4]) = {x \in R; 1 ⩽ x^{2} ⩽ 4} .

Or, pour tout réel $x$ , on a $x^{2} = ∣ x ∣^{2}$ , et la condition $1 ⩽ ∣ x ∣^{2} ⩽ 4$ équivaut à $1 ⩽ ∣ x ∣ ⩽ 2$ , la fonction qui à un réel positif associe son carré étant strictement croissante sur $R_{+}$ . Cette dernière condition signifie que $x$ appartient à $[1, 2]$ ou à $[- 2, - 1]$ . Donc

f^{- 1} ([1, 4]) = [- 2, - 1] \cup [1, 2] .

Notons au passage que cet ensemble n'est pas un intervalle : l'image réciproque d'un intervalle n'a aucune raison d'en être un.

Calcul de $f^{- 1} ({- 1})$ . Par définition, $f^{- 1} ({- 1}) = {x \in R; x^{2} = - 1}$ . Le carré d'un réel étant positif ou nul, aucun réel ne convient. Donc

f^{- 1} ({- 1}) = \emptyset .

C'est bien la preuve que l'écriture $f^{- 1} (B)$ ne suppose rien : ici $f$ n'est pas bijective, et l'image réciproque est simplement vide.

Injectivité, surjectivité, bijectivité

Définition

Soit $f : E \to F$ .

$f$ est injective lorsque tout élément de $F$ possède au plus un antécédent par $f$ , ce qui s'écrit

\forall x \in E, \forall x^{'} \in E, (f (x) = f (x^{'}) ⟹ x = x^{'}) .

$f$ est surjective lorsque tout élément de $F$ possède au moins un antécédent par $f$ , ce qui s'écrit

\forall y \in F, \exists x \in E, y = f (x) .

$f$ est bijective lorsqu'elle est à la fois injective et surjective, c'est-à-dire lorsque tout élément de $F$ possède exactement un antécédent :

\forall y \in F, \exists! x \in E, y = f (x) .

Propriété

Négations. Soit $f : E \to F$ .

$f$ n'est pas injective si et seulement si

\exists x \in E, \exists x^{'} \in E, (x \neq x^{'} et f (x) = f (x^{'})) .

$f$ n'est pas surjective si et seulement si

\exists y \in F, \forall x \in E, f (x) \neq y .

Démonstration. Il suffit d'appliquer les règles de négation d'une proposition quantifiée établies au début du chapitre. Pour l'injectivité, la négation de $\forall x, \forall x^{'}, (f (x) = f (x^{'}) ⟹ x = x^{'})$ est $\exists x, \exists x^{'}, \neg (f (x) = f (x^{'}) ⟹ x = x^{'})$ , et la négation d'une implication $P ⟹ Q$ est « $P$ et $\neg Q$ », d'où le résultat. Pour la surjectivité, la négation de $\forall y, \exists x, y = f (x)$ est $\exists y, \forall x, y \neq f (x)$ . $□$

Remarque

Traduisez ces négations en gestes concrets. Pour réfuter l'injectivité, il suffit d'exhiber deux éléments distincts ayant la même image : un seul couple suffit, et le calcul tient en deux lignes. Pour réfuter la surjectivité, il faut exhiber un élément de $F$ sans antécédent, et justifier qu'il n'en a aucun, ce qui demande un vrai argument.

Propriété

La caractérisation par l'équation $f (x) = y$ . Soit $f : E \to F$ . Alors :

$f$ est injective si et seulement si, pour tout $y \in F$ , l'équation $f (x) = y$ d'inconnue $x \in E$ possède au plus une solution ;
$f$ est surjective si et seulement si, pour tout $y \in F$ , l'équation $f (x) = y$ d'inconnue $x \in E$ possède au moins une solution ;
$f$ est bijective si et seulement si, pour tout $y \in F$ , l'équation $f (x) = y$ d'inconnue $x \in E$ possède une unique solution.

Démonstration. Les solutions de l'équation $f (x) = y$ d'inconnue $x \in E$ sont exactement les antécédents de $y$ par $f$ . Les trois énoncés sont donc la reformulation littérale des définitions, en remplaçant « antécédent » par « solution ». $□$

Remarque

Cette caractérisation est la méthode attendue en classe préparatoire, en particulier dans le cas de la bijectivité : on ne démontre pas séparément l'injectivité et la surjectivité, on résout l'équation. On fixe $y$ dans l'ensemble d'arrivée, on résout par équivalences, et l'unique solution obtenue fournit du même coup l'application réciproque. C'est un raisonnement d'analyse-synthèse déguisé : l'analyse donne la seule valeur possible de $x$ , la synthèse vérifie qu'elle convient et qu'elle appartient bien à $E$ .

Exemple

a. $f : R \to R$ , $x \mapsto x^{2}$ n'est ni injective, ni surjective. En effet $f (- 1) = f (1) = 1$ avec $- 1 \neq 1$ , ce qui réfute l'injectivité. Et le réel $- 1$ n'a pas d'antécédent, puisqu'un carré de réel est positif ou nul, ce qui réfute la surjectivité.

b. $g : R_{+} \to R$ , $x \mapsto x^{2}$ est injective. Soient en effet $x$ et $x^{'}$ deux réels positifs ou nuls tels que $x^{2} = x^{' 2}$ . Alors $(x - x^{'}) (x + x^{'}) = 0$ , donc $x = x^{'}$ ou $x = - x^{'}$ . Dans le second cas, $x$ et $x^{'}$ étant positifs ou nuls et opposés, ils sont tous deux nuls, et l'on a encore $x = x^{'}$ . En revanche, $g$ n'est pas surjective, pour la même raison qu'en a.

c. $h : R_{+} \to R_{+}$ , $x \mapsto x^{2}$ est bijective : pour $y ⩾ 0$ fixé, l'équation $x^{2} = y$ d'inconnue $x ⩾ 0$ a pour unique solution $x = \sqrt{y}$ . Son application réciproque est $y \mapsto \sqrt{y}$ .

d. ${i d}_{E}$ est bijective pour tout ensemble $E$ , et elle est sa propre réciproque.

Remarque

Comparez les exemples a, b et c : c'est la même formule $x \mapsto x^{2}$ , et pourtant les trois applications sont différentes et ont des propriétés différentes. Restreindre l'ensemble de départ a rendu l'application injective ; restreindre l'ensemble d'arrivée l'a rendue surjective. C'est la meilleure illustration de la remarque faite plus haut sur l'égalité de deux applications.

Application réciproque

Définition

Soit $f : E \to F$ une application bijective. Pour tout $y \in F$ , il existe un unique $x \in E$ tel que $f (x) = y$ . L'application qui, à chaque $y \in F$ , associe cet unique antécédent s'appelle l'application réciproque de $f$ et se note $f^{- 1} : F \to E$ . Elle vérifie, par construction,

\forall x \in E, \forall y \in F, (y = f (x) ⟺ x = f^{- 1} (y)) .

Propriété

Soit $f : E \to F$ bijective. Alors

f^{- 1} \circ f = {i d}_{E} et f \circ f^{- 1} = {i d}_{F} .

De plus, $f^{- 1}$ est bijective et $(f^{- 1})^{- 1} = f$ .

Démonstration. Soit $x \in E$ et posons $y = f (x)$ . Par définition, $f^{- 1} (y)$ est l'unique antécédent de $y$ par $f$ . Or $x$ est un antécédent de $y$ , donc $f^{- 1} (y) = x$ , c'est-à-dire $(f^{- 1} \circ f) (x) = x$ . Comme $f^{- 1} \circ f$ et ${i d}_{E}$ vont toutes deux de $E$ dans $E$ , elles sont égales.

Soit maintenant $y \in F$ . Par définition, $f^{- 1} (y)$ est un antécédent de $y$ par $f$ , donc $f (f^{- 1} (y)) = y$ , c'est-à-dire $(f \circ f^{- 1}) (y) = y$ . Les ensembles de départ et d'arrivée coïncidant, $f \circ f^{- 1} = {i d}_{F}$ .

Enfin, l'équivalence $y = f (x) ⟺ x = f^{- 1} (y)$ est symétrique en $f$ et $f^{- 1}$ : elle montre que tout $x \in E$ possède un unique antécédent par $f^{- 1}$ , à savoir $f (x)$ . Donc $f^{- 1}$ est bijective et sa réciproque est $f$ . $□$

Propriété

Caractérisation d'une bijection par les composées. Soit $f : E \to F$ . Les deux assertions suivantes sont équivalentes.

$f$ est bijective.
Il existe une application $g : F \to E$ telle que $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ .

De plus, lorsque c'est le cas, une telle application $g$ est unique et vaut $f^{- 1}$ .

Démonstration. Implication $1 ⟹ 2$ . Si $f$ est bijective, l'application $g = f^{- 1}$ convient d'après la propriété précédente.

Implication $2 ⟹ 1$ . Supposons qu'il existe $g : F \to E$ vérifiant les deux égalités.

Montrons que $f$ est injective. Soient $x$ et $x^{'}$ dans $E$ tels que $f (x) = f (x^{'})$ . En appliquant $g$ aux deux membres, $g (f (x)) = g (f (x^{'}))$ , c'est-à-dire $(g \circ f) (x) = (g \circ f) (x^{'})$ . Comme $g \circ f = {i d}_{E}$ , cela s'écrit $x = x^{'}$ .

Montrons que $f$ est surjective. Soit $y \in F$ . Posons $x = g (y)$ , qui appartient bien à $E$ . Alors $f (x) = f (g (y)) = (f \circ g) (y) = {i d}_{F} (y) = y$ . Donc $y$ possède un antécédent.

Ainsi $f$ est bijective.

Unicité de $g$ . Soit $g$ vérifiant les deux égalités et soit $y \in F$ . Comme $f$ est bijective, notons $x$ l'unique antécédent de $y$ , de sorte que $f^{- 1} (y) = x$ . De $f (x) = y$ on tire $g (y) = g (f (x)) = (g \circ f) (x) = x = f^{- 1} (y)$ . Ceci valant pour tout $y \in F$ , et les ensembles de départ et d'arrivée coïncidant, on a $g = f^{- 1}$ . $□$

Remarque

Cette caractérisation est très commode : dès qu'on devine l'application réciproque, il suffit de calculer les deux composées pour tout démontrer d'un coup. Les deux égalités sont nécessaires : il ne suffit pas de vérifier $g \circ f = {i d}_{E}$ . Nous allons voir pourquoi juste après.

Propriété

Composition et propriétés. Soient $f : E \to F$ et $g : F \to G$ .

Si $f$ et $g$ sont injectives, alors $g \circ f$ est injective.
Si $f$ et $g$ sont surjectives, alors $g \circ f$ est surjective.
Si $f$ et $g$ sont bijectives, alors $g \circ f$ est bijective et

(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1} .

Si $g \circ f$ est injective, alors $f$ est injective.
Si $g \circ f$ est surjective, alors $g$ est surjective.

Démonstration du point 1. Soient $x$ et $x^{'}$ dans $E$ tels que $(g \circ f) (x) = (g \circ f) (x^{'})$ , c'est-à-dire $g (f (x)) = g (f (x^{'}))$ . Comme $g$ est injective et que $f (x)$ , $f (x^{'})$ appartiennent à $F$ , on en déduit $f (x) = f (x^{'})$ . Comme $f$ est injective, on conclut $x = x^{'}$ . $□$

Démonstration du point 2. Soit $z \in G$ . Comme $g$ est surjective, il existe $y \in F$ tel que $g (y) = z$ . Comme $f$ est surjective, il existe $x \in E$ tel que $f (x) = y$ . Alors $(g \circ f) (x) = g (f (x)) = g (y) = z$ . Donc $z$ possède un antécédent par $g \circ f$ . $□$

Démonstration du point 3. Les points 1 et 2 donnent déjà la bijectivité de $g \circ f$ . Pour identifier sa réciproque, utilisons la caractérisation par les composées avec l'application $h = f^{- 1} \circ g^{- 1}$ , qui va bien de $G$ dans $E$ . En utilisant l'associativité de la composition :

h \circ (g \circ f) = f^{- 1} \circ g^{- 1} \circ g \circ f = f^{- 1} \circ {i d}_{F} \circ f = f^{- 1} \circ f = {i d}_{E},

(g \circ f) \circ h = g \circ f \circ f^{- 1} \circ g^{- 1} = g \circ {i d}_{F} \circ g^{- 1} = g \circ g^{- 1} = {i d}_{G} .

D'après la caractérisation, $g \circ f$ est bijective et sa réciproque est $h = f^{- 1} \circ g^{- 1}$ . $□$

Démonstration du point 4. Soient $x$ et $x^{'}$ dans $E$ tels que $f (x) = f (x^{'})$ . En appliquant $g$ aux deux membres, on obtient $g (f (x)) = g (f (x^{'}))$ , c'est-à-dire $(g \circ f) (x) = (g \circ f) (x^{'})$ . Comme $g \circ f$ est injective, il vient $x = x^{'}$ . Donc $f$ est injective. $□$

Démonstration du point 5. Soit $z \in G$ . Comme $g \circ f$ est surjective, il existe $x \in E$ tel que $(g \circ f) (x) = z$ , c'est-à-dire $g (f (x)) = z$ . Posons $y = f (x)$ : c'est un élément de $F$ , et $g (y) = z$ . Donc $z$ possède un antécédent par $g$ , et $g$ est surjective. $□$

Remarque

Les points 4 et 5 sont plus fins qu'ils n'en ont l'air, et ils sont souvent mal mémorisés. Retenez le principe : c'est celle des deux applications qui est "du bon côté" qui hérite de la propriété. L'application $f$ agit en premier, donc elle hérite de l'injectivité ; l'application $g$ agit en dernier, donc elle hérite de la surjectivité.

Les réciproques sont fausses. Prenons $f : R_{+} \to R$ , $x \mapsto x$ (l'inclusion) et $g : R \to R_{+}$ , $x \mapsto x^{2}$ . Alors $g \circ f : R_{+} \to R_{+}$ , $x \mapsto x^{2}$ est bijective, pourtant $f$ n'est pas surjective et $g$ n'est pas injective.

Voici enfin pourquoi, dans la caractérisation des bijections, il faut vérifier les deux composées. Gardons la même application $f : R_{+} \to R$ , $x \mapsto x$ , et prenons cette fois $g : R \to R_{+}$ , $x \mapsto ∣ x ∣$ . Pour tout $x ⩾ 0$ , $(g \circ f) (x) = ∣ x ∣ = x$ , donc $g \circ f = {i d}_{R_{+}}$ , et pourtant $f$ n'est pas bijective, puisqu'aucun réel strictement négatif n'a d'antécédent. La seconde composée, elle, n'est pas l'identité : $(f \circ g) (- 1) = ∣ - 1 ∣ = 1 \neq - 1$ . Une seule des deux égalités ne prouve donc rien.

Méthodes récapitulatives

Méthode

Montrer qu'une application $f : E \to F$ est injective.

Rédaction type : « Soient $x$ et $x^{'}$ dans $E$ tels que $f (x) = f (x^{'})$ . » Puis on manipule cette égalité jusqu'à obtenir $x = x^{'}$ . On peut aussi passer par la contraposée, « si $x \neq x^{'}$ alors $f (x) \neq f (x^{'})$ », mais c'est en général moins commode car on part d'une information négative.

Erreur à éviter : partir de $x = x^{'}$ pour en déduire $f (x) = f (x^{'})$ . Cela ne démontre rien, c'est vrai pour toute application.

Méthode

Montrer qu'une application $f : E \to F$ n'est PAS injective.

Il suffit d'exhiber deux éléments distincts de $E$ ayant la même image, et de le vérifier par le calcul. Une seule ligne suffit : « On a $f (- 1) = f (1) = 1$ alors que $- 1 \neq 1$ , donc $f$ n'est pas injective. » Ne pas oublier de dire que les deux éléments sont distincts, c'est la moitié de l'argument.

Méthode

Montrer qu'une application $f : E \to F$ est surjective.

Rédaction type : « Soit $y \in F$ . » Puis on construit explicitement un antécédent : « Posons $x = \dots$ ». Deux vérifications sont obligatoires et souvent oubliées :

vérifier que le $x$ construit appartient bien à $E$ (c'est là que se cachent les conditions d'existence, dénominateurs non nuls, quantités positives sous une racine) ;
vérifier que $f (x) = y$ , par le calcul.

Méthode

Montrer qu'une application $f : E \to F$ n'est PAS surjective.

Il faut exhiber un élément $y_{0}$ de $F$ et démontrer qu'il n'a aucun antécédent, c'est-à-dire que l'équation $f (x) = y_{0}$ n'a pas de solution dans $E$ . Le plus souvent, on établit une propriété vérifiée par toutes les valeurs de $f$ (par exemple « $f (x) ⩾ 0$ pour tout $x$ »), puis on choisit $y_{0}$ qui ne la vérifie pas.

Méthode

Montrer qu'une application $f : E \to F$ est bijective et déterminer sa réciproque.

C'est la méthode la plus rentable, et celle qui est attendue par défaut.

« Soit $y \in F$ . Cherchons les $x \in E$ tels que $f (x) = y$ . »
Résoudre l'équation par équivalences successives, en gardant à l'esprit que l'inconnue est $x$ et que $y$ est un paramètre fixé.
Conclure que l'équation possède une unique solution, et vérifier que cette solution appartient bien à $E$ . C'est l'étape que les correcteurs traquent.
Conclure : « Tout élément de $F$ possède un unique antécédent, donc $f$ est bijective », puis « et $f^{- 1} (y) = \dots$ ».

Variante lorsqu'on devine la réciproque : poser $g$ , vérifier $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ , et invoquer la caractérisation. Les deux vérifications sont obligatoires.

Exemple

Un exemple complet : une homographie. Soit

f : R ∖ {2} \to R ∖ {1}, f (x) = \frac{x + 3}{x - 2} .

Étape 0 : $f$ est bien une application à valeurs dans l'ensemble annoncé. Pour $x \neq 2$ , le dénominateur $x - 2$ est non nul, donc $f (x)$ est bien défini. Vérifions ensuite que $f (x) \neq 1$ . Si l'on avait $f (x) = 1$ , alors $x + 3 = x - 2$ , d'où $3 = - 2$ , ce qui est absurde. Donc $f (x)$ appartient bien à $R ∖ {1}$ , et $f$ est une application de $R ∖ {2}$ dans $R ∖ {1}$ .

Étape 1 : résolution de l'équation. Soit $y \in R ∖ {1}$ . Cherchons les $x \in R ∖ {2}$ tels que $f (x) = y$ . Comme $x - 2 \neq 0$ , on peut multiplier par $x - 2$ sans changer l'ensemble des solutions :

\begin{aligned} \frac{x + 3}{x - 2} = y & ⟺ x + 3 = y (x - 2) \\ ⟺ x + 3 = y x - 2 y \\ ⟺ x - y x = - 2 y - 3 \\ ⟺ x (1 - y) = - (2 y + 3) \\ ⟺ x = \frac{2 y + 3}{y - 1}, \end{aligned}

la dernière équivalence étant licite car $y \neq 1$ , donc $1 - y \neq 0$ (on divise par $1 - y$ et l'on change les signes du numérateur et du dénominateur).

Étape 2 : la solution appartient bien à l'ensemble de départ. Posons $x_{0} = \frac{2 y + 3}{y - 1}$ . Il faut vérifier que $x_{0} \neq 2$ . Si l'on avait $x_{0} = 2$ , alors $2 y + 3 = 2 (y - 1) = 2 y - 2$ , d'où $3 = - 2$ , ce qui est absurde. Donc $x_{0} \in R ∖ {2}$ .

Étape 3 : conclusion. Pour tout $y \in R ∖ {1}$ , l'équation $f (x) = y$ possède une unique solution dans $R ∖ {2}$ . Donc $f$ est bijective, et

f^{- 1} : R ∖ {1} \to R ∖ {2}, f^{- 1} (y) = \frac{2 y + 3}{y - 1} .

Vérification par les composées. Contrôlons le résultat, ce qui ne coûte que deux calculs. Pour $y \neq 1$ , en multipliant numérateur et dénominateur par $y - 1$ :

f (f^{- 1} (y)) = \frac{\frac{2 y + 3}{y - 1} + 3}{\frac{2 y + 3}{y - 1} - 2} = \frac{(2 y + 3) + 3 (y - 1)}{(2 y + 3) - 2 (y - 1)} = \frac{2 y + 3 + 3 y - 3}{2 y + 3 - 2 y + 2} = \frac{5 y}{5} = y .

Pour $x \neq 2$ , en multipliant numérateur et dénominateur par $x - 2$ :

f^{- 1} (f (x)) = \frac{2 \times \frac{x + 3}{x - 2} + 3}{\frac{x + 3}{x - 2} - 1} = \frac{2 (x + 3) + 3 (x - 2)}{(x + 3) - (x - 2)} = \frac{2 x + 6 + 3 x - 6}{5} = \frac{5 x}{5} = x .

Les deux composées sont bien les identités correspondantes : le résultat est confirmé.

Remarque. L'application réciproque a la même forme que $f$ , et les deux réels exclus se sont échangés : $2$ est exclu du départ de $f$ et de l'arrivée de $f^{- 1}$ , tandis que $1$ est exclu de l'arrivée de $f$ et du départ de $f^{- 1}$ . Ce n'est pas un hasard, et ce sera systématique pour les homographies. $□$

Exemple

Un dernier exemple, pour fixer la méthode dans un cadre plus simple. Soit $f : R \to R$ définie par $f (x) = 3 x - 5$ . Soit $y \in R$ . Alors

3 x - 5 = y ⟺ 3 x = y + 5 ⟺ x = \frac{y + 5}{3} .

L'équation possède donc une unique solution, qui est bien un réel. Ainsi $f$ est bijective, et $f^{- 1} (y) = \frac{y + 5}{3}$ .

Contrôle : $f (f^{- 1} (y)) = 3 \times \frac{y + 5}{3} - 5 = y + 5 - 5 = y$ , et $f^{- 1} (f (x)) = \frac{(3 x - 5) + 5}{3} = \frac{3 x}{3} = x$ . $□$

Ce qu'il faut retenir

Ce chapitre ne contient presque aucun théorème spectaculaire, et c'est normal : ce qu'il installe, ce sont des gestes, que vous répéterez pendant deux ans. En voici la liste, avec l'endroit où chacun resservira.

Nier une assertion quantifiée. On échange $\forall$ et $\exists$ , on nie la conclusion. Ce geste servira chaque fois qu'il faudra montrer qu'une propriété est fausse, en particulier pour prouver qu'une suite n'est pas convergente ou qu'une application n'est pas injective.

Choisir un mode de raisonnement. Direct, contraposée, absurde, disjonction de cas, contre-exemple, analyse-synthèse : le bon choix fait souvent la moitié de la difficulté. L'analyse-synthèse, en particulier, est la structure cachée de toute recherche d'application réciproque et de toute décomposition en éléments simples.

Rédiger une récurrence. Trois étapes nommées, une hypothèse énoncée avec précision, une conclusion. C'est l'outil de base pour tout ce qui est indexé par $N$ : suites définies par récurrence, puissances de matrices, formules de sommation.

Manipuler une somme. Changement d'indice, télescopage, interversion de deux symboles, sommes usuelles connues par cœur. Vous vous en servirez dans les suites, dans les calculs de puissances de matrices, et massivement en probabilités où toute espérance est une somme.

Démontrer une égalité d'ensembles par double inclusion. « Soit $x \in A$ ... donc $x \in B$ », puis l'inverse. C'est le geste central du chapitre, celui qui reviendra en algèbre linéaire chaque fois qu'il faudra montrer l'égalité de deux sous-espaces vectoriels.

Prouver une bijection en résolvant $f (x) = y$ . On fixe $y$ dans l'ensemble d'arrivée, on résout par équivalences, on vérifie que la solution est bien dans l'ensemble de départ. Cette méthode donne la bijectivité et la réciproque d'un seul coup, et elle réapparaîtra pour les applications linéaires et pour les changements de variables.

Enfin, deux réflexes de vigilance à conserver toute l'année : l'écriture $f^{- 1} (B)$ ne suppose jamais que $f$ soit bijective, et deux applications qui ont la même formule mais pas le même ensemble d'arrivée ne sont pas la même application.

Le cours en PDF(PDF, 349 Ko)

Bloqué sur « Raisonnement et vocabulaire ensembliste » ?

On peut le travailler ensemble dès cette semaine. La première heure est offerte — on fait le point honnêtement, et vous repartez au minimum avec une méthode.

Réserver ma 1ʳᵉ heure offerte