ECG appliquées · Chapitre 01 · Premier semestre

Raisonnement et vocabulaire ensembliste

1re année

Logique, quantificateurs, récurrence, sommes et produits, ensembles, applications, injection, surjection, bijection.

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 principalement 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 de quelques mots que vous employez déjà sans y penser : « et », « ou », « si ... alors », « pour tout », « il existe ». Nous recenserons ensuite les grandes manières de conduire une démonstration, puis nous mettrons en place le vocabulaire des sommes, 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, une application linéaire sera d'abord une application. En analyse, la convergence d'une suite sera un énoncé quantifié. Un étudiant qui manipule mal les quantificateurs ne pourra pas rédiger correctement une démonstration au second semestre, quelle que soit son habileté calculatoire.

Notations fixées pour tout le 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 de $B$ ; $\emptyset$ est l'ensemble vide ; $f : E \to F$ est une application de $E$ dans $F$ ; ${i d}_{E}$ est l'application identité de $E$ . 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 la proposition $P$ , le symbole $⟹$ note l'implication et le symbole $⟺$ note l'équivalence. Enfin, le symbole $□$ marque la fin d'une démonstration.

L'ensemble des entiers compris entre $1$ et $n$ sera toujours noté ${1, 2, \dots, n}$ . Certains ouvrages le désignent par des doubles crochets ; nous ne les emploierons pas, afin que toutes les notations de ce cours restent lisibles sans convention supplémentaire.

É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 : la très grande majorité des erreurs de rédaction commises en première année vient d'un flottement sur l'un de ces mots.

Propositions et valeurs de vérité

Définition

Une proposition (on dit aussi une assertion) 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 la proposition le fait qu'elle soit vraie (on note V) ou fausse (on note F). Une proposition ne peut pas être à la fois vraie et fausse, et il n'existe pas de troisième valeur possible.

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

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

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

c. « $7$ est un multiple de $3$ » : fausse.

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

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

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

Attention : une proposition n'a pas besoin d'être vraie pour être une proposition. « $7$ est un multiple de $3$ » est un énoncé parfaitement clair, simplement faux. En revanche, « $x > 0$ » n'est pas une proposition tant que $x$ n'a pas été fixé.

Remarque

Un énoncé dont la valeur de 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 proposition de deux façons seulement :

en fixant la variable : « pour $x = 3$ , l'énoncé $x > 0$ est vrai » ;
en quantifiant la variable : « pour tout réel $x$ , $x^{2} ⩾ 0$ ».

C'est le second procédé qui sera de loin le plus fréquent, et c'est l'objet des quantificateurs, que nous verrons un peu plus loin.

Les connecteurs : négation, « et », « ou »

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

Définition

Soient $P$ et $Q$ deux propositions.

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

Ces trois définitions se résument dans une table de vérité : un tableau qui énumère tous les cas possibles pour les propositions de départ, et donne pour chacun d'eux la valeur de vérité de la proposition construite. Avec deux propositions $P$ et $Q$ , il y a exactement quatre cas.

$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

Une table de vérité est un outil de démonstration à part entière : deux propositions construites à partir de $P$ et de $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 : la proposition « $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, la proposition « $2$ est pair ou $2 < 3$ » est vraie, bien que ses deux membres soient vrais simultanément. Lorsque l'on veut vraiment exprimer un « ou » exclusif, on l'écrit explicitement : « $P$ ou $Q$ , et pas les deux ».

Remarque

Un point de vocabulaire qui déroute souvent : écrire « $x = 2$ ou $x = 3$ » ne signifie pas que l'on hésite, ni que le travail n'est pas terminé. C'est une proposition 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$ et $R$ trois propositions. Les propositions citées dans chacun des points suivants 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$ ».
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 du point 1. La table de vérité comporte deux lignes seulement, puisqu'il n'y a qu'une proposition de départ.

$P$	$\neg P$	$\neg (\neg P)$
V	F	V
F	V	F

Les colonnes de $P$ et de $\neg (\neg P)$ coïncident : ces deux propositions ont bien la même valeur de vérité. Les points 2, 3 et 4 se démontrent exactement de la même manière, en écrivant la table correspondante (huit lignes pour les points 3 et 4, qui font intervenir trois propositions). Nous détaillerons ce travail sur les lois de De Morgan, ci-dessous. $□$

Négation d'une conjonction et d'une disjonction

Ces deux règles, appelées lois de De Morgan, servent en permanence : à chaque fois que l'on nie une hypothèse pour raisonner par l'absurde, à chaque fois que l'on traduit « ce nombre n'est ni pair ni multiple de $3$ ».

Propriété

Soient $P$ et $Q$ deux propositions.

$\neg (P et Q)$ a la même valeur de vérité que « $\neg P$ ou $\neg Q$ ».
$\neg (P ou Q)$ a la même valeur de vérité que « $\neg P$ et $\neg Q$ ».

Autrement dit : la négation échange « et » et « ou », et nie chacun des deux membres.

Démonstration. Le principe est toujours le même : on écrit une table de vérité comportant une colonne pour chacune des deux propositions à comparer, et on constate que ces deux colonnes coïncident ligne à ligne.

Pour le point 1 :

$P$	$Q$	$\neg (P$ et $Q)$	$\neg P$ ou $\neg Q$
V	V	F	F
V	F	V	V
F	V	V	V
F	F	V	V

Détaillons la deuxième ligne, à titre de contrôle : $P$ est vraie et $Q$ est fausse, donc « $P$ et $Q$ » est fausse, donc sa négation est vraie ; par ailleurs $\neg P$ est fausse et $\neg Q$ est vraie, donc « $\neg P$ ou $\neg Q$ » est vraie. Les deux colonnes donnent bien V. Les quatre lignes coïncident : le point 1 est démontré.

Pour le point 2 :

$P$	$Q$	$\neg (P$ ou $Q)$	$\neg P$ et $\neg Q$
V	V	F	F
V	F	F	F
F	V	F	F
F	F	V	V

Les deux dernières colonnes valent successivement F, F, F, V : elles sont identiques. $□$

Exemple

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

a. Soit $x$ un réel. La négation de « $x ⩾ 0$ et $x ⩽ 1$ », c'est-à-dire de « $x$ appartient à $[0, 1]$ », est « $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 « $x = 2$ ou $x = 3$ » est « $x \neq 2$ et $x \neq 3$ ».

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

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

Remarque

La même structure réapparaîtra 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 : $x \in A \cup B$ signifie exactement « $x \in A$ ou $x \in B$ ».

Les quantificateurs

Reprenons le prédicat « $x^{2} ⩾ 0$ ». Pour en faire une proposition, on précise combien de valeurs de $x$ sont concernées. C'est le rôle des quantificateurs.

Définition

Soit $E$ un ensemble et $P (x)$ un prédicat portant sur un élément $x$ de $E$ .

Le quantificateur universel $\forall$ , lu « pour tout » ou « quel que soit », construit la proposition

\forall x \in E, P (x)

qui est vraie lorsque $P (x)$ est vraie pour chaque élément $x$ de $E$ , et fausse dès qu'il existe au moins un élément de $E$ pour lequel $P (x)$ est fausse.

Le quantificateur existentiel $\exists$ , lu « il existe », construit la proposition

\exists x \in E, P (x)

qui est vraie lorsqu'il y a au moins un élément $x$ de $E$ pour lequel $P (x)$ est vraie, et fausse lorsqu'il n'y en a aucun.

On note enfin $\exists! x \in E, P (x)$ , lu « il existe un unique $x$ de $E$ tel que $P (x)$ », la proposition qui affirme qu'il y a exactement un tel élément.

Exemple

a. « $\forall x \in R, x^{2} ⩾ 0$ » est vraie : le carré d'un réel est toujours positif.

b. « $\forall x \in R, x^{2} ⩾ x$ » est fausse : pour $x = \frac{1}{2}$ , on a $x^{2} = \frac{1}{4} < \frac{1}{2}$ .

c. « $\exists n \in N, n^{2} = 49$ » est vraie : l'entier $n = 7$ convient.

d. « $\exists n \in N, n^{2} = 50$ » est fausse : $7^{2} = 49$ et $8^{2} = 64$ , et la suite des carrés est strictement croissante, donc aucun carré d'entier ne vaut $50$ .

e. « $\exists! x \in R, 3 x + 1 = 7$ » est vraie : l'équation a pour unique solution $x = 2$ .

Remarque

La lettre employée dans un quantificateur est muette : elle n'a de sens qu'à l'intérieur de la proposition qu'elle sert à écrire, et on peut la remplacer par n'importe quelle autre lettre non déjà utilisée. Les propositions « $\forall x \in R, x^{2} ⩾ 0$ » et « $\forall t \in R, t^{2} ⩾ 0$ » sont la même proposition. En revanche, écrire « $\forall x \in R, x^{2} ⩾ y$ » sans avoir dit ce qu'est $y$ n'a aucun sens : la variable $y$ est libre, l'énoncé n'est pas une proposition.

Remarque

L'ensemble sur lequel on quantifie fait partie de l'énoncé. La proposition « $\exists x, x^{2} = 2$ » est fausse dans $N$ , fausse dans $Z$ , et vraie dans $R$ . Écrire un quantificateur sans son ensemble, c'est écrire un énoncé dont on ne peut pas dire s'il est vrai. On écrit donc toujours $\forall x \in E$ et $\exists x \in E$ , jamais $\forall x$ tout seul.

Quantifications implicites et ordre des quantificateurs

Beaucoup d'énoncés du cours sont quantifiés sans que le symbole apparaisse. C'est notamment le cas des propositions conditionnelles.

Remarque

Quand on écrit « si $x > 2$ , alors $x^{2} > 4$ », on affirme en réalité

\forall x \in R, (x > 2 ⟹ x^{2} > 4)

Le « pour tout $x$ réel » est implicite, mais il est bien là : c'est lui qui donne un sens à la lettre $x$ . De même, l'identité remarquable « $(a + b)^{2} = a^{2} + 2 a b + b^{2}$ » signifie « $\forall a \in R, \forall b \in R, (a + b)^{2} = a^{2} + 2 a b + b^{2}$ ».

Cette quantification implicite explique la formule rituelle qui ouvre presque toutes les démonstrations : « Soit $x \in R$ . » Elle signifie « je me donne un réel quelconque, et je vais montrer la propriété pour celui-là, sans jamais utiliser autre chose que le fait qu'il est réel ». Comme il était quelconque, le raisonnement vaut pour tous.

Lorsque plusieurs quantificateurs se suivent, leur ordre fait partie de l'énoncé et on ne peut pas le modifier.

Propriété

Deux quantificateurs de même nature qui se suivent peuvent être échangés sans changer le sens :

\forall x \in E, \forall y \in F, P (x, y) et \forall y \in F, \forall x \in E, P (x, y)

sont la même proposition, et de même pour deux $\exists$ consécutifs.

En revanche, échanger un $\forall$ et un $\exists$ change le sens de la proposition. On a seulement l'implication

(\exists y \in F, \forall x \in E, P (x, y)) ⟹ (\forall x \in E, \exists y \in F, P (x, y))

et la réciproque est fausse en général.

Démonstration de l'implication. Supposons qu'il existe $y_{0} \in F$ tel que, pour tout $x \in E$ , $P (x, y_{0})$ soit vraie. Soit $x \in E$ quelconque. Alors $y_{0}$ est un élément de $F$ pour lequel $P (x, y_{0})$ est vraie, donc la proposition « $\exists y \in F, P (x, y)$ » est vraie. Comme $x$ était quelconque, on a bien « $\forall x \in E, \exists y \in F, P (x, y)$ ». $□$

L'idée à retenir est la suivante : dans l'écriture « $\forall x, \exists y$ », le $y$ a le droit de dépendre du $x$ , puisqu'il est choisi après lui ; dans l'écriture « $\exists y, \forall x$ », le $y$ est choisi une fois pour toutes, avant de connaître $x$ , donc il doit convenir simultanément à tous les $x$ . La seconde affirmation est donc bien plus forte que la première.

Exemple

Deux propositions qui ne diffèrent que par l'ordre des quantificateurs. Considérons la suite définie par $u_{n} = n$ pour tout $n \in N$ , et les deux propositions suivantes.

(A) : \forall n \in N, \exists M \in R, u_{n} ⩽ M (B) : \exists M \in R, \forall n \in N, u_{n} ⩽ M

La proposition $(A)$ est vraie, et même sans aucun intérêt. Soit en effet $n \in N$ . Le réel $M = n$ convient, puisque $u_{n} = n ⩽ n$ . Ici, $M$ a été choisi après $n$ : il dépend de $n$ , et c'est autorisé. Autrement dit, $(A)$ dit seulement « chaque terme de la suite est majoré par un certain réel », ce qui est vrai de n'importe quelle suite.

La proposition $(B)$ est fausse. Elle affirme qu'un même réel $M$ majore tous les termes à la fois : c'est la définition d'une suite majorée. Or, soit $M$ un réel quelconque. Choisissons un entier $n$ strictement supérieur à $M$ , ce qui est possible puisque $N$ n'est pas majoré (nous le redémontrerons plus loin dans ce chapitre). Alors $u_{n} = n > M$ , donc $M$ ne majore pas tous les termes. Aucun réel ne convient : $(B)$ est fausse.

Moralité : ces deux propositions s'écrivent avec exactement les mêmes symboles, dans un ordre différent, et l'une est un truisme quand l'autre est une propriété forte qui, ici, est fausse. C'est pourquoi on n'échange jamais un $\forall$ et un $\exists$ à la légère.

Exemple

La même chose, en langage d'entreprise. Une société propose un catalogue d'offres tarifaires à ses clients. Comparons :

(A) : \forall c \in C, \exists o \in O, « l’offre o convient au client c »

(B) : \exists o \in O, \forall c \in C, « l’offre o convient au client c »

La proposition $(A)$ dit : « chaque client trouve dans le catalogue au moins une offre qui lui convient » ; l'offre choisie peut changer d'un client à l'autre. La proposition $(B)$ dit : « il existe une offre unique, la même pour tout le monde, qui convient à tous les clients ». Une entreprise peut très bien satisfaire $(A)$ avec un catalogue de douze offres et ne pas satisfaire $(B)$ du tout. Et si $(B)$ est vraie, alors $(A)$ l'est aussi : c'est exactement l'implication démontrée plus haut.

Remarque

Les quantificateurs ne sont pas des abréviations. Le programme officiel est explicite sur ce point : l'emploi des symboles $\forall$ et $\exists$ en guise d'abréviations d'écriture est proscrit. On les écrit dans les énoncés formels que l'on veut rendre parfaitement précis, typiquement une définition ou une propriété à nier ; on ne les écrit jamais dans les phrases de rédaction d'une démonstration.

À ne pas écrire. « $\forall x \in R$ , $f (x) > 0$ car $\exists$ une forme canonique. »

À écrire. « Soit $x \in R$ . En écrivant $f (x)$ sous forme canonique, on obtient $f (x) = (x - 2)^{2} + 1 > 0$ . Comme $x$ était quelconque, $f$ est strictement positive sur $R$ . »

Une copie de concours se rédige en français, avec des phrases. Les symboles logiques sont là pour lever une ambiguïté, pas pour gagner du temps.

Négation d'une proposition quantifiée

C'est le point technique le plus rentable de toute la section : il intervient dans chaque raisonnement par l'absurde, dans chaque recherche de contre-exemple, et dans toutes les définitions « négatives » des chapitres d'analyse.

Propriété

Soit $E$ un ensemble et $P (x)$ un prédicat sur $E$ . Alors :

\neg (\forall x \in E, P (x)) a la m \hat{e} me valeur de v \overset{ˊ}{e} rit \overset{ˊ}{e} que \exists x \in E, \neg P (x)

\neg (\exists x \in E, P (x)) a la m \hat{e} me valeur de v \overset{ˊ}{e} rit \overset{ˊ}{e} que \forall x \in E, \neg P (x)

Justification. Dire que « pour tout $x$ de $E$ , $P (x)$ » est fausse, c'est dire que la propriété $P$ prend en défaut au moins un élément de $E$ , autrement dit qu'il existe un $x$ de $E$ pour lequel $P (x)$ est fausse : c'est bien « $\exists x \in E, \neg P (x)$ ». Réciproquement, s'il existe un tel $x$ , la proposition universelle ne peut pas être vraie.

Symétriquement, dire que « il existe $x$ dans $E$ tel que $P (x)$ » est fausse, c'est dire qu'aucun élément de $E$ ne convient, donc que tous les éléments de $E$ mettent $P$ en défaut : c'est « $\forall x \in E, \neg P (x)$ ». $□$

Méthode

Nier une proposition quantifiée.

Écrire la proposition complètement, avec tous ses quantificateurs, dans l'ordre, et l'ensemble de chacun.
Parcourir la proposition de gauche à droite et échanger chaque quantificateur : $\forall$ devient $\exists$ , $\exists$ devient $\forall$ . Les ensembles ne changent pas : la négation de « $\forall x \in R$ » est « $\exists x \in R$ », surtout pas « $\exists x \notin R$ ».
Nier uniquement la proposition finale, celle qui suit le dernier quantificateur, en appliquant s'il le faut les lois de De Morgan (« et » devient « ou ») ou la règle de négation d'une implication (voir la section suivante).
Relire l'énoncé obtenu en français et vérifier qu'il dit bien le contraire du premier.

Exemple

Quatre négations, détaillées.

a. Nions $(P_{1}) : \forall x \in R, x^{2} ⩾ 0$ .

Un seul quantificateur, qui devient $\exists$ ; la proposition finale « $x^{2} ⩾ 0$ » se nie en « $x^{2} < 0$ ». Donc

\neg (P_{1}) : \exists x \in R, x^{2} < 0

En français : « il existe un réel de carré strictement négatif ». Comme $(P_{1})$ est vraie, $\neg (P_{1})$ est fausse, ce qui est bien le cas.

b. Nions $(P_{2}) : \exists n \in N, n^{2} = 2$ .

Le $\exists$ devient $\forall$ et l'égalité se nie en une différence :

\neg (P_{2}) : \forall n \in N, n^{2} \neq 2

c. Nions $(P_{3}) : \exists M \in R, \forall n \in N, u_{n} ⩽ M$ (« la suite $(u_{n})$ est majorée »).

On parcourt de gauche à droite : $\exists$ devient $\forall$ , puis $\forall$ devient $\exists$ , et « $u_{n} ⩽ M$ » se nie en « $u_{n} > M$ » :

\neg (P_{3}) : \forall M \in R, \exists n \in N, u_{n} > M

En français : « quel que soit le réel $M$ que l'on se donne, on peut trouver un rang $n$ dont le terme dépasse $M$ ». C'est exactement le raisonnement que nous avons tenu plus haut pour la suite $u_{n} = n$ : on y a bien pris un $M$ quelconque, puis fabriqué un $n$ dépendant de $M$ .

d. Nions $(P_{4}) : \forall x \in R, (x ⩾ 3 et x ⩽ 5)$ .

Le $\forall$ devient $\exists$ , et la conjonction se nie par De Morgan :

\neg (P_{4}) : \exists x \in R, (x < 3 ou x > 5)

Ici $(P_{4})$ est évidemment fausse et sa négation évidemment vraie : $x = 0$ convient.

Remarque

Deux erreurs à ne jamais commettre.

Nier l'appartenance en même temps que le quantificateur. La négation de « $\forall x \in R, P (x)$ » est « $\exists x \in R, \neg P (x)$ », pas « $\exists x \notin R, \neg P (x)$ ». L'ensemble de travail ne change jamais.
Nier « en bloc » sans respecter l'ordre. La négation de « $\forall x, \exists y, P (x, y)$ » est « $\exists x, \forall y, \neg P (x, y)$ » : on garde l'ordre des variables et on retourne chaque quantificateur au passage.

Implication, réciproque, contraposée, équivalence

L'implication est le connecteur le plus important du cours, et aussi celui qui donne lieu au plus grand nombre de malentendus. Une proposition conditionnelle, c'est-à-dire un énoncé de la forme « si $P$ , alors $Q$ », est le format de la quasi-totalité des théorèmes que vous rencontrerez.

L'implication

Définition

Soient $P$ et $Q$ deux propositions. La proposition « $P ⟹ Q$ », lue « $P$ implique $Q$ » ou « si $P$ , alors $Q$ », est par définition la proposition « $\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.

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

$P$	$Q$	$\neg P$ ou $Q$	$P ⟹ Q$
V	V	V	V
V	F	F	F
F	V	V	V
F	F	V	V

Les deux dernières lignes surprennent toujours : une implication dont l'hypothèse est fausse est vraie, quelle que soit la conclusion. L'énoncé « si $2 + 2 = 5$ , alors je suis le roi d'Angleterre » est une implication vraie. Cela n'a rien d'absurde : une implication ne dit rien du tout tant que son hypothèse n'est pas réalisée. Elle promet seulement que si l'hypothèse est vraie, alors la conclusion l'est aussi. Une promesse dont la condition ne se réalise jamais n'est jamais trahie.

Remarque

Retenez la formulation opérationnelle : démontrer une implication $P ⟹ Q$ , c'est supposer $P$ vraie et en déduire $Q$ . Le cas où $P$ est fausse n'a pas à être examiné, il est automatiquement favorable. C'est la raison pour laquelle toute démonstration d'implication commence par « Supposons $P$ ».

Remarque

Une implication n'est pas un lien de causalité ni une chronologie. Écrire $P ⟹ Q$ ne signifie pas que $P$ « produit » $Q$ , ni que $P$ se passe avant $Q$ : c'est uniquement une information sur les valeurs de vérité. Par ailleurs, le symbole $⟹$ n'est pas un signe de ponctuation : on n'écrit pas « $x = 2 ⟹$ on remplace dans l'équation ». Un enchaînement de calculs se rédige avec les mots « donc », « d'où », « par conséquent ».

Condition nécessaire, condition suffisante

Définition

Soient $P$ et $Q$ deux propositions telles que l'implication $P ⟹ Q$ soit vraie. On dit alors que :

$P$ est une condition suffisante de $Q$ : il suffit que $P$ soit vraie pour que $Q$ le soit ;
$Q$ est une condition nécessaire de $P$ : il faut que $Q$ soit vraie pour que $P$ puisse l'être.

On lit aussi $P ⟹ Q$ sous les formes : « $P$ seulement si $Q$ », « pour que $P$ , il faut $Q$ », « pour que $Q$ , il suffit que $P$ ».

Exemple

Soit $n$ un entier naturel. L'implication « $n$ est un multiple de $4$ $⟹$ $n$ est pair » est vraie : si $n = 4 k$ , alors $n = 2 \times (2 k)$ est pair.

Être un multiple de $4$ est donc une condition suffisante pour être pair : il suffit de le savoir pour conclure.
Être pair est une condition nécessaire pour être un multiple de $4$ : un nombre impair n'a aucune chance d'être multiple de $4$ .

Et l'on voit bien que « nécessaire » n'est pas « suffisant » : $6$ est pair sans être multiple de $4$ .

Remarque

« Il faut » et « il suffit » sont les deux pièges de vocabulaire les plus rentables des sujets de concours, parce que le français courant les confond volontiers. Un moyen mnémotechnique fiable : dans « $P ⟹ Q$ », la flèche va du suffisant vers le nécessaire. La condition suffisante est celle qui est à la source de la flèche : elle suffit à déclencher la conclusion. La condition nécessaire est celle qui est à la pointe : on ne peut pas s'en passer.

La contraposée

Définition

Soient $P$ et $Q$ deux propositions. On appelle contraposée de l'implication $P ⟹ Q$ l'implication

\neg Q ⟹ \neg P

Propriété

Une implication et sa contraposée ont la même valeur de vérité : les propositions $P ⟹ Q$ et $\neg Q ⟹ \neg P$ sont vraies dans exactement les mêmes cas.

Démonstration. Écrivons la table de vérité en faisant apparaître les deux implications.

$P$	$Q$	$P ⟹ Q$	$\neg Q$	$\neg P$	$\neg Q ⟹ \neg P$
V	V	V	F	F	V
V	F	F	V	F	F
F	V	V	F	V	V
F	F	V	V	V	V

Vérifions la deuxième ligne, la seule où quelque chose est faux. $P$ est vraie et $Q$ est fausse, donc $P ⟹ Q$ est fausse. Par ailleurs $\neg Q$ est vraie et $\neg P$ est fausse, donc l'implication $\neg Q ⟹ \neg P$ a une hypothèse vraie et une conclusion fausse : elle est fausse elle aussi.

Les colonnes 3 et 6 valent toutes les deux V, F, V, V : elles coïncident ligne à ligne. Les deux implications ont donc bien la même valeur de vérité. $□$

Cette propriété n'est pas une curiosité : c'est le fondement du raisonnement par contraposée, que nous exploiterons dans la section suivante. Elle dit qu'on a le droit de remplacer l'énoncé à démontrer par un autre, parfois beaucoup plus commode.

Exemple

Soit $n$ un entier naturel. Les deux implications suivantes disent exactement la même chose :

« si $n^{2}$ est pair, alors $n$ est pair » ;
« si $n$ est impair, alors $n^{2}$ est impair » (contraposée : on a nié les deux membres et retourné la flèche).

La seconde est facile à démontrer directement, la première ne l'est pas du tout. C'est tout l'intérêt de la manœuvre.

La négation d'une implication

Propriété

Soient $P$ et $Q$ deux propositions. La négation de l'implication $P ⟹ Q$ est la proposition

P et \neg Q

Autrement dit : nier une implication, ce n'est pas obtenir une autre implication. C'est affirmer que l'hypothèse est réalisée et que, malgré cela, la conclusion ne l'est pas.

Démonstration. Par définition, $P ⟹ Q$ est la proposition « $\neg P$ ou $Q$ ». Sa négation est donc $\neg (\neg P ou Q)$ , qui, d'après la loi de De Morgan appliquée à la disjonction, a la même valeur de vérité que « $\neg (\neg P)$ et $\neg Q$ », c'est-à-dire « $P$ et $\neg Q$ » par double négation.

On peut aussi le lire directement sur la table de vérité : l'implication $P ⟹ Q$ est fausse dans la seule ligne où $P$ est vraie et $Q$ est fausse, c'est-à-dire dans le seul cas où « $P$ et $\neg Q$ » est vraie. Les deux propositions $\neg (P ⟹ Q)$ et « $P$ et $\neg Q$ » sont donc vraies exactement dans le même cas. $□$

Exemple

a. La négation de « si $x > 2$ , alors $x^{2} > 4$ » est « $x > 2$ et $x^{2} ⩽ 4$ ».

En tenant compte de la quantification implicite, la négation complète de $\forall x \in R, (x > 2 ⟹ x^{2} > 4)$ est

\exists x \in R, (x > 2 et x^{2} ⩽ 4)

C'est très exactement la description d'un contre-exemple : un réel qui vérifie l'hypothèse sans vérifier la conclusion. Ici l'implication est vraie, donc un tel réel n'existe pas.

b. La négation de « si une entreprise est rentable, alors elle est solvable » est : « une entreprise est rentable et pourtant elle n'est pas solvable ». Ce n'est pas « si une entreprise est rentable, alors elle n'est pas solvable », et ce n'est pas non plus « si une entreprise n'est pas rentable, alors elle n'est pas solvable ». La négation d'un énoncé conditionnel est un énoncé non conditionnel.

La réciproque

Définition

Soient $P$ et $Q$ deux propositions. On appelle réciproque de l'implication $P ⟹ Q$ l'implication

Q ⟹ P

Propriété

Une implication et sa réciproque n'ont aucun lien logique : chacune des quatre combinaisons est possible. En particulier, savoir que $P ⟹ Q$ est vraie ne renseigne en rien sur $Q ⟹ P$ .

Justification par des exemples. Il suffit d'exhiber une situation pour chaque combinaison. Soit $n$ un entier naturel et $x$ un réel.

$P ⟹ Q$ vraie et $Q ⟹ P$ fausse : avec $P$ = « $n$ est multiple de $4$ » et $Q$ = « $n$ est pair », l'implication est vraie et la réciproque est fausse ( $n = 6$ est pair sans être multiple de $4$ ).
$P ⟹ Q$ fausse et $Q ⟹ P$ vraie : le même couple, lu dans l'autre sens, c'est-à-dire $P$ = « $n$ est pair » et $Q$ = « $n$ est multiple de $4$ ».
Les deux vraies : avec $P$ = « $x ⩾ 0$ » et $Q$ = « $x + 1 ⩾ 1$ », l'implication et sa réciproque sont toutes les deux vraies (il suffit d'ajouter ou de retrancher $1$ ).
Les deux fausses : avec $P$ = « $x ⩾ 0$ » et $Q$ = « $x ⩽ 0$ », l'implication est fausse ( $x = 1$ vérifie $P$ mais pas $Q$ ) et la réciproque l'est aussi ( $x = - 1$ vérifie $Q$ mais pas $P$ ). $□$

Remarque

C'est l'une des fautes les plus coûteuses en copie : utiliser la réciproque d'un théorème du cours comme si elle allait de soi. Un théorème s'énonce dans un sens. Si l'on veut l'autre sens, il faut soit citer un théorème qui l'affirme, soit le démontrer.

Cas concret vu au lycée : « si une fonction est dérivable en $a$ , alors elle est continue en $a$ » est un théorème, et sa réciproque est fausse. Autre cas concret, que vous rencontrerez dès le chapitre sur les suites : « si une suite converge, alors elle est bornée » est un théorème, et sa réciproque est fausse elle aussi.

L'équivalence

Définition

Soient $P$ et $Q$ deux propositions. La proposition « $P ⟺ Q$ », lue « $P$ équivaut à $Q$ » ou « $P$ si et seulement si $Q$ », est la conjonction des deux implications :

(P ⟹ Q) et (Q ⟹ P)

Elle est donc vraie exactement lorsque $P$ et $Q$ ont la même valeur de vérité. On dit alors que $P$ est une condition nécessaire et suffisante de $Q$ (et réciproquement).

$P$	$Q$	$P ⟹ Q$	$Q ⟹ P$	$P ⟺ Q$
V	V	V	V	V
V	F	F	V	F
F	V	V	F	F
F	F	V	V	V

Méthode

Démontrer une équivalence. Deux rédactions sont acceptables ; la première est presque toujours la plus sûre.

Rédaction en deux temps (recommandée). On démontre séparément les deux implications, en annonçant clairement chacune :

Sens direct. Supposons $P$ . ... Donc $Q$ .

Sens réciproque. Supposons $Q$ . ... Donc $P$ .

Conclusion. Les deux implications sont établies, donc $P ⟺ Q$ .

Rédaction par équivalences successives. On enchaîne les transformations en écrivant $⟺$ à chaque étape :

x^{2} - 5 x + 6 = 0 ⟺ (x - 2) (x - 3) = 0 ⟺ x = 2 ou x = 3

Cette rédaction n'est licite que si chaque étape est réellement une équivalence, ce qui doit être vérifié à chaque ligne. Élever au carré, multiplier par une quantité qui peut être nulle, composer par une fonction non injective : autant d'opérations qui ne sont pas des équivalences. Au moindre doute, revenir à la rédaction en deux temps.

Exemple

Une chaîne d'équivalences valide. Soit $x \in R$ . Résolvons $\frac{2 x + 1}{x - 3} = 5$ pour $x \neq 3$ .

\begin{aligned} \frac{2 x + 1}{x - 3} = 5 & ⟺ 2 x + 1 = 5 (x - 3) \\ ⟺ 2 x + 1 = 5 x - 15 \\ ⟺ 16 = 3 x \\ ⟺ x = \frac{16}{3} \end{aligned}

La première étape est bien une équivalence parce que l'on a multiplié par $x - 3$ , qui est non nul par hypothèse. La valeur trouvée vérifie $x \neq 3$ , elle est donc bien solution.

Une chaîne qui n'en est pas une. Soit $x \in R$ . On a l'implication

x = - 2 ⟹ x^{2} = 4

mais l'écrire avec $⟺$ serait faux, puisque $x = 2$ vérifie aussi $x^{2} = 4$ . Élever au carré n'est pas une équivalence. C'est la raison pour laquelle, après avoir élevé au carré dans la résolution d'une équation, on est obligé de vérifier les solutions obtenues.

Les modes de raisonnement

Nous disposons maintenant du vocabulaire nécessaire pour décrire les grandes façons de conduire une démonstration. Il n'y en a pas trente-six, et le plus difficile n'est pas de les connaître : c'est de reconnaître, devant un énoncé donné, laquelle est la bonne. À la fin de cette section, une règle simple pourra vous guider : regardez la forme logique de ce qu'on vous demande de montrer, elle dicte presque toujours la première ligne de la rédaction.

Le raisonnement direct

C'est le mode par défaut : pour établir $P ⟹ Q$ , on suppose $P$ et on enchaîne les déductions jusqu'à $Q$ .

Méthode

Raisonnement direct.

Écrire « Supposons $P$ » (ou « Soit $x$ tel que ... » si l'énoncé est quantifié).
Enchaîner des déductions, en justifiant chaque étape par une définition, une propriété du cours ou un calcul.
Terminer par « ... donc $Q$ », puis conclure.

Exemple

Montrons que pour tout réel $x$ , $x^{2} - 4 x + 5 > 0$ .

Soit $x \in R$ . Mettons l'expression sous forme canonique :

x^{2} - 4 x + 5 = (x^{2} - 4 x + 4) + 1 = (x - 2)^{2} + 1

Or $(x - 2)^{2} ⩾ 0$ , car le carré d'un réel est positif. Donc $(x - 2)^{2} + 1 ⩾ 1 > 0$ .

Conclusion : pour tout réel $x$ , $x^{2} - 4 x + 5 > 0$ . $□$

Notez la structure : on part d'un $x$ quelconque (« Soit $x \in R$ »), on n'utilise rien d'autre que le fait qu'il est réel, et la conclusion vaut donc pour tous les réels.

Exemple

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

Supposons $n$ pair. Par définition, il existe un entier $k$ tel que $n = 2 k$ . Alors

n^{2} = (2 k)^{2} = 4 k^{2} = 2 \times (2 k^{2})

Comme $2 k^{2}$ est un entier, $n^{2}$ s'écrit comme le double d'un entier : $n^{2}$ est pair. $□$

Observez le procédé, qui est systématique : on traduit l'hypothèse par sa définition (« pair » devient « de la forme $2 k$ »), on calcule, puis on relit le résultat à travers la définition de la conclusion (« de la forme $2 \times$ entier » redevient « pair »).

Le contre-exemple

Propriété

Pour démontrer qu'une proposition universelle

\forall x \in E, P (x)

est fausse, il suffit d'exhiber un seul élément $x_{0}$ de $E$ pour lequel $P (x_{0})$ est fausse. Un tel élément s'appelle un contre-exemple.

Justification. C'est exactement la règle de négation d'une proposition universelle : la négation de « $\forall x \in E, P (x)$ » est « $\exists x \in E, \neg P (x)$ ». Démontrer une proposition existentielle, c'est en exhiber un témoin. $□$

Méthode

Réfuter une proposition universelle par contre-exemple.

Écrire la négation de la proposition pour savoir ce qu'on cherche : un $x$ dans l'ensemble, tel que la propriété soit en défaut.
Chercher le candidat dans les cas « fragiles » : $0$ , $1$ , les nombres négatifs, les valeurs entre $0$ et $1$ , les cas où un dénominateur s'annule, les petites valeurs de $n$ .
Écrire le candidat explicitement et vérifier par le calcul que la propriété est bien fausse pour lui. Un contre-exemple non vérifié ne vaut rien.
Conclure : « la proposition est donc fausse ».

Un seul contre-exemple suffit ; il est inutile d'en donner trois. En revanche, un contre-exemple ne démontre jamais qu'une proposition est vraie.

Exemple

a. La proposition « $\forall x \in R, x^{2} ⩾ x$ » est fausse.

En effet, prenons $x = \frac{1}{2}$ . Alors $x^{2} = \frac{1}{4}$ et $\frac{1}{4} < \frac{1}{2}$ , donc $x^{2} ⩾ x$ est fausse pour cette valeur. La proposition universelle est donc fausse. $□$

Commentaire. On aurait pu chercher longtemps parmi les entiers sans rien trouver : pour $x$ entier, $x^{2} ⩾ x$ est toujours vraie. Le contre-exemple se cache dans l'intervalle $] 0, 1 [$ , et c'est justement là qu'il fallait aller regarder.

b. La proposition « $\forall x \in R, \sqrt{x^{2}} = x$ » est fausse : pour $x = - 3$ , on a $\sqrt{(- 3)^{2}} = \sqrt{9} = 3 \neq - 3$ . La formule correcte est $\sqrt{x^{2}} = ∣ x ∣$ .

c. La proposition « $\forall n \in N, n^{2} + n + 1$ est impair » est vraie, elle. On ne cherchera donc pas de contre-exemple : $n^{2} + n = n (n + 1)$ est un produit de deux entiers consécutifs, donc pair, et son successeur est impair. La leçon est qu'avant de chercher un contre-exemple, il faut se demander sérieusement si l'énoncé n'est pas vrai.

La disjonction de cas

Méthode

Raisonnement par disjonction de cas. Pour démontrer une proposition portant sur un objet $x$ , on découpe l'ensemble des situations possibles en plusieurs cas, et on traite chacun d'eux séparément.

Annoncer le découpage : « Distinguons deux cas. » ou « Selon le signe de $x$ , deux cas se présentent. »
Vérifier que les cas recouvrent toutes les situations : c'est le point que les correcteurs vérifient en premier. Un découpage qui oublie un cas ne démontre rien.
Traiter chaque cas complètement, en commençant par « Premier cas : supposons ... ».
Conclure globalement : « Dans tous les cas, ... ». La conclusion doit être la même dans chaque branche.

Les découpages les plus fréquents : selon la parité d'un entier, selon le signe d'un réel, selon la position par rapport à une valeur charnière, selon que l'on est dans un ensemble ou dans son complémentaire.

Exemple

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

Soit $n \in N$ . Distinguons deux cas selon la parité de $n$ .

Premier cas : $n$ est pair. Il existe alors un entier $k$ tel que $n = 2 k$ . Donc

n (n + 1) = 2 k (n + 1) = 2 \times [k (n + 1)]

et $k (n + 1)$ est un entier : $n (n + 1)$ est pair.

Second cas : $n$ est impair. Il existe alors un entier $k$ tel que $n = 2 k + 1$ . Donc $n + 1 = 2 k + 2 = 2 (k + 1)$ , d'où

n (n + 1) = n \times 2 (k + 1) = 2 \times [n (k + 1)]

et $n (k + 1)$ est un entier : $n (n + 1)$ est encore pair.

Conclusion : tout entier étant pair ou impair, les deux cas couvrent bien toutes les situations, et dans les deux cas $n (n + 1)$ est pair. $□$

Contrôle : $n = 5$ donne $5 \times 6 = 30$ , effectivement pair.

Exemple

Un exemple avec la valeur absolue. Rappelons la définition : pour $x \in R$ ,

∣ x ∣ = {\begin{cases} x & si x ⩾ 0 \\ - x & si x < 0 \end{cases}

Étape 1. Montrons que pour tout réel $x$ , on a $x ⩽ ∣ x ∣$ et $- x ⩽ ∣ x ∣$ .

Soit $x \in R$ . Deux cas.

Premier cas : $x ⩾ 0$ . Alors $∣ x ∣ = x$ , donc $x ⩽ ∣ x ∣$ est vraie (c'est une égalité). Par ailleurs $- x ⩽ 0 ⩽ x = ∣ x ∣$ , donc $- x ⩽ ∣ x ∣$ .

Second cas : $x < 0$ . Alors $∣ x ∣ = - x$ , donc $- x ⩽ ∣ x ∣$ est vraie (c'est une égalité). Par ailleurs $x < 0 < - x = ∣ x ∣$ , donc $x ⩽ ∣ x ∣$ .

Dans les deux cas, les deux inégalités sont vraies.

Étape 2. Montrons l'inégalité triangulaire : pour tous réels $x$ et $y$ , $∣ x + y ∣ ⩽ ∣ x ∣ + ∣ y ∣$ .

Soient $x$ et $y$ deux réels. Distinguons deux cas selon le signe de $x + y$ .

Premier cas : $x + y ⩾ 0$ . Alors $∣ x + y ∣ = x + y$ . Or $x ⩽ ∣ x ∣$ et $y ⩽ ∣ y ∣$ d'après l'étape 1, donc en additionnant ces deux inégalités de même sens :

∣ x + y ∣ = x + y ⩽ ∣ x ∣ + ∣ y ∣

Second cas : $x + y < 0$ . Alors $∣ x + y ∣ = - (x + y) = (- x) + (- y)$ . Or $- x ⩽ ∣ x ∣$ et $- y ⩽ ∣ y ∣$ d'après l'étape 1, donc en additionnant :

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

Conclusion : dans tous les cas, $∣ x + y ∣ ⩽ ∣ x ∣ + ∣ y ∣$ . $□$

Contrôle : pour $x = 3$ et $y = - 5$ , on a $∣ x + y ∣ = ∣ - 2 ∣ = 2$ et $∣ x ∣ + ∣ y ∣ = 3 + 5 = 8$ . L'inégalité est bien vérifiée, et largement.

Le raisonnement par contraposée

Méthode

Raisonnement par contraposée. Pour démontrer l'implication $P ⟹ Q$ , on démontre à la place l'implication $\neg Q ⟹ \neg P$ , qui a la même valeur de vérité.

Annoncer le procédé : « Raisonnons par contraposée. » Le correcteur doit savoir ce que vous faites.
Écrire la contraposée, proprement : « Montrons que si $\neg Q$ , alors $\neg P$ . » Attention à ne pas se tromper de sens.
Démontrer cette implication par un raisonnement direct.
Conclure : « Par contraposition, l'implication $P ⟹ Q$ est donc vraie. »

Quand y penser ? Quand l'hypothèse $P$ est difficile à exploiter mais que sa négation $\neg P$ est facile, et surtout quand la conclusion $Q$ est de la forme « $x$ n'est pas ... », « $x \neq . . .$ », « $x$ n'appartient pas à ... ». Une conclusion négative devient une hypothèse positive après contraposition, et une hypothèse est toujours plus facile à utiliser qu'une conclusion.

Exemple

Montrons que, pour tout entier naturel $n$ , si $n^{2}$ est pair, alors $n$ est pair.

Raisonnons par contraposée. La contraposée de cette implication s'obtient en niant les deux membres et en retournant la flèche : il s'agit de montrer que 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$ . Alors

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, $n^{2}$ s'écrit sous la forme $2 m + 1$ avec $m$ entier : $n^{2}$ est impair.

Conclusion : la contraposée est démontrée, donc l'implication initiale est vraie : pour tout entier naturel $n$ , si $n^{2}$ est pair, alors $n$ est pair. $□$

Pourquoi la contraposée ? L'hypothèse directe « $n^{2}$ est pair » donne $n^{2} = 2 k$ , dont on ne sait rien tirer sur $n$ sans outils d'arithmétique. L'hypothèse contraposée « $n$ est impair » donne au contraire $n = 2 k + 1$ , qu'il suffit d'élever au carré. Le même énoncé devient un calcul de trois lignes.

Remarque

Ne confondez pas la contraposée (qui est équivalente à l'implication de départ) avec la réciproque (qui n'a aucun lien avec elle). Sur l'exemple précédent :

implication : « $n^{2}$ pair $⟹$ $n$ pair » (vraie) ;
contraposée : « $n$ impair $⟹$ $n^{2}$ impair » (vraie, c'est la même chose) ;
réciproque : « $n$ pair $⟹$ $n^{2}$ pair » (vraie aussi ici, mais cela demande une autre démonstration, faite plus haut).

Le fait que la réciproque soit vraie ici est un accident heureux, pas une conséquence.

Le raisonnement par l'absurde

Méthode

Raisonnement par l'absurde. Pour démontrer qu'une proposition $R$ est vraie, on suppose qu'elle est fausse et on aboutit à une contradiction, c'est-à-dire à une proposition manifestement fausse ou à deux affirmations incompatibles.

Annoncer : « Raisonnons par l'absurde. »
Supposer la négation de ce qu'on veut montrer, en l'écrivant correctement (c'est ici que servent les règles de négation).
Raisonner normalement jusqu'à obtenir une contradiction explicite, que l'on nomme : « ce qui contredit l'hypothèse de départ », « or $0 \neq 1$ », « $n$ serait à la fois pair et impair ».
Conclure : « L'hypothèse de départ est donc absurde, et $R$ est vraie. »

Quand y penser ? Quand on veut démontrer une non-existence (« il n'existe pas de rationnel dont le carré vaut $2$ »), une irrationalité, une unicité, ou un énoncé du type « $x$ n'est pas ... » dont on ne voit pas par quel bout le prendre. Supposer le contraire fournit alors un objet concret à manipuler, ce qui est toujours plus confortable que de partir de rien.

Exemple

Le nombre $\sqrt{2}$ est irrationnel.

Rappelons d'abord ce qu'il faut montrer : $\sqrt{2}$ ne peut pas s'écrire comme quotient de deux entiers. Nous utiliserons le résultat démontré plus haut par contraposée : si le carré d'un entier est pair, cet entier est pair.

Raisonnons par l'absurde et supposons que $\sqrt{2}$ soit rationnel. Il existe alors deux entiers naturels non nuls $p$ et $q$ tels que

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

Parmi toutes les écritures possibles, on peut choisir celle-ci de sorte que $p$ et $q$ ne soient pas tous les deux pairs. En effet, s'ils l'étaient, on pourrait simplifier la fraction par $2$ ; ce procédé fait strictement diminuer le numérateur, qui est un entier naturel non nul, donc il ne peut pas se répéter indéfiniment. Au bout d'un nombre fini de simplifications, on obtient une écriture dans laquelle $p$ et $q$ ne sont pas tous les deux pairs. Fixons une telle écriture.

En élevant au carré l'égalité $\sqrt{2} = \frac{p}{q}$ , on obtient $2 = \frac{p^{2}}{q^{2}}$ , c'est-à-dire, en multipliant par $q^{2}$ qui est non nul,

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

Ainsi $p^{2}$ est le double de l'entier $q^{2}$ : $p^{2}$ est pair. D'après le résultat rappelé ci-dessus, $p$ est donc pair. Il existe par conséquent un entier $p^{'}$ tel que $p = 2 p^{'}$ . En reportant dans l'égalité précédente :

(2 p^{'})^{2} = 2 q^{2} soit 4 p^{' 2} = 2 q^{2} soit encore q^{2} = 2 p^{' 2}

Ainsi $q^{2}$ est le double de l'entier $p^{' 2}$ : $q^{2}$ est pair, donc, par le même résultat, $q$ est pair.

Nous obtenons donc que $p$ et $q$ sont tous les deux pairs, ce qui contredit le choix que nous avions fait de l'écriture $\frac{p}{q}$ .

Conclusion : l'hypothèse « $\sqrt{2}$ est rationnel » conduit à une contradiction. Elle est donc fausse : $\sqrt{2}$ est irrationnel. $□$

Remarque de méthode. Cette démonstration est un modèle du genre et mérite d'être sue. Elle combine les deux raisonnements de la section : une contraposée pour le lemme sur la parité, une absurdité pour le résultat principal. Notez aussi la précaution prise dès le début : on ne se contente pas d'écrire $\sqrt{2} = p / q$ , on impose une condition sur l'écriture ( $p$ et $q$ pas tous les deux pairs), et c'est précisément cette condition qui sera contredite à la fin. Sans elle, on n'obtiendrait aucune contradiction, seulement le fait que $p$ et $q$ sont pairs, ce qui n'a rien d'absurde en soi.

Exemple

Un second exemple, plus court. Montrons qu'il n'existe pas de plus grand entier naturel.

Raisonnons par l'absurde et supposons qu'il existe un entier naturel $N$ tel que, pour tout $n \in N$ , $n ⩽ N$ . Considérons l'entier $N + 1$ . C'est un entier naturel, donc l'hypothèse s'applique à lui : $N + 1 ⩽ N$ . En soustrayant $N$ des deux côtés, on obtient $1 ⩽ 0$ , ce qui est faux.

Conclusion : l'hypothèse est absurde, il n'existe pas de plus grand entier naturel. $□$

Remarque

Absurde ou contraposée ? Les deux se ressemblent, puisque tous deux commencent par nier quelque chose, et les étudiants passent souvent de l'un à l'autre sans s'en rendre compte. La différence est nette :

par contraposée, on suppose $\neg Q$ et on doit aboutir à $\neg P$ , une conclusion fixée d'avance ;
par l'absurde, on suppose $P$ et $\neg Q$ , et on cherche une contradiction quelconque, on ne sait pas laquelle à l'avance.

Le raisonnement par l'absurde est donc plus souple, mais aussi plus dangereux : une démonstration par l'absurde qui n'aboutit à aucune contradiction claire ne démontre rien. Quand la contraposée suffit, on la préfère : elle est plus lisible.

Démontrer une inclusion, démontrer une égalité d'ensembles

Ces deux trames seront utilisées en permanence dans la section consacrée aux ensembles ; nous les énonçons dès maintenant, car ce sont des modes de raisonnement avant d'être des résultats.

Méthode

Démontrer une inclusion $A \subset B$ .

La définition de l'inclusion est : $\forall x, (x \in A ⟹ x \in B)$ . La rédaction en découle mécaniquement.

Soit $x \in A$ . [ ... on utilise la définition de $A$ ... ] Donc $x \in B$ .

Comme $x$ était quelconque dans $A$ , on a bien $A \subset B$ .

On part toujours d'un élément de l'ensemble de gauche, jamais de l'ensemble de droite.

Méthode

Démontrer une égalité d'ensembles $A = B$ par double inclusion.

Montrons que $A \subset B$ . Soit $x \in A$ . ... Donc $x \in B$ .

Montrons que $B \subset A$ . Soit $x \in B$ . ... Donc $x \in A$ .

Conclusion. Par double inclusion, $A = B$ .

C'est la méthode de référence : elle marche toujours. Une variante plus rapide consiste à écrire une chaîne d'équivalences :

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

Elle est correcte à condition que chaque étape soit une véritable équivalence, et elle est particulièrement adaptée aux identités ensemblistes générales (distributivité, lois de De Morgan), où les manipulations sont purement logiques. Dans un cas concret où les ensembles sont décrits par des conditions différentes, la double inclusion reste plus prudente.

Le raisonnement par récurrence

Voici le mode de raisonnement le plus caractéristique du travail sur les entiers, et celui qui sera le plus souvent exigé de vous : il apparaît dans presque tous les sujets de concours, dans l'étude des suites, dans les probabilités, dans le calcul matriciel. Nous ne ferons aucune théorie à son sujet : nous allons le présenter comme un outil, fixer une trame de rédaction, et l'employer sur des exemples jusqu'à ce que le réflexe soit acquis.

Le principe et la trame de rédaction

Propriété

Principe de récurrence. Soit $n_{0}$ un entier naturel et, pour chaque entier $n ⩾ n_{0}$ , une proposition $H_{n}$ . Si les deux conditions suivantes sont réunies :

initialisation : la proposition $H_{n_{0}}$ est vraie ;
hérédité : pour tout entier $n ⩾ n_{0}$ , l'implication $H_{n} ⟹ H_{n + 1}$ est vraie ;

alors la proposition $H_{n}$ est vraie pour tout entier $n ⩾ n_{0}$ .

Ce principe est admis : il exprime une propriété fondamentale de l'ensemble $N$ des entiers naturels.

Remarque

L'image de l'échelle est la bonne. L'initialisation dit : « je sais poser le pied sur le barreau numéro $n_{0}$ ». L'hérédité dit : « depuis n'importe quel barreau, je sais monter au suivant ». Les deux ensemble permettent d'atteindre tous les barreaux au-dessus de $n_{0}$ , et aucun en dessous.

Chacune des deux conditions est indispensable, et pour des raisons différentes. Sans initialisation, on sait monter d'un barreau à l'autre mais on n'est jamais monté sur l'échelle. Sans hérédité, on est sur le premier barreau et on y reste.

Méthode

La trame de rédaction en quatre temps. Elle ne se négocie pas : un correcteur attend ces quatre moments, dans cet ordre, et retire des points si l'un manque.

1. Énoncé de la propriété. On écrit explicitement ce que l'on veut démontrer, sous la forme d'une proposition dépendant de $n$ :

Pour tout entier $n ⩾ n_{0}$ , notons $H_{n}$ la proposition : « ... ».

Montrons par récurrence que $H_{n}$ est vraie pour tout $n ⩾ n_{0}$ .

La proposition $H_{n}$ doit être une phrase complète, contenant la variable $n$ , et ne contenant pas le mot « pour tout $n$ » (c'est l'erreur classique).

2. Initialisation. On vérifie $H_{n_{0}}$ par un calcul explicite, en écrivant séparément les deux membres :

Initialisation. Pour $n = n_{0}$ : le membre de gauche vaut ..., le membre de droite vaut ..., ils sont égaux. Donc $H_{n_{0}}$ est vraie.

3. Hérédité. C'est le cœur de la démonstration :

Hérédité. Soit $n ⩾ n_{0}$ un entier fixé. Supposons $H_{n}$ vraie, c'est-à-dire [réécrire l'hypothèse en toutes lettres]. Montrons que $H_{n + 1}$ est vraie, c'est-à-dire que [réécrire ce qu'il faut obtenir].

[calcul, en signalant l'endroit exact où l'hypothèse de récurrence est utilisée]

Donc $H_{n + 1}$ est vraie.

4. Conclusion.

Conclusion. La propriété est vraie au rang $n_{0}$ et elle est héréditaire. D'après le principe de récurrence, $H_{n}$ est vraie pour tout entier $n ⩾ n_{0}$ .

Remarque

Deux conseils de rédaction qui font gagner des points à chaque copie.

Écrire ce qu'on veut obtenir au début de l'hérédité (« montrons que ... »). Cela évite de rédiger dans le vide, et cela donne une cible : la plupart des hérédités se font en partant du membre le plus compliqué de $H_{n + 1}$ et en y faisant apparaître le membre correspondant de $H_{n}$ .
Signaler l'usage de l'hypothèse de récurrence au moment où on s'en sert : « par hypothèse de récurrence, ... ». Une hérédité où l'hypothèse n'est jamais utilisée est presque toujours le signe d'une erreur.

Un premier exemple entièrement rédigé

Nous allons démontrer la formule qui donne la somme des $n$ premiers entiers. La notation $\sum$ sera définie précisément dans la section suivante ; pour l'instant, $\sum_{k = 1}^{n} k$ est simplement une abréviation de $1 + 2 + \dots + n$ .

Exemple

Montrons que pour tout entier $n ⩾ 1$ ,

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

Énoncé de la propriété. Pour tout entier $n ⩾ 1$ , notons $H_{n}$ la proposition :

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

Montrons par récurrence que $H_{n}$ est vraie pour tout entier $n ⩾ 1$ .

Initialisation. Pour $n = 1$ , le membre de gauche vaut $\sum_{k = 1}^{1} k = 1$ , et le membre de droite vaut $\frac{1 \times (1 + 1)}{2} = \frac{2}{2} = 1$ . Les deux membres sont égaux, donc $H_{1}$ est vraie.

Hérédité. Soit $n ⩾ 1$ un entier fixé. Supposons $H_{n}$ vraie, c'est-à-dire

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

Montrons que $H_{n + 1}$ est vraie, c'est-à-dire que $\sum_{k = 1}^{n + 1} k = \frac{(n + 1) (n + 2)}{2}$ .

Partons du membre de gauche de $H_{n + 1}$ . En isolant le dernier terme de la somme, qui correspond à $k = 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 \\ = \frac{n (n + 1)}{2} + \frac{2 (n + 1)}{2} \\ = \frac{(n + 1) (n + 2)}{2} \end{aligned}

où l'on a mis $(n + 1)$ en facteur à la dernière ligne. On reconnaît le membre de droite de $H_{n + 1}$ , puisque $(n + 1) + 1 = n + 2$ . Donc $H_{n + 1}$ est vraie.

Conclusion. La propriété est vraie au rang $1$ et elle est héréditaire. D'après le principe de récurrence, pour tout entier $n ⩾ 1$ ,

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

Contrôle pour $n = 4$ : la somme vaut $1 + 2 + 3 + 4 = 10$ , et la formule donne $\frac{4 \times 5}{2} = 10$ . Les deux coïncident.

Remarque

Prenez l'habitude de faire ce contrôle numérique sur une petite valeur, au brouillon d'abord, sur la copie ensuite si c'est rapide. Il ne remplace évidemment pas la démonstration, mais il détecte en dix secondes une formule mal recopiée, un facteur $2$ oublié ou un décalage d'indice. La quasi-totalité des erreurs de récurrence se voient sur $n = 1$ , $n = 2$ ou $n = 3$ .

Un exemple avec une inégalité : l'inégalité de Bernoulli

Les récurrences portant sur des inégalités demandent une vigilance supplémentaire : à chaque fois qu'on multiplie une inégalité par un nombre, il faut avoir vérifié le signe de ce nombre.

Propriété

Inégalité de Bernoulli. Pour tout réel $x ⩾ - 1$ et tout entier naturel $n$ ,

(1 + x)^{n} ⩾ 1 + n x

Exemple

Démonstration rédigée.

Soit $x$ un réel fixé tel que $x ⩾ - 1$ . Pour tout entier $n \in N$ , notons $H_{n}$ la proposition :

H_{n} : (1 + x)^{n} ⩾ 1 + n x

Montrons par récurrence que $H_{n}$ est vraie pour tout entier $n ⩾ 0$ .

Initialisation. Pour $n = 0$ , le membre de gauche vaut $(1 + x)^{0} = 1$ , et le membre de droite vaut $1 + 0 \times x = 1$ . On a bien $1 ⩾ 1$ , donc $H_{0}$ est vraie.

Hérédité. Soit $n ⩾ 0$ un entier fixé. Supposons $H_{n}$ vraie, c'est-à-dire $(1 + x)^{n} ⩾ 1 + n x$ . Montrons que $(1 + x)^{n + 1} ⩾ 1 + (n + 1) x$ .

Comme $x ⩾ - 1$ , on a $1 + x ⩾ 0$ . On peut donc multiplier les deux membres de l'hypothèse de récurrence par $1 + x$ sans changer le sens de l'inégalité :

(1 + x)^{n} \times (1 + x) ⩾ (1 + n x) (1 + x)

Le membre de gauche vaut $(1 + x)^{n + 1}$ . Développons le membre de droite :

(1 + n x) (1 + x) = 1 + x + n x + n x^{2} = 1 + (n + 1) x + n x^{2}

Nous avons donc établi $(1 + x)^{n + 1} ⩾ 1 + (n + 1) x + n x^{2}$ . Or $n ⩾ 0$ et $x^{2} ⩾ 0$ , donc $n x^{2} ⩾ 0$ , et par conséquent

1 + (n + 1) x + n x^{2} ⩾ 1 + (n + 1) x

Par transitivité de l'inégalité, $(1 + x)^{n + 1} ⩾ 1 + (n + 1) x$ , c'est-à-dire $H_{n + 1}$ .

Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire. D'après le principe de récurrence, pour tout entier naturel $n$ et tout réel $x ⩾ - 1$ , $(1 + x)^{n} ⩾ 1 + n x$ . $□$

Contrôle : pour $x = 0,1$ et $n = 3$ , le membre de gauche vaut ${1,1}^{3} = 1,331$ et le membre de droite vaut $1 + 0,3 = 1,3$ . L'inégalité est vérifiée.

Remarque

Trois points de vigilance sur cette démonstration, qui valent pour toutes les récurrences avec inégalités.

L'hypothèse $x ⩾ - 1$ sert, et à un endroit précis : c'est elle qui garantit $1 + x ⩾ 0$ et autorise la multiplication sans changer le sens de l'inégalité. Elle n'est pas décorative : pour $x = - 3$ et $n = 5$ , on a $(1 + x)^{5} = (- 2)^{5} = - 32$ tandis que $1 + 5 x = - 14$ , et l'inégalité $- 32 ⩾ - 14$ est fausse. L'énoncé tombe donc en défaut dès que l'on sort de $x ⩾ - 1$ .
Le réel $x$ est fixé avant la récurrence, et il ne bouge plus. La récurrence porte sur $n$ seulement.
La dernière étape est une majoration supplémentaire : on n'obtient pas directement $H_{n + 1}$ , on obtient mieux, puis on relâche. C'est extrêmement fréquent : dans une récurrence sur une inégalité, on démontre presque toujours un peu plus que ce qui est demandé, avant de conclure par transitivité.

Les pièges classiques

Remarque

Piège n°1 : oublier l'initialisation. C'est l'erreur la plus grave, parce que la démonstration paraît complète. Une propriété peut parfaitement être héréditaire et fausse pour tout $n$ .

Considérons en effet la proposition

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

Vérifions qu'elle est héréditaire. Soit $n ⩾ 1$ fixé, supposons $H_{n}$ vraie. Alors

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

(le calcul est exactement celui de l'exemple précédent, le $+ 1$ étant simplement recopié). C'est bien $H_{n + 1}$ : la propriété est héréditaire.

Et pourtant elle est fausse pour tout $n$ . Pour $n = 1$ : le membre de gauche vaut $1$ , le membre de droite vaut $\frac{1 \times 2}{2} + 1 = 2$ . L'initialisation échoue, et comme on l'a démontré plus haut, la vraie formule est sans le $+ 1$ .

Moralité : l'hérédité, à elle seule, ne démontre strictement rien. Elle dit seulement « si jamais c'était vrai quelque part, ce serait vrai après ». Encore faut-il que ce soit vrai quelque part.

Remarque

Piège n°2 : supposer ce que l'on veut démontrer. L'hérédité consiste à fixer un entier $n$ et à supposer $H_{n}$ pour celui-là. Écrire « supposons que pour tout $n$ , $H_{n}$ soit vraie » revient à supposer le résultat cherché : la démonstration ne vaut plus rien.

Rédaction fautive. « Supposons que pour tout $n \in N$ , $u_{n} ⩽ 3$ . Montrons que $u_{n + 1} ⩽ 3$ . »

Rédaction correcte. « Soit $n \in N$ fixé. Supposons $u_{n} ⩽ 3$ . Montrons que $u_{n + 1} ⩽ 3$ . »

La différence tient à un mot, et elle est totale. C'est l'une des rares fautes qui font perdre l'intégralité des points d'une question.

Remarque

Piège n°3 : se tromper de rang de départ. L'initialisation doit être faite au rang où commence l'énoncé, et il faut vérifier que l'hérédité est valable à partir de ce rang. Ces deux rangs ne coïncident pas toujours, et c'est là que se glissent les erreurs.

Exemple

Un cas où le rang de départ compte vraiment. Considérons la proposition « $2^{n} ⩾ n^{2}$ ». Calculons les premières valeurs.

$n$	0	1	2	3	4	5
$2^{n}$	1	2	4	8	16	32
$n^{2}$	0	1	4	9	16	25

L'inégalité est vraie pour $n = 0$ , $1$ , $2$ , fausse pour $n = 3$ ( $8 < 9$ ), puis vraie de nouveau à partir de $n = 4$ . On ne peut donc pas espérer démontrer « pour tout $n \in N$ , $2^{n} ⩾ n^{2}$ » : c'est faux. L'énoncé correct est : pour tout $n ⩾ 4$ , $2^{n} ⩾ n^{2}$ .

Vérifions au passage que l'hérédité, elle, fonctionne dès $n ⩾ 3$ . Soit $n ⩾ 3$ fixé, supposons $2^{n} ⩾ n^{2}$ . Alors

2^{n + 1} = 2 \times 2^{n} ⩾ 2 n^{2}

Il suffit donc de montrer que $2 n^{2} ⩾ (n + 1)^{2}$ . Or

2 n^{2} - (n + 1)^{2} = 2 n^{2} - n^{2} - 2 n - 1 = n^{2} - 2 n - 1 = (n - 1)^{2} - 2

et pour $n ⩾ 3$ on a $(n - 1)^{2} ⩾ 4 > 2$ , donc $2 n^{2} - (n + 1)^{2} > 0$ . Ainsi $2^{n + 1} ⩾ 2 n^{2} ⩾ (n + 1)^{2}$ .

La situation est donc la suivante : l'hérédité vaut pour tout $n ⩾ 3$ , mais la propriété est fausse au rang $3$ . Il faut donc initialiser au rang $4$ (où $16 ⩾ 16$ est vrai), et la conclusion ne porte que sur les $n ⩾ 4$ . Une initialisation faite au rang $3$ « parce que l'hérédité marche à partir de $3$ » serait un contresens complet.

Remarque

Piège n°4 : la conclusion qui déborde. Si l'on initialise au rang $n_{0}$ , la conclusion est « pour tout $n ⩾ n_{0}$ », et surtout pas « pour tout $n \in N$ ». Recopier machinalement la conclusion d'un exercice précédent est une source d'erreurs fréquente.

Piège n°5 : la récurrence inutile. Toutes les formules ne s'établissent pas par récurrence, et certaines démonstrations directes sont bien plus courtes et bien plus éclairantes. Nous verrons dans la section suivante que la formule $\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}$ se démontre aussi par télescopage et par la méthode de Gauss, sans aucune récurrence. Une récurrence a d'ailleurs un inconvénient de fond : elle vérifie une formule que l'on connaît déjà, elle ne permet jamais de la découvrir.

La récurrence double

Certaines suites sont définies par une relation qui fait intervenir les deux termes précédents. L'hypothèse portant sur le seul rang $n$ ne suffit alors plus à atteindre le rang $n + 1$ : il faut disposer de deux rangs consécutifs.

Propriété

Récurrence double. Soit $n_{0}$ un entier naturel et, pour chaque entier $n ⩾ n_{0}$ , une proposition $H_{n}$ . Si :

$H_{n_{0}}$ et $H_{n_{0} + 1}$ sont vraies (initialisation aux deux premiers rangs) ;
pour tout entier $n ⩾ n_{0}$ , l'implication $(H_{n} et H_{n + 1}) ⟹ H_{n + 2}$ est vraie ;

alors $H_{n}$ est vraie pour tout entier $n ⩾ n_{0}$ .

Il ne s'agit pas d'un nouveau principe, mais d'une variante d'emploi du précédent, adaptée aux suites définies par une relation d'ordre $2$ .

Remarque

Reprenons l'image de l'échelle : ici, on ne sait monter d'un barreau que si l'on a un pied sur les deux barreaux précédents. Il faut donc en gravir deux pour démarrer. Une initialisation à un seul rang laisserait la machine en panne dès le premier pas, et c'est une erreur très fréquente en devoir.

Exemple

Une suite récurrente d'ordre $2$ . Soit $(u_{n})_{n \in N}$ la suite définie par

u_{0} = 1, u_{1} = 5, et \forall n \in N, u_{n + 2} = 5 u_{n + 1} - 6 u_{n}

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

Au brouillon d'abord, calculons quelques termes pour vérifier que l'énoncé est plausible : $u_{2} = 5 \times 5 - 6 \times 1 = 19$ , puis $u_{3} = 5 \times 19 - 6 \times 5 = 95 - 30 = 65$ . La formule proposée donne $3^{3} - 2^{3} = 27 - 8 = 19$ pour $n = 2$ , et $3^{4} - 2^{4} = 81 - 16 = 65$ pour $n = 3$ . Tout concorde.

Énoncé de la propriété. Pour tout entier $n \in N$ , notons $H_{n}$ la proposition :

H_{n} : u_{n} = 3^{n + 1} - 2^{n + 1}

Montrons par récurrence double que $H_{n}$ est vraie pour tout $n \in N$ .

Initialisation (deux rangs).

Pour $n = 0$ : $3^{0 + 1} - 2^{0 + 1} = 3 - 2 = 1 = u_{0}$ . Donc $H_{0}$ est vraie.

Pour $n = 1$ : $3^{1 + 1} - 2^{1 + 1} = 9 - 4 = 5 = u_{1}$ . Donc $H_{1}$ est vraie.

Hérédité. Soit $n \in N$ un entier fixé. Supposons $H_{n}$ et $H_{n + 1}$ vraies, c'est-à-dire

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

Montrons que $u_{n + 2} = 3^{n + 3} - 2^{n + 3}$ .

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 (3^{n + 2} - 2^{n + 2}) - 6 (3^{n + 1} - 2^{n + 1}) \\ = 5 \times 3^{n + 2} - 5 \times 2^{n + 2} - 6 \times 3^{n + 1} + 6 \times 2^{n + 1} \end{aligned}

Regroupons les puissances de $3$ d'un côté et celles de $2$ de l'autre. Comme $6 \times 3^{n + 1} = 2 \times 3 \times 3^{n + 1} = 2 \times 3^{n + 2}$ et $6 \times 2^{n + 1} = 3 \times 2 \times 2^{n + 1} = 3 \times 2^{n + 2}$ , il vient

\begin{aligned} u_{n + 2} & = 5 \times 3^{n + 2} - 2 \times 3^{n + 2} - 5 \times 2^{n + 2} + 3 \times 2^{n + 2} \\ = (5 - 2) \times 3^{n + 2} - (5 - 3) \times 2^{n + 2} \\ = 3 \times 3^{n + 2} - 2 \times 2^{n + 2} \\ = 3^{n + 3} - 2^{n + 3} \end{aligned}

C'est exactement $H_{n + 2}$ .

Conclusion. Les propriétés $H_{0}$ et $H_{1}$ sont vraies, et pour tout $n \in N$ , $H_{n}$ et $H_{n + 1}$ entraînent $H_{n + 2}$ . D'après le principe de récurrence double, pour tout entier naturel $n$ ,

u_{n} = 3^{n + 1} - 2^{n + 1} □

Remarque

Deux observations sur cet exemple.

L'hérédité utilise les deux hypothèses, $H_{n}$ et $H_{n + 1}$ : c'est le signe que la récurrence double était bien nécessaire. Si une seule avait suffi, une récurrence simple aurait fait l'affaire.
Les nombres $2$ et $3$ qui apparaissent dans la formule ne sortent pas de nulle part : ce sont les solutions de l'équation $r^{2} = 5 r - 6$ , c'est-à-dire $r^{2} - 5 r + 6 = 0$ . Vous démontrerez dans le chapitre consacré aux suites que c'est un phénomène général pour les suites vérifiant $u_{n + 2} = a u_{n + 1} + b u_{n}$ . Ici, on nous donnait la formule ; la récurrence sert à la vérifier, pas à la trouver.

La récurrence forte

Dernière variante d'emploi : parfois, pour atteindre le rang $n + 1$ , il faut disposer de tous les rangs précédents, et pas seulement d'un ou de deux.

Propriété

Récurrence forte. Soit $n_{0}$ un entier naturel et, pour chaque entier $n ⩾ n_{0}$ , une proposition $H_{n}$ . Si :

$H_{n_{0}}$ est vraie ;
pour tout entier $n ⩾ n_{0}$ , l'implication $(H_{n_{0}} et H_{n_{0} + 1} et \dots et H_{n}) ⟹ H_{n + 1}$ est vraie ;

alors $H_{n}$ est vraie pour tout entier $n ⩾ n_{0}$ .

Autrement dit, on s'autorise à supposer la propriété vraie à tous les rangs de $n_{0}$ jusqu'à $n$ pour la démontrer au rang $n + 1$ . C'est encore une variante d'emploi du principe de récurrence, pas un principe nouveau.

Remarque

Quand y penser ? Dès que le rang $n + 1$ dépend d'un rang antérieur qu'on ne contrôle pas d'avance : une relation faisant intervenir la somme de tous les termes précédents, ou un terme $u_{n + 1}$ défini à partir d'un $u_{k}$ avec $k$ variable. En pratique, si en rédigeant l'hérédité vous vous surprenez à utiliser $H_{n - 3}$ alors que vous n'avez supposé que $H_{n}$ , c'est le signal : il faut passer à une récurrence forte.

Exemple

Une suite définie par la somme de tous ses termes précédents. Soit $(u_{n})_{n ⩾ 1}$ la suite définie par

u_{1} = 1 et \forall n ⩾ 1, u_{n + 1} = \frac{2}{n} \sum_{k = 1}^{n} u_{k}

Montrons que pour tout entier $n ⩾ 1$ , $u_{n} = n$ .

Au brouillon : $u_{2} = \frac{2}{1} \times u_{1} = 2$ , puis $u_{3} = \frac{2}{2} \times (u_{1} + u_{2}) = 1 + 2 = 3$ , puis $u_{4} = \frac{2}{3} \times (1 + 2 + 3) = \frac{2 \times 6}{3} = 4$ . La formule semble juste.

Énoncé de la propriété. Pour tout entier $n ⩾ 1$ , notons $H_{n}$ la proposition : « $u_{n} = n$ ». Montrons par récurrence forte que $H_{n}$ est vraie pour tout $n ⩾ 1$ .

Initialisation. Pour $n = 1$ : $u_{1} = 1$ par définition de la suite, donc $H_{1}$ est vraie.

Hérédité. Soit $n ⩾ 1$ un entier fixé. Supposons que $H_{1}, H_{2}, \dots, H_{n}$ soient toutes vraies, c'est-à-dire que $u_{k} = k$ pour tout entier $k$ compris entre $1$ et $n$ . Montrons que $u_{n + 1} = n + 1$ .

Par définition de la suite,

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

Or, par hypothèse de récurrence forte, $u_{k} = k$ pour chacun des indices $k$ intervenant dans cette somme. Donc

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

d'après la formule démontrée plus haut. Par conséquent

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

C'est exactement $H_{n + 1}$ .

Conclusion. La propriété est vraie au rang $1$ , et pour tout $n ⩾ 1$ , la conjonction de $H_{1}, \dots, H_{n}$ entraîne $H_{n + 1}$ . D'après le principe de récurrence forte, $u_{n} = n$ pour tout entier $n ⩾ 1$ . $□$

Pourquoi une récurrence forte ? Parce que le calcul de $u_{n + 1}$ fait intervenir tous les termes $u_{1}, \dots, u_{n}$ à la fois. La seule hypothèse « $u_{n} = n$ » n'aurait rien donné : on ne saurait pas évaluer la somme.

Remarque

Comment choisir entre les trois ? La question se règle en regardant la relation de définition, ou l'endroit du calcul où l'on bloque.

La relation exprime $u_{n + 1}$ en fonction de $u_{n}$ seulement : récurrence simple.
La relation exprime $u_{n + 2}$ en fonction de $u_{n + 1}$ et $u_{n}$ : récurrence double, avec deux initialisations.
La relation fait intervenir une somme de tous les termes précédents, ou un terme d'indice indéterminé : récurrence forte.

Et dans le doute, la récurrence forte est toujours licite : supposer plus de choses ne peut pas rendre une démonstration fausse. Elle est simplement moins élégante quand elle n'est pas nécessaire.

Sommes et produits

Les points de suspension sont commodes mais dangereux : dans « $1 + 2 + \dots + n$ », le lecteur devine, il ne lit pas. Or une démonstration ne se devine pas. Le symbole $\sum$ permet d'écrire une somme sans aucune ambiguïté, et surtout de la manipuler avec des règles précises. C'est un outil de calcul que vous utiliserez tous les jours, en analyse comme en probabilités.

La notation somme

Définition

Soient $p$ et $n$ deux entiers avec $p ⩽ n$ , et $u_{p}, u_{p + 1}, \dots, u_{n}$ des nombres réels. On note

\sum_{i = p}^{n} u_{i} = u_{p} + u_{p + 1} + \dots + u_{n}

et on lit « somme, pour $i$ allant de $p$ à $n$ , des $u_{i}$ ». L'entier $p$ est la borne inférieure, l'entier $n$ la borne supérieure, et $u_{i}$ le terme général de la somme.

Plus généralement, si $I$ est une partie finie de $N$ et si l'on dispose d'un réel $u_{i}$ pour chaque $i \in I$ , on note

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

la somme de tous ces réels. L'ordre dans lequel on les additionne n'a aucune importance : l'addition des réels est commutative et associative.

Exemple

a. $\sum_{i = 1}^{4} i^{2} = 1^{2} + 2^{2} + 3^{2} + 4^{2} = 1 + 4 + 9 + 16 = 30$ .

b. $\sum_{i = 3}^{6} (2 i - 1) = 5 + 7 + 9 + 11 = 32$ .

c. Avec $I = {1, 3, 7}$ et $u_{i} = i^{2}$ : $\sum_{i \in I} u_{i} = 1 + 9 + 49 = 59$ .

d. Avec $I$ l'ensemble des entiers pairs compris entre $1$ et $10$ , c'est-à-dire $I = {2, 4, 6, 8, 10}$ : $\sum_{i \in I} i = 2 + 4 + 6 + 8 + 10 = 30$ .

Remarque

La notation $\sum_{i \in I}$ est plus souple que la notation à deux bornes, et c'est elle qui servira en probabilités (somme sur un ensemble d'issues) et un peu plus loin dans ce chapitre pour les sommes doubles. Quand $I = {p, p + 1, \dots, n}$ , les deux notations désignent la même chose.

Indice muet, nombre de termes, somme vide

Trois points de vocabulaire qui règlent à eux seuls une bonne partie des erreurs de calcul.

Propriété

L'indice est muet. Dans $\sum_{i = p}^{n} u_{i}$ , la lettre $i$ n'a d'existence qu'à l'intérieur de la somme. On peut la remplacer par n'importe quelle autre lettre non utilisée par ailleurs :

\sum_{i = 1}^{n} u_{i} = \sum_{k = 1}^{n} u_{k} = \sum_{j = 1}^{n} u_{j}

En conséquence, le résultat d'une somme ne peut pas dépendre de l'indice. Une réponse de la forme « $\sum_{k = 1}^{n} k = n k$ » est nécessairement fausse : le $k$ de droite ne veut rien dire.

Remarque

Corollaire pratique : l'indice de sommation ne doit jamais porter le même nom qu'une autre lettre de l'énoncé. Écrire $\sum_{n = 1}^{n} u_{n}$ n'a aucun sens, puisque le même symbole $n$ y désigne à la fois la borne (fixée) et l'indice (variable). C'est une faute qui coûte cher, et elle est fréquente au moment de démarrer un calcul.

Propriété

Nombre de termes. La somme $\sum_{i = p}^{n} u_{i}$ comporte exactement

n - p + 1 termes

En particulier, pour une constante $c$ ne dépendant pas de $i$ :

\sum_{i = p}^{n} c = (n - p + 1) c et notamment \sum_{i = 1}^{n} 1 = n

Démonstration. Les indices concernés sont les entiers $p, p + 1, \dots, n$ . Pour les compter, on les décale de $p$ : l'application qui à $i$ associe $i - p + 1$ transforme cette liste en $1, 2, \dots, n - p + 1$ , sans répétition ni oubli. Il y a donc $n - p + 1$ indices, donc autant de termes. Quand tous les termes valent $c$ , la somme vaut $(n - p + 1) c$ . $□$

Remarque

Le piège du « $+ 1$ ». C'est l'erreur de calcul la plus répandue de tout le chapitre. De $3$ à $7$ , il y a $7 - 3 + 1 = 5$ entiers ( $3$ , $4$ , $5$ , $6$ , $7$ ), et non $4$ . On dit parfois « erreur des poteaux » : entre le premier et le dernier poteau d'une clôture, il y a un poteau de plus que d'intervalles.

Le réflexe qui sauve : quand vous n'êtes pas sûr, comptez sur un petit cas. De $1$ à $3$ , il y a $3$ termes, et la formule donne $3 - 1 + 1 = 3$ . C'est réglé en trois secondes.

Définition

Convention de la somme vide. Si $p > n$ , la somme $\sum_{i = p}^{n} u_{i}$ est dite vide et vaut $0$ par convention. De même, $\sum_{i \in \emptyset} u_{i} = 0$ .

Remarque

Cette convention n'est pas une coquetterie : elle rend les formules valables sans avoir à traiter des cas particuliers. Par exemple, la formule $\sum_{i = 1}^{n} 1 = n$ reste correcte pour $n = 0$ , puisque la somme est alors vide et vaut $0$ . De même, dans un télescopage, elle permet de ne pas séparer le cas où la somme se réduit à un seul terme, comme nous le verrons.

Notez la cohérence : $0$ est l'élément neutre de l'addition, et c'est bien la valeur qui « ne change rien » quand on ajoute une somme vide.

Linéarité et relation de Chasles

Propriété

Linéarité de la somme. Soient $(u_{i})$ et $(v_{i})$ deux familles de réels indexées par les entiers de $p$ à $n$ , et $λ$ , $μ$ deux réels. Alors

\sum_{i = p}^{n} (λ u_{i} + μ v_{i}) = λ \sum_{i = p}^{n} u_{i} + μ \sum_{i = p}^{n} v_{i}

En particulier, on peut séparer une somme en deux et sortir une constante :

\sum_{i = p}^{n} (u_{i} + v_{i}) = \sum_{i = p}^{n} u_{i} + \sum_{i = p}^{n} v_{i} et \sum_{i = p}^{n} λ u_{i} = λ \sum_{i = p}^{n} u_{i}

Démonstration. Il suffit d'écrire la somme en toutes lettres et d'utiliser la commutativité et l'associativité de l'addition des réels, ainsi que la distributivité de la multiplication :

\begin{aligned} \sum_{i = p}^{n} (λ u_{i} + μ v_{i}) & = (λ u_{p} + μ v_{p}) + \dots + (λ u_{n} + μ v_{n}) \\ = (λ u_{p} + \dots + λ u_{n}) + (μ v_{p} + \dots + μ v_{n}) \\ = λ (u_{p} + \dots + u_{n}) + μ (v_{p} + \dots + v_{n}) \\ = λ \sum_{i = p}^{n} u_{i} + μ \sum_{i = p}^{n} v_{i} \end{aligned}

$□$

Remarque

Ce que la linéarité n'autorise PAS. Il n'y a aucune formule donnant la somme d'un produit, d'un quotient, d'un carré ou d'un logarithme en fonction des sommes des facteurs. Les écritures suivantes sont fausses en général :

\sum_{i = 1}^{n} u_{i} v_{i} \neq (\sum_{i = 1}^{n} u_{i}) (\sum_{i = 1}^{n} v_{i}) \sum_{i = 1}^{n} u_{i}^{2} \neq {(\sum_{i = 1}^{n} u_{i})}^{2} \sum_{i = 1}^{n} \frac{1}{u_{i}} \neq \frac{1}{\sum_{i = 1}^{n} u_{i}}

Contre-exemple immédiat pour la première : avec $n = 2$ , $u = (1, 1)$ et $v = (1, 1)$ , le membre de gauche vaut $1 + 1 = 2$ et le membre de droite vaut $2 \times 2 = 4$ .

Une constante, en revanche, sort toujours : dans $\sum_{i = 1}^{n} n u_{i}$ , le facteur $n$ ne dépend pas de $i$ , il est donc constant pour la sommation et l'on peut écrire $n \sum_{i = 1}^{n} u_{i}$ . Le critère est toujours le même : le facteur dépend-il de l'indice ?

Propriété

Relation de Chasles. Soient $p ⩽ m < n$ trois entiers. Alors

\sum_{i = p}^{n} u_{i} = \sum_{i = p}^{m} u_{i} + \sum_{i = m + 1}^{n} u_{i}

En particulier, on peut isoler le premier ou le dernier terme d'une somme :

\sum_{i = p}^{n} u_{i} = u_{p} + \sum_{i = p + 1}^{n} u_{i} et \sum_{i = p}^{n} u_{i} = (\sum_{i = p}^{n - 1} u_{i}) + u_{n}

Démonstration. La liste $u_{p}, \dots, u_{n}$ se décompose en la liste $u_{p}, \dots, u_{m}$ suivie de la liste $u_{m + 1}, \dots, u_{n}$ ; l'associativité de l'addition permet de regrouper les termes comme on le souhaite. $□$

Remarque

L'isolement du dernier terme est exactement le geste qui fait fonctionner toutes les hérédités de récurrence portant sur des sommes. Relisez le premier exemple de la section précédente : la première ligne du calcul est une relation de Chasles.

Le changement d'indice

C'est la manipulation la plus délicate, et la plus utile. L'idée est simple : on renomme l'indice pour faire apparaître une autre écriture de la même somme. Comme l'indice est muet, la valeur ne change pas ; ce qui change, ce sont les bornes et le terme général.

Méthode

Effectuer un changement d'indice par translation. On veut transformer $\sum_{i = p}^{n} u_{i}$ en posant $j = i + a$ (où $a$ est un entier fixé).

Écrire la correspondance : $j = i + a$ , donc $i = j - a$ .
Translater les bornes : quand $i$ parcourt les entiers de $p$ à $n$ , l'entier $j$ parcourt ceux de $p + a$ à $n + a$ . On l'écrit toujours en toutes lettres : « lorsque $i$ varie de $p$ à $n$ , $j$ varie de $p + a$ à $n + a$ ».
Réécrire le terme général en remplaçant chaque $i$ par $j - a$ .
Vérifier le nombre de termes : il doit être inchangé. Avant : $n - p + 1$ . Après : $(n + a) - (p + a) + 1 = n - p + 1$ . C'est le contrôle qui détecte instantanément une erreur de bornes.

Exemple

a. Transformons $\sum_{i = 1}^{n} \frac{1}{i + 1}$ en posant $j = i + 1$ .

Lorsque $i$ varie de $1$ à $n$ , l'entier $j = i + 1$ varie de $2$ à $n + 1$ . Le terme général $\frac{1}{i + 1}$ devient $\frac{1}{j}$ . Donc

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

Contrôle du nombre de termes : $n - 1 + 1 = n$ à gauche, $(n + 1) - 2 + 1 = n$ à droite. Cohérent.

Contrôle sur $n = 2$ : à gauche $\frac{1}{2} + \frac{1}{3}$ ; à droite $\frac{1}{2} + \frac{1}{3}$ . Identiques.

b. Transformons $\sum_{k = 2}^{n} (k - 1)^{2}$ en posant $j = k - 1$ .

Lorsque $k$ varie de $2$ à $n$ , $j$ varie de $1$ à $n - 1$ , et le terme général devient $j^{2}$ :

\sum_{k = 2}^{n} (k - 1)^{2} = \sum_{j = 1}^{n - 1} j^{2}

c. Transformons $\sum_{k = 0}^{n} q^{k + 1}$ en posant $j = k + 1$ : lorsque $k$ varie de $0$ à $n$ , $j$ varie de $1$ à $n + 1$ , donc

\sum_{k = 0}^{n} q^{k + 1} = \sum_{j = 1}^{n + 1} q^{j}

Méthode

Effectuer un changement d'indice par renversement. On veut lire la somme « à l'envers ». Dans $\sum_{i = p}^{n} u_{i}$ , on pose $j = n + p - i$ .

Lorsque $i = p$ , on a $j = n$ ; lorsque $i = n$ , on a $j = p$ . L'indice $j$ parcourt donc les mêmes entiers, dans l'ordre inverse, et comme l'ordre des termes ne compte pas :

\sum_{i = p}^{n} u_{i} = \sum_{j = p}^{n} u_{n + p - j}

C'est ce changement d'indice qui est au cœur de la méthode de Gauss, ci-dessous.

Remarque

Les deux erreurs classiques du changement d'indice.

Translater le terme général et oublier les bornes (ou l'inverse). Les deux se font en même temps, c'est un seul geste.
Croire qu'un changement d'indice change la valeur de la somme. Il ne change rien : c'est la même somme, écrite autrement. Un changement d'indice ne « simplifie » jamais tout seul ; il sert à rendre deux sommes comparables.

Le télescopage

Propriété

Somme télescopique. Soient $p ⩽ n$ deux entiers et $a_{p}, a_{p + 1}, \dots, a_{n + 1}$ des réels. Alors

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

Démonstration. Séparons la somme en deux par linéarité :

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

Dans la première somme, posons le changement d'indice $j = k + 1$ : lorsque $k$ varie de $p$ à $n$ , $j$ varie de $p + 1$ à $n + 1$ , et le terme général $a_{k + 1}$ devient $a_{j}$ . Donc

\sum_{k = p}^{n} (a_{k + 1} - a_{k}) = \sum_{j = p + 1}^{n + 1} a_{j} - \sum_{j = p}^{n} a_{j}

Les deux sommes portent maintenant sur le même terme général $a_{j}$ et ne diffèrent plus que par leurs bornes. Isolons le dernier terme de la première et le premier terme de la seconde, par la relation de Chasles :

\sum_{j = p + 1}^{n + 1} a_{j} = (\sum_{j = p + 1}^{n} a_{j}) + a_{n + 1} et \sum_{j = p}^{n} a_{j} = a_{p} + \sum_{j = p + 1}^{n} a_{j}

En soustrayant, la somme $\sum_{j = p + 1}^{n} a_{j}$ se simplifie et il reste

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

Cas limite. Si $n = p$ , la somme $\sum_{j = p + 1}^{n} a_{j}$ est vide et vaut $0$ d'après notre convention : le calcul ci-dessus reste valable, et donne $a_{p + 1} - a_{p}$ , ce qui est bien la valeur de la somme réduite à son unique terme. $□$

Méthode

Reconnaître et utiliser un télescopage.

Chercher à écrire le terme général sous la forme $a_{k + 1} - a_{k}$ , c'est-à-dire comme la différence de deux valeurs consécutives d'une même expression.
Écrire explicitement quel est le $a_{k}$ choisi : « posons $a_{k} = \dots$ ».
Appliquer la formule : il ne reste que $a_{n + 1} - a_{p}$ .
Contrôler sur une petite valeur de $n$ .

Les formes qui doivent alerter : une différence de deux termes voisins ( $\ln (k + 1) - \ln k$ , $\sqrt{k + 1} - \sqrt{k}$ , $(k + 1)^{2} - k^{2}$ ), ou un quotient du type $\frac{1}{k (k + 1)}$ que l'on décompose d'abord en $\frac{1}{k} - \frac{1}{k + 1}$ .

Attention au sens de la différence : une somme de termes $a_{k} - a_{k + 1}$ (dans l'autre sens) vaut $a_{p} - a_{n + 1}$ . Un signe se perd très vite ici.

Exemple

Calculons $S = \sum_{k = 1}^{n} \frac{1}{k (k + 1)}$ pour $n ⩾ 1$ .

Commençons par décomposer le terme général. Pour tout $k ⩾ 1$ ,

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

Posons donc $a_{k} = - \frac{1}{k}$ , de sorte que $a_{k + 1} - a_{k} = - \frac{1}{k + 1} + \frac{1}{k} = \frac{1}{k (k + 1)}$ . La somme est télescopique :

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

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

Les sommes usuelles

Ces formules doivent être sues par cœur et reconnues instantanément. Nous les démontrons toutes, et parfois de deux façons.

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}

Et pour tout réel $q$ et tout entier $n ⩾ 0$ (somme géométrique, vue au lycée) :

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

Démonstration de $\sum_{k = 1}^{n} 1 = n$ . La somme comporte $n - 1 + 1 = n$ termes, tous égaux à $1$ . $□$

Première démonstration de $\sum_{k = 1}^{n} k$ : par télescopage. Considérons la somme

U = \sum_{k = 1}^{n} ((k + 1)^{2} - k^{2})

Calculons-la d'abord par télescopage. En posant $a_{k} = k^{2}$ , le terme général vaut $a_{k + 1} - a_{k}$ , donc

U = a_{n + 1} - a_{1} = (n + 1)^{2} - 1 = n^{2} + 2 n + 1 - 1 = n^{2} + 2 n

Calculons-la ensuite en développant. Pour tout $k$ , $(k + 1)^{2} - k^{2} = k^{2} + 2 k + 1 - k^{2} = 2 k + 1$ . Par linéarité,

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

Confrontons les deux calculs. Ils portent sur la même quantité, donc

2 \sum_{k = 1}^{n} k + n = n^{2} + 2 n d’o \overset{ˋ}{u} 2 \sum_{k = 1}^{n} k = n^{2} + n = n (n + 1) puis \sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}

$□$

Seconde démonstration de $\sum_{k = 1}^{n} k$ : la méthode de Gauss. Notons $S = \sum_{k = 1}^{n} k$ . Effectuons dans cette somme le changement d'indice par renversement $j = n + 1 - k$ : lorsque $k$ varie de $1$ à $n$ , $j$ varie de $n$ à $1$ , c'est-à-dire décrit les mêmes entiers, et $k = n + 1 - j$ . Donc

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

Additionnons les deux écritures de $S$ , en réutilisant la lettre $k$ comme indice dans les deux (elle est muette) :

2 S = \sum_{k = 1}^{n} k + \sum_{k = 1}^{n} (n + 1 - k) = \sum_{k = 1}^{n} [k + (n + 1 - k)] = \sum_{k = 1}^{n} (n + 1)

Cette dernière somme comporte $n$ termes tous égaux à la constante $n + 1$ , donc $2 S = n (n + 1)$ , d'où $S = \frac{n (n + 1)}{2}$ . $□$

Remarque

C'est l'idée qu'aurait eue, dit-on, le jeune Gauss à qui l'on demandait d'additionner les entiers de $1$ à $100$ : il a apparié le premier avec le dernier, le deuxième avec l'avant-dernier, et ainsi de suite, chaque paire valant $101$ . Il y a $50$ paires, d'où $5050$ . La rédaction ci-dessus est simplement la version propre de cette idée : le renversement d'indice remplace les pointillés.

Notez qu'aucune de ces deux démonstrations n'est une récurrence. Toutes deux produisent le résultat, alors que la récurrence de la section précédente se contentait de le vérifier.

Démonstration de $\sum_{k = 1}^{n} k^{2}$ : par récurrence. Pour tout entier $n ⩾ 1$ , notons

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

Initialisation. Pour $n = 1$ : le membre de gauche vaut $1^{2} = 1$ ; le membre de droite vaut $\frac{1 \times 2 \times 3}{6} = 1$ . Donc $H_{1}$ est vraie.

Hérédité. Soit $n ⩾ 1$ fixé, supposons $H_{n}$ vraie. Alors, en isolant le dernier terme :

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

Il reste à factoriser $2 n^{2} + 7 n + 6$ . Son discriminant vaut $49 - 48 = 1$ , ses racines sont $\frac{- 7 - 1}{4} = - 2$ et $\frac{- 7 + 1}{4} = - \frac{3}{2}$ , donc

2 n^{2} + 7 n + 6 = 2 (n + 2) (n + \frac{3}{2}) = (n + 2) (2 n + 3)

Contrôle du développement : $(n + 2) (2 n + 3) = 2 n^{2} + 3 n + 4 n + 6 = 2 n^{2} + 7 n + 6$ . C'est bien cela. Par conséquent

\sum_{k = 1}^{n + 1} k^{2} = \frac{(n + 1) (n + 2) (2 n + 3)}{6} = \frac{(n + 1) [(n + 1) + 1] [2 (n + 1) + 1]}{6}

ce qui est exactement $H_{n + 1}$ .

Conclusion. Par récurrence, la formule est vraie pour tout entier $n ⩾ 1$ . $□$

Contrôle pour $n = 3$ : $1 + 4 + 9 = 14$ , et $\frac{3 \times 4 \times 7}{6} = \frac{84}{6} = 14$ .

Démonstration de la somme géométrique : par télescopage. Soit $q$ un réel et $n ⩾ 0$ .

Cas $q = 1$ . La somme vaut $\sum_{k = 0}^{n} 1^{k} = \sum_{k = 0}^{n} 1 = n + 1$ , car elle comporte $n - 0 + 1 = n + 1$ termes égaux à $1$ .

Cas $q \neq 1$ . Notons $S = \sum_{k = 0}^{n} q^{k}$ et calculons $(1 - q) S$ . Par linéarité,

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

Posons $a_{k} = q^{k}$ . Le terme général s'écrit $a_{k} - a_{k + 1} = - (a_{k + 1} - a_{k})$ , donc, d'après la formule du télescopage,

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

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

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

$□$

Contrôle pour $q = 2$ et $n = 3$ : $1 + 2 + 4 + 8 = 15$ , et $\frac{1 - 2^{4}}{1 - 2} = \frac{- 15}{- 1} = 15$ .

Remarque

Trois réflexes autour de la somme géométrique.

Le cas $q = 1$ est un cas particulier obligatoire : la formule générale a $1 - q$ au dénominateur. Un correcteur qui voit une division par $1 - q$ sans discussion préalable sanctionne.
Retenez la forme mnémotechnique : $\frac{1 - q^{nombre de termes}}{1 - q}$ . Ici il y a $n + 1$ termes, d'où l'exposant $n + 1$ .
Si la somme commence à $k = 1$ et non à $k = 0$ , on ne réapprend pas de formule : on retranche le terme manquant, $\sum_{k = 1}^{n} q^{k} = (\sum_{k = 0}^{n} q^{k}) - 1$ .

Exemple

Un calcul complet mêlant plusieurs formules. Calculons, pour $n ⩾ 1$ ,

T = \sum_{k = 1}^{n} (3 k^{2} - 2 k + 5)

Par linéarité de la somme :

\begin{aligned} T & = 3 \sum_{k = 1}^{n} k^{2} - 2 \sum_{k = 1}^{n} k + 5 \sum_{k = 1}^{n} 1 \\ = 3 \times \frac{n (n + 1) (2 n + 1)}{6} - 2 \times \frac{n (n + 1)}{2} + 5 n \\ = \frac{n (n + 1) (2 n + 1)}{2} - n (n + 1) + 5 n \end{aligned}

On peut mettre $n$ en facteur et réduire au même dénominateur :

\begin{aligned} T & = \frac{n [(n + 1) (2 n + 1) - 2 (n + 1) + 10]}{2} \\ = \frac{n [2 n^{2} + 3 n + 1 - 2 n - 2 + 10]}{2} \\ = \frac{n (2 n^{2} + n + 9)}{2} \end{aligned}

Contrôle pour $n = 2$ : le calcul direct donne $(3 - 2 + 5) + (12 - 4 + 5) = 6 + 13 = 19$ , et la formule donne $\frac{2 \times (8 + 2 + 9)}{2} = 19$ . $□$

La notation produit et la factorielle

Définition

Soient $p ⩽ n$ deux entiers et $u_{p}, \dots, u_{n}$ des réels. On note

\prod_{i = p}^{n} u_{i} = u_{p} \times u_{p + 1} \times \dots \times u_{n}

Par convention, un produit vide (c'est-à-dire lorsque $p > n$ , ou indexé par $\emptyset$ ) vaut $1$ , qui est l'élément neutre de la multiplication.

Définition

Pour tout entier $n ⩾ 1$ , on appelle factorielle de $n$ l'entier

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

et l'on pose $0! = 1$ , conformément à la convention du produit vide.

Les premières valeurs sont $1! = 1$ , $2! = 2$ , $3! = 6$ , $4! = 24$ , $5! = 120$ , $6! = 720$ . La croissance est extrêmement rapide : $10! = 3 628 800$ .

Propriété

Pour tout entier $n ⩾ 0$ : $(n + 1)! = (n + 1) \times n!$

Démonstration. Il suffit d'isoler le dernier facteur du produit, celui qui correspond à $k = n + 1$ :

(n + 1)! = \prod_{k = 1}^{n + 1} k = (\prod_{k = 1}^{n} k) \times (n + 1) = n! \times (n + 1)

Pour $n = 0$ , la formule donne $1! = 1 \times 0! = 1$ , ce qui est cohérent avec les conventions. $□$

Remarque

Les règles de calcul sur les produits sont l'exact analogue de celles sur les sommes, avec la multiplication à la place de l'addition. En particulier :

une constante ne « sort » pas d'un produit comme d'une somme : $\prod_{i = 1}^{n} (λ u_{i}) = λ^{n} \prod_{i = 1}^{n} u_{i}$ , car le facteur $λ$ apparaît une fois par terme ;
le produit d'une constante vaut $\prod_{i = p}^{n} c = c^{n - p + 1}$ , l'exposant étant le nombre de termes ;
$\prod_{i = 1}^{n} (u_{i} v_{i}) = (\prod_{i = 1}^{n} u_{i}) (\prod_{i = 1}^{n} v_{i})$ , alors que la formule analogue est fausse pour les sommes. Le produit est multiplicatif, la somme est additive : chacun sa loi.

Propriété

Produit télescopique. Soient $p ⩽ n$ et $a_{p}, \dots, a_{n + 1}$ des réels tous non nuls. Alors

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

Démonstration. Écrivons le produit en toutes lettres :

\prod_{k = p}^{n} \frac{a_{k + 1}}{a_{k}} = \frac{a_{p + 1}}{a_{p}} \times \frac{a_{p + 2}}{a_{p + 1}} \times \dots \times \frac{a_{n + 1}}{a_{n}}

Chaque numérateur $a_{k + 1}$ , pour $k$ allant de $p$ à $n - 1$ , se simplifie avec le dénominateur du facteur suivant. Il ne subsiste que le numérateur du dernier facteur et le dénominateur du premier, d'où le résultat.

On peut aussi le déduire du télescopage additif lorsque tous les $a_{k}$ sont strictement positifs, en passant au logarithme : $\ln$ transforme le produit en somme, et $\sum_{k = p}^{n} (\ln a_{k + 1} - \ln a_{k}) = \ln a_{n + 1} - \ln a_{p}$ . $□$

Exemple

a. Calculons $P = \prod_{k = 1}^{n} \frac{k + 1}{k}$ pour $n ⩾ 1$ .

En posant $a_{k} = k$ (tous non nuls pour $k ⩾ 1$ ), le facteur général vaut $\frac{a_{k + 1}}{a_{k}}$ , donc

P = \frac{a_{n + 1}}{a_{1}} = \frac{n + 1}{1} = n + 1

Contrôle pour $n = 3$ : $\frac{2}{1} \times \frac{3}{2} \times \frac{4}{3} = 4 = 3 + 1$ .

b. Calculons $Q = \prod_{k = 2}^{n} (1 - \frac{1}{k})$ pour $n ⩾ 2$ .

Pour tout $k ⩾ 2$ , $1 - \frac{1}{k} = \frac{k - 1}{k}$ . Posons $a_{k} = \frac{1}{k - 1}$ , qui est bien défini et non nul pour $k ⩾ 2$ . Alors

\frac{a_{k + 1}}{a_{k}} = \frac{\frac{1}{k}}{\frac{1}{k - 1}} = \frac{k - 1}{k}

et le produit est donc télescopique :

Q = \prod_{k = 2}^{n} \frac{a_{k + 1}}{a_{k}} = \frac{a_{n + 1}}{a_{2}} = \frac{\frac{1}{n}}{1} = \frac{1}{n}

Contrôle pour $n = 4$ : $(1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{4}) = \frac{1}{2} \times \frac{2}{3} \times \frac{3}{4} = \frac{1}{4}$ . $□$

Sommes indexées par une partie finie de $N^{2}$

Il arrive très souvent que les quantités à additionner soient repérées par deux indices : un tableau de valeurs, une matrice de coûts, une loi de probabilité à deux variables. On parle alors de somme double.

Définition

Soit $A$ une partie finie de $N^{2}$ , c'est-à-dire un ensemble fini de couples d'entiers, et supposons donné un réel $u_{i, j}$ pour chaque couple $(i, j) \in A$ . On note

\sum_{(i, j) \in A} u_{i, j}

la somme de tous ces réels. Là encore, l'ordre dans lequel on effectue les additions n'a aucune importance.

Propriété

Cas rectangulaire et interversion des sommes. Soit $A = {1, \dots, n} \times {1, \dots, m}$ , c'est-à-dire l'ensemble des couples $(i, j)$ tels que $1 ⩽ i ⩽ n$ et $1 ⩽ j ⩽ m$ . Alors

\sum_{(i, j) \in A} u_{i, j} = \sum_{i = 1}^{n} (\sum_{j = 1}^{m} u_{i, j}) = \sum_{j = 1}^{m} (\sum_{i = 1}^{n} u_{i, j})

Les deux signes somme peuvent donc être intervertis dans le cas rectangulaire.

Justification. Disposons les $n m$ réels dans un tableau à $n$ lignes et $m$ colonnes, le réel $u_{i, j}$ étant placé à la ligne $i$ et à la colonne $j$ . La première écriture consiste à sommer chaque ligne, puis à additionner les totaux de lignes ; la seconde à sommer chaque colonne, puis à additionner les totaux de colonnes. Dans les deux cas, chaque case du tableau est comptée exactement une fois, et l'addition des réels est commutative et associative : les deux résultats sont égaux, et égaux à la somme de toutes les cases. $□$

Exemple

Un tableau minuscule pour fixer les idées. Prenons $n = 3$ , $m = 2$ et $u_{i, j} = i + j$ . Le tableau des valeurs est le suivant.

$u_{i, j}$	$j = 1$	$j = 2$
$i = 1$	2	3
$i = 2$	3	4
$i = 3$	4	5

Par lignes : les totaux valent $2 + 3 = 5$ , puis $3 + 4 = 7$ , puis $4 + 5 = 9$ , et $5 + 7 + 9 = 21$ .

Par colonnes : les totaux valent $2 + 3 + 4 = 9$ et $3 + 4 + 5 = 12$ , et $9 + 12 = 21$ .

Les deux lectures donnent bien $21$ .

Méthode

Calculer une somme double rectangulaire. On calcule d'abord la somme intérieure, en traitant l'indice extérieur comme une constante, puis la somme extérieure.

Repérer l'indice de la somme intérieure : c'est lui qui varie ; tout ce qui ne le contient pas est constant et peut sortir.
Calculer cette somme intérieure à l'aide des formules usuelles. Le résultat dépend en général de l'indice extérieur.
Calculer la somme extérieure du résultat obtenu.

Cas particulier très utile : si le terme général se factorise sous la forme $u_{i, j} = a_{i} b_{j}$ (chaque facteur ne dépendant que d'un seul indice), alors

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

car dans la somme intérieure, $a_{i}$ est constant et sort.

Exemple

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

Somme intérieure. Fixons $i$ . L'indice de sommation est $j$ , donc $i$ est une constante :

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

(la première somme comporte $m$ termes tous égaux à $i$ ).

Somme extérieure. Il reste

\begin{aligned} S & = \sum_{i = 1}^{n} (m i + \frac{m (m + 1)}{2}) \\ = m \sum_{i = 1}^{n} i + n \times \frac{m (m + 1)}{2} \\ = m \times \frac{n (n + 1)}{2} + \frac{n m (m + 1)}{2} \\ = \frac{n m}{2} [(n + 1) + (m + 1)] = \frac{n m (n + m + 2)}{2} \end{aligned}

Contrôle avec $n = 3$ et $m = 2$ : la formule donne $\frac{3 \times 2 \times (3 + 2 + 2)}{2} = \frac{6 \times 7}{2} = 21$ , ce qui est bien le total du tableau ci-dessus. $□$

Exemple

Un cas qui se factorise. Calculons $\sum_{i = 1}^{n} \sum_{j = 1}^{m} i j$ .

Le terme général est le produit de $i$ (qui ne dépend que de $i$ ) et de $j$ (qui ne dépend que de $j$ ). Donc

\sum_{i = 1}^{n} \sum_{j = 1}^{m} i j = (\sum_{i = 1}^{n} i) (\sum_{j = 1}^{m} j) = \frac{n (n + 1)}{2} \times \frac{m (m + 1)}{2} = \frac{n (n + 1) m (m + 1)}{4}

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

Venons-en au cas le plus important, celui où le domaine de sommation n'est pas un rectangle.

Propriété

Cas triangulaire : la méthode des deux lectures. Soit $A$ l'ensemble des couples $(i, j)$ d'entiers tels que $1 ⩽ i ⩽ j ⩽ n$ . Alors

\sum_{(i, j) \in A} u_{i, j} = \underset{lecture par colonnes}{\underset{⏟}{\sum_{j = 1}^{n} (\sum_{i = 1}^{j} u_{i, j})}} = \underset{lecture par lignes}{\underset{⏟}{\sum_{i = 1}^{n} (\sum_{j = i}^{n} u_{i, j})}}

On note souvent cette somme $\sum_{1 ⩽ i ⩽ j ⩽ n} u_{i, j}$ .

Justification. Reprenons le tableau à $n$ lignes et $n$ colonnes, mais ne conservons que les cases situées sur la diagonale ou au-dessus, c'est-à-dire celles pour lesquelles $i ⩽ j$ . On obtient un triangle.

Si l'on décide de parcourir ce triangle colonne par colonne, il faut fixer $j$ (qui varie de $1$ à $n$ ) et faire varier $i$ ; la condition $i ⩽ j$ impose alors $1 ⩽ i ⩽ j$ .
Si l'on décide de le parcourir ligne par ligne, il faut fixer $i$ (qui varie de $1$ à $n$ ) et faire varier $j$ ; la condition $i ⩽ j$ impose alors $i ⩽ j ⩽ n$ .

Dans les deux cas, chaque case du triangle est comptée exactement une fois. $□$

Méthode

Traiter une somme sur un domaine triangulaire.

Décrire le domaine par les deux inégalités qui le définissent, ici $1 ⩽ i ⩽ j ⩽ n$ .
Choisir l'ordre de sommation : on somme d'abord sur l'indice « intérieur ». La bonne question est : si je fixe l'un des deux indices, entre quelles bornes varie l'autre ? Ces bornes dépendent alors de l'indice fixé, et c'est normal.
Écrire les bornes intérieures en fonction de l'indice extérieur, jamais l'inverse : dans $\sum_{i = 1}^{n} \sum_{j = i}^{n}$ , la borne $i$ de la somme intérieure vient de l'extérieur, ce qui est licite ; l'écriture inverse $\sum_{j = i}^{n} \sum_{i = 1}^{n}$ n'a aucun sens, car $i$ n'y est pas encore défini.
Contrôler sur $n = 2$ ou $n = 3$ en énumérant les couples à la main.

Les deux lectures donnent le même résultat : on choisit celle qui mène au calcul le plus simple, et l'on peut aussi les faire toutes les deux et comparer, ce qui constitue une vérification très solide.

Exemple

Un exemple entièrement traité, calculé de deux façons. Soit $n ⩾ 1$ . Calculons

S = \sum_{1 ⩽ i ⩽ j ⩽ n} i

Le terme général est $u_{i, j} = i$ : il ne dépend pas de $j$ , mais l'indice $j$ intervient tout de même, à travers le domaine de sommation.

Commençons par énumérer, pour $n = 3$ , les couples $(i, j)$ avec $1 ⩽ i ⩽ j ⩽ 3$ : ce 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$ . Nous devrons retrouver ce nombre.

Première lecture : par lignes (on fixe $i$ , et $j$ varie de $i$ à $n$ ).

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

Dans la somme intérieure, le terme $i$ est constant et le nombre de termes vaut $n - i + 1$ . Donc

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

Par conséquent, en développant puis en utilisant les sommes usuelles :

\begin{aligned} S & = \sum_{i = 1}^{n} i (n + 1 - i) = \sum_{i = 1}^{n} [(n + 1) i - i^{2}] \\ = (n + 1) \sum_{i = 1}^{n} i - \sum_{i = 1}^{n} i^{2} \\ = (n + 1) \times \frac{n (n + 1)}{2} - \frac{n (n + 1) (2 n + 1)}{6} \\ = n (n + 1) [\frac{n + 1}{2} - \frac{2 n + 1}{6}] \\ = n (n + 1) \times \frac{3 (n + 1) - (2 n + 1)}{6} \\ = n (n + 1) \times \frac{n + 2}{6} = \frac{n (n + 1) (n + 2)}{6} \end{aligned}

Seconde lecture : par colonnes (on fixe $j$ , et $i$ varie de $1$ à $j$ ).

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

en appliquant la formule usuelle à la somme intérieure. Puis, par linéarité :

\begin{aligned} S & = \frac{1}{2} \sum_{j = 1}^{n} (j^{2} + j) = \frac{1}{2} (\sum_{j = 1}^{n} j^{2} + \sum_{j = 1}^{n} j) \\ = \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) (2 n + 4)}{12} = \frac{n (n + 1) (n + 2)}{6} \end{aligned}

Les deux lectures donnent le même résultat, ce qui constitue une excellente vérification :

\sum_{1 ⩽ i ⩽ j ⩽ n} i = \frac{n (n + 1) (n + 2)}{6}

Contrôle pour $n = 3$ : la formule donne $\frac{3 \times 4 \times 5}{6} = 10$ , ce qui correspond bien à l'énumération faite au début. $□$

Exemple

Compter les couples. En prenant $u_{i, j} = 1$ dans le cas triangulaire, on obtient le nombre de couples $(i, j)$ tels que $1 ⩽ i ⩽ j ⩽ n$ :

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

Contrôle pour $n = 3$ : nous avons énuméré $6$ couples plus haut, et $\frac{3 \times 4}{2} = 6$ . $□$

Remarque

Le lien entre le carré et le triangle. Soient $a_{1}, \dots, a_{n}$ des réels. Le domaine carré ${1, \dots, n} \times {1, \dots, n}$ se décompose en trois morceaux : le triangle strict $i < j$ , la diagonale $i = j$ , et le triangle strict $i > j$ . En sommant $a_{i} a_{j}$ sur le carré :

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

Or les deux sommes sur les triangles stricts sont égales : elles portent sur la même quantité $a_{i} a_{j} = a_{j} a_{i}$ , à un échange des noms des indices près. En les notant toutes deux $D$ , on obtient ${(\sum a_{i})}^{2} = 2 D + \sum a_{i}^{2}$ , d'où

\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}]

Contrôle avec $n = 3$ et $(a_{1}, a_{2}, a_{3}) = (1, 2, 3)$ : le membre de gauche vaut $1 \times 2 + 1 \times 3 + 2 \times 3 = 11$ ; le membre de droite vaut $\frac{6^{2} - 14}{2} = \frac{22}{2} = 11$ . Cette identité, très utile, illustre bien la puissance de la décomposition d'un domaine de sommation.

Ensembles

Nous abordons maintenant le vocabulaire qui servira de support à tout le reste de l'année. Il n'est pas question de construire une théorie des ensembles : nous adoptons le point de vue intuitif, qui suffit très largement, et nous nous concentrons sur les règles de calcul et sur la rédaction.

Ensembles, éléments, appartenance

Définition

Un ensemble est une collection d'objets, appelés ses éléments. Si $x$ est un élément de l'ensemble $E$ , on dit que $x$ appartient à $E$ et on note $x \in E$ . Dans le cas contraire, on note $x \notin E$ .

Deux ensembles sont égaux lorsqu'ils ont exactement les mêmes éléments.

L'ensemble qui ne contient aucun élément s'appelle l'ensemble vide et se note $\emptyset$ .

Les ensembles de nombres usuels vous sont déjà familiers :

N \subset Z \subset Q \subset R

où $N$ est l'ensemble des entiers naturels, $Z$ celui des entiers relatifs, $Q$ celui des rationnels et $R$ celui des réels. On note $N^{*}$ , $Z^{*}$ , $R^{*}$ ces ensembles privés de $0$ , et $R_{+}$ l'ensemble des réels positifs.

Définition

Il y a deux manières de décrire un ensemble.

En extension : on écrit la liste de ses éléments entre accolades, par exemple $A = {2, 3, 5, 7}$ . L'ordre n'a pas d'importance et les répétitions ne comptent pas : ${1, 2}$ , ${2, 1}$ et ${1, 2, 2}$ désignent le même ensemble.
En compréhension : on décrit ses éléments par une propriété caractéristique, par exemple

B = {x \in R; x^{2} ⩽ 4}

qui se lit « l'ensemble des réels $x$ tels que $x^{2} ⩽ 4$ », et qui n'est autre que l'intervalle $[- 2, 2]$ .

Exemple

a. ${n \in N; n est pair et n ⩽ 9} = {0, 2, 4, 6, 8}$ : le même ensemble, décrit en compréhension puis en extension.

b. ${x \in R; x^{2} = 4} = {- 2, 2}$ .

c. ${x \in R; x^{2} = - 1} = \emptyset$ : aucun réel n'a un carré strictement négatif. Un ensemble décrit en compréhension peut parfaitement être vide, et c'est souvent la conclusion d'un exercice.

d. ${x \in R; x^{2} ⩾ 0} = R$ : à l'inverse, la condition peut ne rien exclure du tout.

Remarque

Ne confondez pas $\emptyset$ et ${\emptyset}$ ni $0$ et ${0}$ . L'ensemble vide $\emptyset$ n'a aucun élément ; l'ensemble ${\emptyset}$ en a un (à savoir l'ensemble vide) ; l'ensemble ${0}$ en a un aussi (à savoir le nombre $0$ ). Écrire $\emptyset = {0}$ est une faute grave : un ensemble sans élément n'est pas un ensemble contenant $0$ . De même, ne notez jamais l'ensemble vide « ${\emptyset}$ » : c'est une erreur courante et immédiatement repérée.

Inclusion et égalité

Définition

Soient $E$ et $F$ deux ensembles. On dit que $E$ est inclus dans $F$ , ou que $E$ est une partie (ou un sous-ensemble) de $F$ , et on note $E \subset F$ , lorsque tout élément de $E$ est aussi un élément de $F$ , c'est-à-dire lorsque

\forall x, (x \in E ⟹ x \in F)

Propriété

Soient $E$ , $F$ , $G$ trois ensembles.

$\emptyset \subset E$ et $E \subset E$ .
Transitivité : si $E \subset F$ et $F \subset G$ , alors $E \subset G$ .
Antisymétrie : $E = F$ si et seulement si $E \subset F$ et $F \subset E$ .

Démonstration.

Point 1. L'inclusion $\emptyset \subset E$ signifie « pour tout $x$ , si $x \in \emptyset$ , alors $x \in E$ ». L'hypothèse $x \in \emptyset$ étant toujours fausse, l'implication est toujours vraie (revoyez la table de vérité de l'implication). L'inclusion $E \subset E$ est immédiate : si $x \in E$ , alors $x \in E$ .

Point 2. Supposons $E \subset F$ et $F \subset G$ . Soit $x \in E$ . Comme $E \subset F$ , on a $x \in F$ . Comme $F \subset G$ , on a $x \in G$ . Donc tout élément de $E$ est dans $G$ : $E \subset G$ .

Point 3. Si $E = F$ , les deux ensembles ont les mêmes éléments, donc chacun est inclus dans l'autre. Réciproquement, supposons $E \subset F$ et $F \subset E$ . Soit $x$ un objet quelconque. Si $x \in E$ , alors $x \in F$ par la première inclusion ; si $x \in F$ , alors $x \in E$ par la seconde. Donc $x \in E$ et $x \in F$ sont deux propositions équivalentes : les deux ensembles ont exactement les mêmes éléments, donc $E = F$ . $□$

Le point 3 est la justification de la méthode par double inclusion énoncée dans la section sur les modes de raisonnement, et que nous utiliserons systématiquement.

Remarque

La confusion $\in$ / $\subset$ : le piège numéro un du chapitre.

Ces deux symboles ne relient pas les mêmes objets.

$x \in E$ relie un élément à un ensemble : « $x$ est l'un des objets de la collection $E$ ».
$A \subset E$ relie deux ensembles : « tous les objets de $A$ sont dans $E$ ».

Prenons $E = {1, 2, 3}$ . Alors :

1 \in E (vrai) {1} \subset E (vrai) 1 \subset E (n’a pas de sens) {1} \in E (faux)

La dernière est fausse parce que les éléments de $E$ sont les nombres $1$ , $2$ et $3$ , et non l'ensemble ${1}$ . On retiendra la formule : $1$ est dans $E$ , mais ${1}$ est une partie de $E$ . Un correcteur repère une confusion $\in$ / $\subset$ en une seconde, et elle est très mal notée : elle signale que l'étudiant ne sait pas de quel type d'objet il parle.

L'ensemble des parties

Définition

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

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

C'est un objet un peu déroutant au premier abord, car ses éléments sont eux-mêmes des ensembles. L'équivalence ci-dessus est à connaître par cœur : elle est le pont entre les deux symboles $\in$ et $\subset$ .

Exemple

Toutes les parties d'un ensemble à trois éléments. Prenons $E = {a, b, c}$ . Dressons la liste complète de ses parties, en les classant par nombre d'éléments.

La partie à $0$ élément : $\emptyset$ .
Les parties à $1$ élément : ${a}$ , ${b}$ , ${c}$ .
Les parties à $2$ éléments : ${a, b}$ , ${a, c}$ , ${b, c}$ .
La partie à $3$ éléments : ${a, b, c}$ , c'est-à-dire $E$ lui-même.

Donc

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

Cet ensemble a huit éléments, alors que $E$ n'en a que trois. Vérifions au passage quelques affirmations :

a \in E mais a \notin P (E) {a} \subset E et {a} \in P (E)

\emptyset \in P (E) E \in P (E) {{a}} \subset P (E)

La dernière ligne mérite une lecture lente : ${a}$ est un élément de $P (E)$ , donc l'ensemble dont l'unique élément est ${a}$ , à savoir ${{a}}$ , est une partie de $P (E)$ .

Remarque

Sur cet exemple, $E$ a $3$ éléments et $P (E)$ en a $8 = 2^{3}$ . Ce n'est pas un hasard : on démontrera dans le chapitre de dénombrement que si $E$ possède $n$ éléments, alors $P (E)$ en possède $2^{n}$ . Nous admettons ce résultat ici, et nous nous contentons de l'avoir observé.

Notez enfin que $P (E)$ n'est jamais vide, même si $E$ l'est : $P (\emptyset) = {\emptyset}$ , un ensemble à un élément.

Réunion, intersection, complémentaire, différence

Définition

Soient $A$ et $B$ deux parties d'un même ensemble $E$ .

La réunion de $A$ et $B$ est $A \cup B = {x \in E; x \in A ou x \in B}$ .
L'intersection de $A$ et $B$ est $A \cap B = {x \in E; x \in A et x \in B}$ .
Le complémentaire de $A$ dans $E$ est $\overline{A} = {x \in E; x \notin A}$ .
La différence de $A$ et $B$ est $A ∖ B = {x \in E; x \in A et x \notin B}$ .

Lorsque $A \cap B = \emptyset$ , on dit que $A$ et $B$ sont disjoints.

Autrement dit, pour tout $x \in E$ :

x \in A \cup B ⟺ (x \in A ou x \in B) x \in A \cap B ⟺ (x \in A et x \in B)

x \in \overline{A} ⟺ x \notin A x \in A ∖ B ⟺ (x \in A et x \notin B)

Remarque

Tout le calcul ensembliste est du calcul logique déguisé. Les quatre équivalences ci-dessus traduisent :

la réunion en « ou » ;
l'intersection en « et » ;
le complémentaire en « non » ;
la différence en « et non », d'où l'écriture $A ∖ B = A \cap \overline{B}$ .

C'est pourquoi les propriétés de la section suivante (distributivité, lois de De Morgan) sont exactement celles que nous avons démontrées sur les connecteurs. Une seule chose à retenir vraiment, donc, et deux vocabulaires pour la dire.

Attention à un détail de notation : le complémentaire $\overline{A}$ n'a de sens que relativement à un ensemble de référence $E$ , qui doit être connu du lecteur. Si le contexte ne le précise pas, on écrit $E ∖ A$ , qui est sans ambiguïté.

Exemple

Prenons $E = {1, 2, 3, 4, 5, 6}$ , $A = {1, 2, 3}$ et $B = {3, 4}$ . Alors

A \cup B = {1, 2, 3, 4} A \cap B = {3}

\overline{A} = {4, 5, 6} \overline{B} = {1, 2, 5, 6}

A ∖ B = {1, 2} B ∖ A = {4}

Observez que $A ∖ B \neq B ∖ A$ : la différence n'est pas symétrique, contrairement à la réunion et à l'intersection.

Propriété

Soient $A$ , $B$ , $C$ des parties d'un ensemble $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)$ .
Éléments neutres et absorbants : $A \cup \emptyset = A$ , $A \cap \emptyset = \emptyset$ , $A \cup E = E$ , $A \cap E = A$ .
Complémentaire : $A \cup \overline{A} = E$ , $A \cap \overline{A} = \emptyset$ , $\overline{\overline{A}} = A$ .
Inclusions : $A \cap B \subset A \subset A \cup B$ .
Distributivité :

A \cap (B \cup C) = (A \cap B) \cup (A \cap C) 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} \overline{A \cap B} = \overline{A} \cup \overline{B}

Nous démontrons intégralement une distributivité et les deux lois de De Morgan ; les autres points se traitent de la même façon, en revenant à la définition et aux règles logiques correspondantes.

Démonstration de la première distributivité, par double inclusion. Montrons que

A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

Première inclusion : $A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C)$ .

Soit $x \in A \cap (B \cup C)$ . Par définition de l'intersection, $x \in A$ et $x \in B \cup C$ . Par définition de la réunion, cette seconde appartenance signifie $x \in B$ ou $x \in C$ . Distinguons donc deux cas.

Premier cas : $x \in B$ . Comme on a aussi $x \in A$ , on en déduit $x \in A \cap B$ , donc a fortiori $x \in (A \cap B) \cup (A \cap C)$ .

Second cas : $x \in C$ . Comme on a aussi $x \in A$ , on en déduit $x \in A \cap C$ , donc à nouveau $x \in (A \cap B) \cup (A \cap C)$ .

Dans les deux cas, $x$ appartient à $(A \cap B) \cup (A \cap C)$ . La première inclusion est établie.

Seconde inclusion : $(A \cap B) \cup (A \cap C) \subset A \cap (B \cup C)$ .

Soit $x \in (A \cap B) \cup (A \cap C)$ . Par définition de la réunion, $x \in A \cap B$ ou $x \in A \cap C$ . Distinguons à nouveau deux cas.

Premier cas : $x \in A \cap B$ . Alors $x \in A$ et $x \in B$ . De $x \in B$ on déduit $x \in B \cup C$ . Donc $x \in A$ et $x \in B \cup C$ , c'est-à-dire $x \in A \cap (B \cup C)$ .

Second cas : $x \in A \cap C$ . Alors $x \in A$ et $x \in C$ , donc $x \in B \cup C$ , et l'on conclut de même que $x \in A \cap (B \cup C)$ .

Dans les deux cas, $x$ appartient à $A \cap (B \cup C)$ . La seconde inclusion est établie.

Conclusion. Par double inclusion, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ . $□$

Démonstration des lois de De Morgan. Soit $x \in E$ . Procédons par équivalences successives, en traduisant à chaque étape une définition ensembliste en énoncé logique, et réciproquement.

Première loi.

\begin{aligned} x \in \overline{A \cup B} & ⟺ x \notin A \cup B & d \overset{ˊ}{e} finition du compl \overset{ˊ}{e} mentaire \\ ⟺ \neg (x \in A ou x \in B) & d \overset{ˊ}{e} finition de la r \overset{ˊ}{e} union \\ ⟺ (x \notin A) et (x \notin B) & loi de De Morgan logique \\ ⟺ x \in \overline{A} et x \in \overline{B} & d \overset{ˊ}{e} finition du compl \overset{ˊ}{e} mentaire \\ ⟺ x \in \overline{A} \cap \overline{B} & d \overset{ˊ}{e} finition de l’intersection \end{aligned}

Comme $x$ était un élément quelconque de $E$ , les deux ensembles $\overline{A \cup B}$ et $\overline{A} \cap \overline{B}$ ont les mêmes éléments : ils sont égaux.

Seconde loi. Le raisonnement est identique, en échangeant les rôles des deux connecteurs.

\begin{aligned} x \in \overline{A \cap B} & ⟺ \neg (x \in A et x \in B) \\ ⟺ (x \notin A) ou (x \notin B) \\ ⟺ x \in \overline{A} ou x \in \overline{B} \\ ⟺ x \in \overline{A} \cup \overline{B} \end{aligned}

D'où $\overline{A \cap B} = \overline{A} \cup \overline{B}$ . $□$

Remarque

La chaîne d'équivalences est ici parfaitement licite, parce que chaque étape est une traduction (une définition lue dans un sens puis dans l'autre) ou une règle logique déjà démontrée. C'est exactement le cas de figure où cette rédaction est préférable à la double inclusion : elle est plus courte et plus lisible. Dans un exercice où les ensembles sont donnés par des conditions concrètes, la double inclusion reste plus prudente.

Retenez le résumé, valable en probabilités mot pour mot : le complémentaire d'une réunion est l'intersection des complémentaires, et le complémentaire d'une intersection est la réunion des complémentaires. Un « ou » nié devient un « et ».

Exemple

Vérification sur un cas concret. Reprenons $E = {1, 2, 3, 4, 5, 6}$ , $A = {1, 2, 3}$ et $B = {3, 4}$ .

D'un côté, $A \cup B = {1, 2, 3, 4}$ , donc $\overline{A \cup B} = {5, 6}$ .

De l'autre, $\overline{A} = {4, 5, 6}$ et $\overline{B} = {1, 2, 5, 6}$ , donc $\overline{A} \cap \overline{B} = {5, 6}$ .

Les deux coïncident. De même, $A \cap B = {3}$ donne $\overline{A \cap B} = {1, 2, 4, 5, 6}$ , et $\overline{A} \cup \overline{B} = {4, 5, 6} \cup {1, 2, 5, 6} = {1, 2, 4, 5, 6}$ . Cela ne démontre rien (un exemple n'est pas une preuve), mais c'est un bon moyen de vérifier qu'on n'a pas inversé les deux formules.

Le produit cartésien

Définition

Soient $E$ et $F$ deux ensembles. Le produit cartésien de $E$ par $F$ , noté $E \times F$ , est l'ensemble des couples $(x, y)$ où $x \in E$ et $y \in F$ :

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

Deux couples sont égaux lorsque leurs deux composantes le sont :

(x, y) = (x^{'}, y^{'}) ⟺ (x = x^{'} et y = y^{'})

Lorsque $E = F$ , on note $E^{2} = E \times E$ , et plus généralement $E^{n}$ l'ensemble des $n$ -uplets $(x_{1}, x_{2}, \dots, x_{n})$ dont toutes les composantes appartiennent à $E$ .

Remarque

Un couple n'est pas une paire. Dans un couple, l'ordre compte : $(1, 2)$ et $(2, 1)$ sont deux couples différents, alors que les ensembles ${1, 2}$ et ${2, 1}$ sont égaux. De même, $(1, 1)$ est un couple parfaitement légitime, alors que ${1, 1} = {1}$ n'a qu'un élément. C'est la raison pour laquelle on utilise des parenthèses pour les couples et des accolades pour les ensembles : la distinction typographique porte une différence de sens.

Conséquence : en général, $E \times F \neq F \times E$ .

Exemple

a. Avec $E = {1, 2}$ et $F = {a, b, c}$ :

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

Cet ensemble a $6 = 2 \times 3$ éléments. On peut le disposer en tableau à $2$ lignes et $3$ colonnes, ce qui explique le nom de « produit ». C'est exactement la structure qui sous-tend les sommes doubles rectangulaires de la section précédente.

b. $R^{2} = R \times R$ est l'ensemble des couples de réels. Muni d'un repère, il s'identifie au plan : le couple $(x, y)$ est le point d'abscisse $x$ et d'ordonnée $y$ . C'est le cadre de toute la géométrie analytique que vous connaissez, et ce sera celui de l'optimisation à deux variables en deuxième année.

c. $R^{3}$ s'identifie de même à l'espace, et $R^{n}$ est l'ensemble des listes ordonnées de $n$ réels. En économie, un élément de $R^{n}$ décrit couramment un panier de $n$ biens, ou les $n$ coordonnées d'un individu dans un jeu de données.

d. $N^{2}$ est l'ensemble des couples d'entiers naturels : c'est précisément l'ensemble dans lequel vivent les indices des sommes doubles.

Exemple

Une lecture géométrique. Dans le plan $R^{2}$ , décrivons l'ensemble

C = [1, 3] \times [0, 2]

Un point $M (x, y)$ appartient à $C$ si et seulement si $1 ⩽ x ⩽ 3$ et $0 ⩽ y ⩽ 2$ . L'ensemble $C$ est donc le rectangle plein dont les côtés sont parallèles aux axes, délimité horizontalement par les droites d'équations $x = 1$ et $x = 3$ , verticalement par les droites d'équations $y = 0$ et $y = 2$ . Ses quatre sommets sont les points de coordonnées $(1, 0)$ , $(3, 0)$ , $(3, 2)$ et $(1, 2)$ .

Ce n'est pas un hasard si le produit cartésien de deux intervalles donne un rectangle : les deux contraintes portent sur des coordonnées indépendantes l'une de l'autre. En revanche, l'ensemble ${(x, y) \in R^{2}; x ⩽ y}$ n'est pas un produit cartésien : la condition lie les deux coordonnées, et l'on obtient un demi-plan. C'est exactement la différence entre le domaine rectangulaire et le domaine triangulaire des sommes doubles.

Remarque

On observe sur l'exemple a. que si $E$ possède $n$ éléments et $F$ en possède $m$ , alors $E \times F$ en possède $n m$ . Nous admettons ce résultat, qui sera démontré dans le chapitre de dénombrement, et nous ne l'utiliserons ici que pour compter des cases dans un tableau.

Applications

Le mot « fonction » vous est familier depuis le lycée, mais son emploi y était assez souple : on disait « la fonction $\frac{1}{x}$ » sans préciser où elle vit. En classe préparatoire, une application est un objet à trois composantes : un ensemble de départ, un ensemble d'arrivée, et une règle. Changer l'une des trois, c'est changer d'objet. Cette exigence n'est pas un formalisme gratuit : nous verrons qu'une même formule peut être bijective ou non selon les ensembles choisis.

Définition, image, antécédent

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$ est l'ensemble de départ, l'ensemble $F$ est l'ensemble d'arrivée.

L'élément $f (x)$ s'appelle l'image de $x$ par $f$ . Chaque élément de $E$ a une image, et une seule.
Étant donné $y \in F$ , tout élément $x \in E$ tel que $f (x) = y$ s'appelle un antécédent de $y$ par $f$ . Un élément de $F$ peut avoir zéro, un, ou plusieurs antécédents.

Le graphe de $f$ est la partie de $E \times F$ définie par $Γ_{f} = {(x, f (x)); x \in E}$ .

Remarque

La dissymétrie entre image et antécédent est le point à retenir, et c'est elle qui produira les notions d'injection et de surjection.

Du côté du départ : chaque $x$ a exactement une image. C'est ce qui fait de $f$ une application ; sinon le procédé n'en est pas une.
Du côté de l'arrivée : un $y$ peut avoir n'importe quel nombre d'antécédents, y compris aucun.

Sur la courbe d'une fonction de $R$ dans $R$ , cela se lit ainsi : toute droite verticale rencontre la courbe en exactement un point (c'est ce qui fait une application), tandis qu'une droite horizontale peut la rencontrer en zéro, un, ou plusieurs points.

Exemple

Considérons $f : R \to R$ , $x \mapsto x^{2}$ .

L'image de $3$ est $f (3) = 9$ . L'image de $- 3$ est également $9$ .
Le réel $9$ admet deux antécédents : $3$ et $- 3$ , car ce sont les deux solutions de $x^{2} = 9$ .
Le réel $0$ admet un seul antécédent : $0$ .
Le réel $- 4$ n'admet aucun antécédent, car $x^{2} = - 4$ n'a pas de solution réelle.

Chercher les antécédents d'un élément $y$ , c'est donc résoudre l'équation $f (x) = y$ d'inconnue $x$ . Toute la suite de la section repose sur cette lecture.

Remarque

Une application n'est pas une formule. Les deux objets suivants sont différents, bien qu'ils partagent la même expression :

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

Nous verrons que la première n'est ni injective ni surjective, alors que la seconde est bijective. La formule est identique, les ensembles changent, les propriétés changent du tout au tout.

Inversement, une formule seule ne définit pas toujours une application : « $x \mapsto \frac{1}{x}$ » n'est pas une application de $R$ dans $R$ , puisque $0$ n'aurait pas d'image. C'en est une de $R^{*}$ dans $R$ . Écrire les ensembles fait partie de la réponse.

Définition

Deux applications $f$ et $g$ sont égales lorsque :

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$ , $f (x) = g (x)$ .

Si $A$ est une partie de $E$ , la restriction de $f$ à $A$ est l'application

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

C'est la même règle, appliquée à un départ plus petit. En toute rigueur, $f_{∣ A}$ et $f$ sont deux applications différentes dès que $A \neq E$ .

Enfin, l'application identité de $E$ est ${i d}_{E} : E \to E$ , $x \mapsto x$ .

La 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))

qui se lit « $g$ rond $f$ ». Pour qu'elle ait un sens, il faut que l'ensemble d'arrivée de $f$ soit l'ensemble de départ de $g$ : on applique $f$ d'abord, $g$ ensuite.

Remarque

L'ordre de lecture est contre-intuitif : dans « $g \circ f$ », c'est $f$ qui agit en premier. On lit de droite à gauche, comme dans l'écriture $g (f (x))$ où la parenthèse la plus intérieure est évaluée d'abord.

Propriété

Associativité de la composition. 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, sans ambiguïté.

Démonstration. Les deux applications ont le même ensemble de départ $E$ et le même ensemble d'arrivée $H$ . Il reste à vérifier qu'elles prennent la même valeur en chaque point. Soit $x \in E$ . D'une part,

[h \circ (g \circ f)] (x) = h ((g \circ f) (x)) = h (g (f (x)))

D'autre part,

[(h \circ g) \circ f] (x) = (h \circ g) (f (x)) = h (g (f (x)))

Les deux résultats sont identiques. Comme $x$ était quelconque, les deux applications sont égales. $□$

Propriété

La composition n'est pas commutative. En général, $g \circ f \neq f \circ g$ , et il arrive même que l'une des deux composées n'ait aucun sens.

Démonstration par contre-exemple. Prenons $f : R \to R$ , $x \mapsto x + 1$ , et $g : R \to R$ , $x \mapsto x^{2}$ . Les deux composées existent, et 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 différentes : pour $x = 1$ , la première vaut $4$ et la seconde vaut $2$ . $□$

Remarque

Un seul point suffit à prouver que deux applications sont différentes : c'est un contre-exemple, et il faut le donner explicitement, avec le calcul. Écrire « $(x + 1)^{2} \neq x^{2} + 1$ » sans plus de précision est insuffisant, puisque les deux expressions coïncident pour $x = 0$ .

Injection

Définition

Soit $f : E \to F$ . On dit que $f$ est injective lorsque deux éléments distincts de $E$ ont toujours des images distinctes, autrement dit lorsque

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

Traduction en termes d'antécédents : tout élément de $F$ admet au plus un antécédent par $f$ .

Remarque

La définition est souvent donnée sous sa forme contraposée, qui dit la même chose :

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

C'est la formulation la plus parlante (« $f$ ne colle jamais deux points ensemble »), mais celle de la définition est de loin la plus commode à utiliser : partir d'une égalité est toujours plus facile que partir d'une différence.

Méthode

Montrer qu'une application est injective.

Soient $x$ et $x^{'}$ deux éléments de $E$ tels que $f (x) = f (x^{'})$ .

[on écrit l'égalité avec les expressions, et on la manipule]

Donc $x = x^{'}$ . L'application $f$ est donc injective.

Réfuter l'injectivité. On exhibe deux éléments distincts de $E$ ayant la même image :

On a $f (- 1) = f (1) = 1$ alors que $- 1 \neq 1$ . Donc $f$ n'est pas injective.

Il faut bien vérifier que les deux éléments choisis appartiennent à l'ensemble de départ : c'est là que se joue la différence entre $x \mapsto x^{2}$ sur $R$ et sur $R_{+}$ .

Exemple

a. L'application $f : R \to R$ , $x \mapsto 2 x + 1$ est injective.

Soient $x$ et $x^{'}$ deux réels tels que $f (x) = f (x^{'})$ . Alors $2 x + 1 = 2 x^{'} + 1$ , donc $2 x = 2 x^{'}$ , donc $x = x^{'}$ en divisant par $2$ . L'application $f$ est injective. $□$

b. L'application $g : R \to R$ , $x \mapsto x^{2}$ n'est pas injective.

En effet, $- 2$ et $2$ sont deux réels distincts, et pourtant $g (- 2) = 4 = g (2)$ . $□$

c. L'application $h : R_{+} \to R$ , $x \mapsto x^{2}$ est injective.

Soient $x$ et $x^{'}$ deux réels positifs tels que $x^{2} = x^{' 2}$ . Alors $x^{2} - x^{' 2} = 0$ , c'est-à-dire $(x - x^{'}) (x + x^{'}) = 0$ . Donc $x = x^{'}$ ou $x = - x^{'}$ . Dans le second cas, comme $x ⩾ 0$ et $x^{'} ⩾ 0$ , on a $x = - x^{'} ⩽ 0$ et donc $x = 0$ , puis $x^{'} = 0$ : là encore $x = x^{'}$ . Dans tous les cas, $x = x^{'}$ , donc $h$ est injective. $□$

Comparez b. et c. : c'est la même formule. Restreindre le départ à $R_{+}$ a supprimé le seul obstacle à l'injectivité.

Surjection

Définition

Soit $f : E \to F$ . On dit que $f$ est surjective lorsque tout élément de l'ensemble d'arrivée est atteint, autrement dit lorsque

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

Traduction en termes d'antécédents : tout élément de $F$ admet au moins un antécédent par $f$ .

Méthode

Montrer qu'une application est surjective. C'est un problème de résolution d'équation : on se donne $y$ dans l'arrivée, et on cherche un $x$ dans le départ tel que $f (x) = y$ .

Soit $y \in F$ . Cherchons $x \in E$ tel que $f (x) = y$ .

[on résout l'équation $f (x) = y$ d'inconnue $x$ , en exprimant $x$ en fonction de $y$ ]

Posons $x = \dots$ . Cet élément appartient bien à $E$ [le vérifier !], et $f (x) = y$ [le vérifier par le calcul]. Donc $f$ est surjective.

Deux vérifications sont exigibles et souvent oubliées : que le $x$ trouvé est bien dans l'ensemble de départ, et qu'il vérifie bien $f (x) = y$ .

Réfuter la surjectivité. On exhibe un élément de l'arrivée sans antécédent :

Le réel $- 1$ appartient à l'ensemble d'arrivée $R$ , et l'équation $x^{2} = - 1$ n'a pas de solution réelle. Donc $f$ n'est pas surjective.

Exemple

a. L'application $f : R \to R$ , $x \mapsto 2 x + 1$ est surjective.

Soit $y \in R$ . Résolvons $2 x + 1 = y$ : cette équation équivaut à $x = \frac{y - 1}{2}$ . Posons donc $x = \frac{y - 1}{2}$ . C'est bien un réel, donc un élément de l'ensemble de départ, et

f (x) = 2 \times \frac{y - 1}{2} + 1 = (y - 1) + 1 = y

Donc $y$ admet un antécédent, et $f$ est surjective. $□$

b. L'application $g : R \to R$ , $x \mapsto x^{2}$ n'est pas surjective : le réel $- 1$ appartient à l'ensemble d'arrivée et n'a pas d'antécédent, puisqu'un carré de réel n'est jamais strictement négatif. $□$

c. L'application $k : R \to R_{+}$ , $x \mapsto x^{2}$ est surjective.

Soit $y \in R_{+}$ . Comme $y ⩾ 0$ , le réel $\sqrt{y}$ est bien défini, et $k (\sqrt{y}) = {(\sqrt{y})}^{2} = y$ . Donc $y$ a un antécédent, et $k$ est surjective. $□$

Comparez b. et c. : à nouveau la même formule. Cette fois, c'est la réduction de l'ensemble d'arrivée qui a rendu l'application surjective. Rétrécir l'arrivée favorise la surjectivité ; rétrécir le départ favorise l'injectivité.

Remarque

Récapitulons ce que les ensembles font à la formule $x \mapsto x^{2}$ .

Application	Injective	Surjective
$R \to R$	non	non
$R_{+} \to R$	oui	non
$R \to R_{+}$	non	oui
$R_{+} \to R_{+}$	oui	oui

Ce tableau est à méditer : on ne demande jamais « la fonction carré est-elle injective ? » sans préciser les ensembles. La question n'aurait pas de sens.

Bijection

Définition

Soit $f : E \to F$ . On dit que $f$ est bijective lorsqu'elle est à la fois injective et surjective, c'est-à-dire lorsque

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

Traduction : tout élément de $F$ admet exactement un antécédent par $f$ .

L'équivalence entre les deux formulations est immédiate : « au moins un » (surjectivité) et « au plus un » (injectivité) réunis donnent « exactement un ».

Méthode

Montrer qu'une application est bijective. Deux stratégies.

Stratégie 1 : séparément. On démontre l'injectivité, puis la surjectivité, avec les deux méthodes ci-dessus. C'est long mais toujours faisable.

Stratégie 2 : par résolution de l'équation (la plus efficace). On traite les deux d'un coup :

Soit $y \in F$ . Résolvons l'équation $f (x) = y$ d'inconnue $x \in E$ .

[chaîne d'équivalences] $f (x) = y ⟺ \dots ⟺ x = φ (y)$

L'équation admet donc une solution et une seule dans $E$ , à savoir $x = φ (y)$ . Comme $y$ était quelconque, tout élément de $F$ a exactement un antécédent : $f$ est bijective, et sa réciproque est $y \mapsto φ (y)$ .

Cette seconde stratégie a un avantage décisif : elle fournit la réciproque en même temps que la bijectivité. C'est presque toujours celle qu'il faut employer. Sa seule exigence est la rigueur de la chaîne d'équivalences : chaque étape doit être réversible, et il faut vérifier que la solution trouvée est bien dans $E$ .

L'application réciproque

Définition

Soit $f : E \to F$ une application bijective. Pour chaque $y \in F$ , il existe un unique $x \in E$ tel que $f (x) = y$ . On peut donc définir une application

f^{- 1} : F \to E

qui à chaque $y \in F$ associe cet unique antécédent. On l'appelle l'application réciproque de $f$ .

Remarque

Deux avertissements de notation.

Le symbole $f^{- 1}$ ne désigne jamais $\frac{1}{f}$ . L'application réciproque de $x \mapsto 2 x + 1$ est $y \mapsto \frac{y - 1}{2}$ , et certainement pas $x \mapsto \frac{1}{2 x + 1}$ .
L'écriture $f^{- 1}$ suppose $f$ bijective. Tant que la bijectivité n'est pas établie, on n'a pas le droit d'écrire ce symbole.

Propriété

Caractérisation d'une bijection. Soit $f : E \to F$ une application. Les deux propositions 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, une telle application $g$ est alors unique et vaut $f^{- 1}$ . Autrement dit,

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

Démonstration.

Le point 1 entraîne le point 2. Supposons $f$ bijective et posons $g = f^{- 1}$ . Soit $x \in E$ . L'élément $f (x)$ appartient à $F$ , et son unique antécédent est $x$ par construction ; donc $f^{- 1} (f (x)) = x$ . Ainsi $f^{- 1} \circ f = {i d}_{E}$ . Soit maintenant $y \in F$ . Par définition, $f^{- 1} (y)$ est l'unique antécédent de $y$ , donc $f (f^{- 1} (y)) = y$ . Ainsi $f \circ f^{- 1} = {i d}_{F}$ .

Le point 2 entraîne le point 1. Supposons qu'une telle application $g$ existe.

Injectivité. 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^{'})$ , c'est-à-dire $x = x^{'}$ puisque $g \circ f = {i d}_{E}$ . Donc $f$ est injective.

Surjectivité. Soit $y \in F$ . Posons $x = g (y)$ , qui est un élément de $E$ . Alors $f (x) = f (g (y)) = (f \circ g) (y) = y$ puisque $f \circ g = {i d}_{F}$ . Donc $y$ a un antécédent, et $f$ est surjective.

Ainsi $f$ est bijective.

Unicité de $g$ . Supposons que deux applications $g$ et $h$ de $F$ dans $E$ vérifient toutes deux les conditions du point 2. Alors, en utilisant l'associativité de la composition :

g = g \circ {i d}_{F} = g \circ (f \circ h) = (g \circ f) \circ h = {i d}_{E} \circ h = h

Donc $g = h$ , et comme $f^{- 1}$ convient, cette unique application est $f^{- 1}$ . $□$

Remarque

Cette caractérisation est un outil de démonstration très puissant : pour établir qu'une application est bijective et identifier sa réciproque, il suffit d'exhiber une candidate $g$ et de vérifier les deux compositions. Aucune résolution d'équation n'est nécessaire. Nous l'utiliserons dans un instant pour la réciproque d'une composée.

Attention toutefois : les deux égalités sont nécessaires. Une seule des deux ne suffit pas à garantir la bijectivité.

Exemple

Un exemple entièrement traité : une homographie. Considérons

f : R ∖ {3} \to R, x \mapsto \frac{2 x + 1}{x - 3}

L'application est bien définie : pour $x \neq 3$ , le dénominateur $x - 3$ est non nul.

Question : $f$ est-elle bijective ? Sinon, sur quel ensemble d'arrivée le devient-elle, et quelle est alors sa réciproque ?

Résolution de l'équation $f (x) = y$ . Soit $y \in R$ . Pour $x \in R ∖ {3}$ , on a $x - 3 \neq 0$ , donc on peut multiplier par $x - 3$ sans perdre d'information :

\begin{aligned} \frac{2 x + 1}{x - 3} = y & ⟺ 2 x + 1 = y (x - 3) \\ ⟺ 2 x + 1 = y x - 3 y \\ ⟺ 2 x - y x = - 3 y - 1 \\ ⟺ x (2 - y) = - (3 y + 1) \\ ⟺ x (y - 2) = 3 y + 1 \end{aligned}

Discutons selon la valeur de $y$ .

Cas $y = 2$ . L'équation devient $0 = 3 \times 2 + 1 = 7$ , ce qui est impossible. Le réel $2$ n'a donc aucun antécédent : $f$ n'est pas surjective de $R ∖ {3}$ dans $R$ .

Cas $y \neq 2$ . On peut diviser par $y - 2$ , et l'équation équivaut à

x = \frac{3 y + 1}{y - 2}

Il y a donc au plus une solution. Vérifions qu'elle appartient bien à l'ensemble de départ, c'est-à-dire qu'elle est différente de $3$ . Si l'on avait $\frac{3 y + 1}{y - 2} = 3$ , alors $3 y + 1 = 3 (y - 2) = 3 y - 6$ , d'où $1 = - 6$ , ce qui est absurde. Donc $\frac{3 y + 1}{y - 2} \neq 3$ : la solution est bien dans $R ∖ {3}$ .

Conclusion. L'application

f : R ∖ {3} \to R ∖ {2}, x \mapsto \frac{2 x + 1}{x - 3}

est bijective, et sa réciproque est

f^{- 1} : R ∖ {2} \to R ∖ {3}, y \mapsto \frac{3 y + 1}{y - 2}

Vérification par les deux compositions. Soit $x \in R ∖ {3}$ . En posant $y = \frac{2 x + 1}{x - 3}$ :

\begin{aligned} f^{- 1} (f (x)) & = \frac{3 \times \frac{2 x + 1}{x - 3} + 1}{\frac{2 x + 1}{x - 3} - 2} = \frac{\frac{3 (2 x + 1) + (x - 3)}{x - 3}}{\frac{(2 x + 1) - 2 (x - 3)}{x - 3}} \\ = \frac{6 x + 3 + x - 3}{2 x + 1 - 2 x + 6} = \frac{7 x}{7} = x \end{aligned}

Soit maintenant $y \in R ∖ {2}$ :

\begin{aligned} f (f^{- 1} (y)) & = \frac{2 \times \frac{3 y + 1}{y - 2} + 1}{\frac{3 y + 1}{y - 2} - 3} = \frac{\frac{2 (3 y + 1) + (y - 2)}{y - 2}}{\frac{(3 y + 1) - 3 (y - 2)}{y - 2}} \\ = \frac{6 y + 2 + y - 2}{3 y + 1 - 3 y + 6} = \frac{7 y}{7} = y \end{aligned}

Les deux compositions donnent bien l'identité. $□$

Contrôle numérique : $f (4) = \frac{9}{1} = 9$ , et $f^{- 1} (9) = \frac{28}{7} = 4$ . De même $f (0) = \frac{1}{- 3} = - \frac{1}{3}$ , et $f^{- 1} (- \frac{1}{3}) = \frac{- 1 + 1}{- \frac{1}{3} - 2} = 0$ .

Remarque

Le réflexe du domaine. Sur cet exemple, deux valeurs jouent un rôle particulier : $3$ , qui est exclue du départ (le dénominateur s'annule), et $2$ , qui est exclue de l'arrivée (aucun antécédent). Ce n'est pas une coïncidence : pour une homographie $x \mapsto \frac{a x + b}{c x + d}$ avec $c \neq 0$ , la valeur exclue du départ est $- \frac{d}{c}$ et celle exclue de l'arrivée est $\frac{a}{c}$ . Ici, $- \frac{- 3}{1} = 3$ et $\frac{2}{1} = 2$ . Vous pouvez utiliser cette observation comme contrôle, jamais comme démonstration.

Composée de deux bijections, réciproque de la composée

Propriété

Soient $f : E \to F$ et $g : F \to G$ deux applications bijectives. Alors $g \circ f : E \to G$ est bijective, et

{(g \circ f)}^{- 1} = f^{- 1} \circ g^{- 1}

Notez l'inversion de l'ordre : la réciproque de la composée compose les réciproques dans l'autre sens.

Démonstration. Comme $f$ et $g$ sont bijectives, les applications $f^{- 1} : F \to E$ et $g^{- 1} : G \to F$ existent. Posons

h = f^{- 1} \circ g^{- 1} : G \to E

qui est bien définie (l'arrivée de $g^{- 1}$ est $F$ , qui est le départ de $f^{- 1}$ ). Nous allons vérifier les deux égalités de la caractérisation démontrée plus haut, en utilisant librement l'associativité de la composition.

Première composition.

\begin{aligned} h \circ (g \circ f) & = (f^{- 1} \circ g^{- 1}) \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} \end{aligned}

Seconde composition.

\begin{aligned} (g \circ f) \circ h & = (g \circ f) \circ (f^{- 1} \circ g^{- 1}) \\ = g \circ (f \circ f^{- 1}) \circ g^{- 1} \\ = g \circ {i d}_{F} \circ g^{- 1} \\ = g \circ g^{- 1} = {i d}_{G} \end{aligned}

D'après la caractérisation d'une bijection, l'application $g \circ f$ est donc bijective et sa réciproque est $h$ , c'est-à-dire

{(g \circ f)}^{- 1} = f^{- 1} \circ g^{- 1} □

Remarque

Le moyen mnémotechnique classique est celui des chaussettes et des chaussures. Pour s'habiller, on enfile les chaussettes ( $f$ ) puis les chaussures ( $g$ ). Pour se déshabiller, on retire d'abord les chaussures ( $g^{- 1}$ ), ensuite les chaussettes ( $f^{- 1}$ ). On défait dans l'ordre inverse.

Erreur à éviter : écrire $(g \circ f)^{- 1} = g^{- 1} \circ f^{- 1}$ . Le plus souvent, cette composée n'a même aucun sens. En effet, dans $g^{- 1} \circ f^{- 1}$ , c'est $f^{- 1}$ qui agirait en premier : elle arrive dans $E$ , alors que $g^{- 1}$ part de $G$ . Il faudrait donc $E = G$ , ce qui n'a aucune raison d'être vrai. Vérifier la cohérence des ensembles suffit à détecter la faute.

Exemple

Application concrète. Soient

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

Ces deux applications sont bijectives : nous l'avons établi pour $f$ , et pour $g$ c'est un résultat du lycée que nous admettons, la réciproque étant le logarithme népérien. Leurs réciproques sont donc

f^{- 1} (y) = \frac{y - 1}{2} et g^{- 1} (y) = \ln y

La composée vaut $(g \circ f) (x) = e^{2 x + 1}$ , et c'est une application de $R$ dans $R_{+}^{*}$ . D'après la propriété, sa réciproque est

{(g \circ f)}^{- 1} (y) = (f^{- 1} \circ g^{- 1}) (y) = f^{- 1} (\ln y) = \frac{\ln y - 1}{2}

Vérification directe. Soit $y > 0$ . Résolvons $e^{2 x + 1} = y$ . En composant par le logarithme, ce qui est une équivalence puisque l'exponentielle est bijective de $R$ sur $R_{+}^{*}$ , on obtient $2 x + 1 = \ln y$ , puis $x = \frac{\ln y - 1}{2}$ . On retrouve bien le même résultat.

Contrôle numérique : $(g \circ f) (0) = e^{1} = e$ , et $\frac{\ln e - 1}{2} = \frac{1 - 1}{2} = 0$ . $□$

Les erreurs qui coûtent des points

Voici, rassemblées, les fautes que les correcteurs rencontrent le plus souvent sur ce chapitre. Aucune n'est difficile à éviter ; toutes se paient cher, parce qu'elles portent sur la rigueur et non sur la technique. Relisez cette liste avant chaque devoir du premier semestre.

Le cours en PDF(PDF, 325 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

Ce qu'il faut savoir faire

Éléments de logique

Propositions et valeurs de vérité

Les connecteurs : négation, « et », « ou »

Négation d'une conjonction et d'une disjonction

Les quantificateurs

Quantifications implicites et ordre des quantificateurs

Négation d'une proposition quantifiée

Implication, réciproque, contraposée, équivalence

L'implication

Condition nécessaire, condition suffisante

La contraposée

La négation d'une implication

La réciproque

L'équivalence

Les modes de raisonnement

Le raisonnement direct

Le contre-exemple

La disjonction de cas

Le raisonnement par contraposée

Le raisonnement par l'absurde

Démontrer une inclusion, démontrer une égalité d'ensembles

Le raisonnement par récurrence

Le principe et la trame de rédaction

Un premier exemple entièrement rédigé

Un exemple avec une inégalité : l'inégalité de Bernoulli

Les pièges classiques

La récurrence double

La récurrence forte

Sommes et produits

La notation somme

Indice muet, nombre de termes, somme vide

Linéarité et relation de Chasles

Le changement d'indice

Le télescopage

Les sommes usuelles

La notation produit et la factorielle

Sommes indexées par une partie finie de N2

Ensembles

Ensembles, éléments, appartenance

Inclusion et égalité

L'ensemble des parties

Réunion, intersection, complémentaire, différence

Le produit cartésien

Applications

Définition, image, antécédent

La composition

Injection

Surjection

Bijection

L'application réciproque

Composée de deux bijections, réciproque de la composée

Les erreurs qui coûtent des points

Bloqué sur « Raisonnement et vocabulaire ensembliste » ?

Sommes indexées par une partie finie de $N^{2}$