c Christophe Bertault - MPSI

Pour bien démarrer l’année

Ce chapitre a un statut un peu particulier par rapport à tous ceux qui vont suivre : nous allons y étudier les bases de la
logique mathématique et y définir quelques notions élémentaires que nous utiliserons toute l’année. Ne paniquez pas si vous
n’aimez pas ce chapitre, les chapitres suivants ressembleront davantage aux chapitres que l’on vous a enseignés au lycée.

1 Un peu de logique
Convenons d’appeler proposition toute phrase p au sujet de laquelle on peut poser la question : p est-elle vraie ? La plupart
des phrases grammaticalement correctes sont des propositions, mais par exemple, « Dis-le-moi ! », « Bonjour » ou « Comment
vas-tu ? » n’en sont pas ; la question « Est-il vrai que bonjour ? » n’a aucun sens.
La valeur de vérité d’une proposition est soit le vrai (V), soit le faux (F). Deux propositions qui ont la même valeur de vérité
sont dites équivalentes ; cela veut dire qu’elles sont soit toutes les deux vraies, soit toutes les deux fausses. Cette notion est très
importante : quand vous devez démontrer une proposition p, vous n’êtes pas obligé de démontrer p elle-même ; il suffit que vous
démontriez n’importe quelle proposition q équivalente à p.

Exemple « Socrate n’est pas immortel » et « Socrate est mortel » sont deux propositions équivalentes ; démontrer l’une
revient donc à démontrer l’autre.

1.1 Connecteurs logiques

On appelle connecteur logique tout moyen de construire une proposition unique à partir d’une ou plusieurs propositions. Par
exemple, « et », « ou », « si, alors » et « parce que » sont des connecteurs ; à partir des propositions « J’ai faim » et « J’ai soif »,
on peut construire une nouvelle proposition « J’ai faim et (j’ai) soif ».
Un connecteur logique est dit vérifonctionnel si la valeur de vérité d’une proposition construite à l’aide de ce connecteur
dépend seulement de la valeur de vérité des propositions utilisées dans la construction. Ainsi la proposition « p et q » est vraie
si et seulement si les deux propositions p et q sont vraies. Peu importe le contenu exact de p et q ; seule leur vérité compte.
En mathématiques, tous les connecteurs logiques sont vérifonctionnels. L’intérêt des connecteurs
p q p et q
vérifonctionnels réside dans la facilité avec laquelle on peut les définir. Par exemple, pour définir le
V V V
connecteur « et », il suffit de décrire, en fonction de la valeur de vérité de p et q, la valeur de vérité de la
V F F
proposition « p et q » : par définition, « p et q » est vraie si p et q le sont, et fausse dans tous les autres
F V F
cas. Par souci de clarté, on présente généralement cette définition sous forme d’un tableau appelé une
F F F
table de vérité :

Pour votre propre culture, vous remarquerez que certains connecteurs logiques ne sont pas vérifonctionnels. C’est le cas du
connecteur « parce que ». Imaginons en effet un contexte dans lequel il est vrai que « Ses lunettes sont cassées parce qu’il les a
faites tomber ». Alors les deux propositions « Ses lunettes sont cassées » et « Il les a faites tomber » sont vraies. Remplaçons à
présent « Il les a faites tomber » par « La glace est un solide », elle aussi vraie. Si le connecteur « parce que » était vérifonctionnel,
notre nouvelle proposition « Ses lunettes sont cassées parce que la glace est un solide » devrait encore être vraie ; ce qui n’est
pas le cas. Cette absurdité prouve que « parce que » n’est pas vérifonctionnel.

1.1.1 Négation non

p non p
La proposition « non p » est vraie si p est fausse, fausse si p est vraie. V F
F V

p non p non (non p)

Loi de la double négation : p et « non (non p) » sont deux propositions
V F V
équivalentes. On s’en rend compte en observant la table suivante :
F V F
- %
Colonnes identiques

1
c Christophe Bertault - MPSI

1.1.2 Conjonction et, disjonction ou

p q p et q p ou q
La proposition « p et q » est vraie si p et q sont vraies, fausse dans tous les autres cas. V V V V
Quant à la proposition « p ou q », elle est vraie si p est vraie ou si q est vraie (éventuellement V F F V
les deux), fausse dans le seul cas où p et q sont fausses toutes les deux. F V F V
F F F F

$ $ $ Attention ! Dans le langage usuel, il arrive que le « ou » oppose les termes qu’il relie : dans l’expression « fromage
ou dessert », le « ou » est exclusif car il exclut la possibilité qu’on choisisse les deux (fromage et dessert).
Au contraire, en mathématiques, « ou » est inclusif : « p ou q » est vraie même quand p et q sont vraies.

Lois de De Morgan :
• « non (p et q) » et « (non p) ou (non q) » sont deux propositions équivalentes.
• « non (p ou q) » et « (non p) et (non q) » sont deux propositions équivalentes.

p q non p non q p et q non (p et q) (non p) ou (non q) p ou q non(p ou q) (non p) et (non q)

V V F F V F F V F F
V F F V F V V V F F
F V V F F V V V F F
F F V V F V V F V V
- % - %
Colonnes identiques Colonnes identiques

« Je n’aime ni le chocolat ni la vanille » — « (non p) et (non q) »
Exemple Ces deux phrases sont équivalentes : .
« Il est faux que j’aime le chocolat ou la vanille » — « non (p ou q) »

1.1.3 Implication =⇒
p q p =⇒ q
La proposition « p =⇒ q » se lit « p implique q » ou « si p, alors q ». Elle est vraie si p est fausse
V V V
ou si q est vraie, fausse uniquement lorsque p est vraie et q fausse. Elle répond à la question : si on
V F F
suppose que p est vraie, q l’est-elle aussi ? La proposition p est appelée l’antécédent de l’implication
F V V
« p =⇒ q », et q est appelée son conséquent.
F F V

   En pratique Pour montrer la vérité d’une implication « p =⇒ q », il convient d’abord de supposer que p est
vraie (ce n’est là qu’une hypothèse) ; puis de montrer d’une façon ou d’une autre que, sous cette hypothèse, q est vraie. Même
si vous ne savez pas démontrer jusqu’au bout que l’implication « p =⇒ q » est vraie, vous devez sur votre copie, de vous-même,
commencer bêtement par : « Supposons p vraie ».

$ $ $ Attention !
• Une implication « p =⇒ q » peut être vraie alors que p et q n’ont rien de commun. Il suffit que leurs valeurs de vérité
respectent la table de vérité de l’implication. Ainsi la phrase « Si 0 = 0, alors les oiseaux ont des plumes » est vraie.
• Par définition, « p =⇒ q » est toujours vraie quand p est fausse. Ainsi la phrase étrange « Si 0 6= 0, alors 0 = 0 » est vraie.
Après un tel exemple, la définition du connecteur =⇒ peut sembler suspecte ; pourquoi donc avoir choisi cette table de
vérité ? Nous le justifierons un peu plus loin.
• Affirmer que « p =⇒ q » est vraie n’implique ni que p est vraie, ni que q est vraie. Ainsi, il est vrai que « Si Pinocchio
est Président de la République, alors il est le chef des armées » ; pourtant il est faux que Pinocchio est Président de la
République, et il est également faux qu’il est chef des armées.

p q non q p =⇒ q non (p =⇒ q) p et (non q)

Négation d’une implication : « non (p =⇒ q) » V V F V F F
et « p et (non q) » sont deux propositions équivalentes. V F V F V V
F V F V F F
F F V V F F
- %
Colonnes identiques

   En pratique Conformément à ce qui précède, pour montrer qu’une implication « p =⇒ q » est fausse, on peut
montrer que « p et (non q) » est vraie, i.e. que p est vraie mais que q est fausse.

2
c Christophe Bertault - MPSI

Exemple Est-il vrai que, si on a 18 ans (p), alors on a le droit de vote (q) ? La réponse est. . . non. Car je peux très bien
avoir 18 ans — p est vraie — et un casier judiciaire tel que le droit de vote m’a été supprimé — q est fausse.

p q non q non p p =⇒ q (non q) =⇒ (non p)

Contraposition :
V V F F V V
« p =⇒ q » et « (non q) =⇒ (non p) » sont deux proposi-
V F V F F F
tions équivalentes. La proposition « (non q) =⇒ (non p) » est
F V F V V V
appelée la contraposée de l’implication « p =⇒ q ».
F F V V V V
- %
Colonnes identiques

« S’il pleut, alors il y a des nuages » — « p =⇒ q »
Exemple Ces deux phrases sont équivalentes : .
« S’il n’y a pas de nuages, alors il ne pleut pas » — « (non q) =⇒ (non p) »

1.1.4 Equivalence ⇐⇒
p q p ⇐⇒ q
V V V
La proposition « p ⇐⇒ q » se lit « p si et seulement si q » ou « p et q sont équivalentes ». Elle est
V F F
vraie si p et q ont la même valeur de vérité, fausse sinon.
F V F
F F V

p q p =⇒ q q =⇒ p p ⇐⇒ q (p =⇒ q) et (q =⇒ p)
Equivalence et double implication :
V V V V V V
« p ⇐⇒ q » et « (p =⇒ q) et (q =⇒ p) » sont deux
V F F V F F
propositions équivalentes. La proposition « q =⇒ p » est
F V V F F F
appelée la réciproque de l’implication « p =⇒ q ».
F F V V V V
- %
Colonnes identiques

   En pratique Pour montrer qu’une équivalence « p ⇐⇒ q » est vraie, on peut choisir l’une des trois méthodes
suivantes :
1) aller de p jusqu’à q au moyen d’un raisonnement dont chaque étape est une équivalence :

p ⇐⇒ p1 ⇐⇒ p2 ⇐⇒ . . . ⇐⇒ pn ⇐⇒ q ;

2) montrer l’implication « p =⇒ q », puis sa réciproque « q =⇒ p » ;

3) montrer l’implication « p =⇒ q », puis la contraposée de sa réciproque « (non p) =⇒ (non q) ».

Revenons un instant sur le connecteur =⇒. Nous sommes restés sur un point d’interrogation tout à l’heure : pourquoi avoir
décidé que « p =⇒ q » est vraie quand p est fausse ? Cela a pour conséquence étrange que la proposition « Si 0 6= 0, alors 0 = 0 »
est vraie.
En réalité avions-nous le choix ? Ce qui est sûr, c’est qu’il n’est pas question
p q p =⇒ q q p ⇐⇒ q p et q
de toucher aux deux premières lignes de la table de vérité de l’implication.
V V V V V V
Seules les deux dernières lignes nous gênent, lorsque p est fausse. Et si on les
V F F F F F
changeait ? Le problème, c’est qu’en changeant les deux dernières lignes de la
F V V V F F
table de vérité de l’implication, on retombe sur des connecteurs déjà connus
F F V F V F
comme l’illustre la table ci-contre :

1.2 Quantificateurs universel ∀ et existentiel ∃

1.2.1 Définition

On appelle prédicat toute propriété portant sur un ou plusieurs objets donnés en arguments. Par exemple, « être un oreiller »
est un prédicat ; si nous le notons O, la notation O(x) signifiera « x est un oreiller ». De même, « être plus âgé que » est un
prédicat, portant lui sur deux objets ; si nous le notons A, la notation A(x, y) pourra signifier « x est plus âgé que y ». En
mathématiques, nous connaissons quelques prédicats incontournables : =, 6, < . . . sauf qu’au lieu de noter 6 (x, y), on préfère
employer la notation x 6 y.

3
 c Christophe Bertault - MPSI

Il existe deux quantificateurs en mathématiques : le quantificateur universel ∀ et le quantificateur existentiel ∃. Si E est un

ensemble et si P est un prédicat à un objet :
• la proposition « Tous les éléments de E vérifient la propriété P » s’écrit : ∀x ∈ E, P(x)
et se lit : « Pour tout x élément de E/quel que soit x élément de E, x vérifie P » ;
• la proposition « L’un (au moins) des éléments de E vérifie la propriété P » s’écrit : ∃ x ∈ E/ P(x)
et se lit : « Il existe un élément x de E tel que x vérifie P ».

   En pratique La remarque qui suit est très importante : je me ferai un plaisir de couper la tête à tous ceux qui
n’apprendront pas vite à la respecter. Vous la retrouverez avec davantage de détails dans le « Petit manuel de bonne rédaction ».
• Supposons qu’on veuille démontrer un théorème à base de ∀ de la forme : ∀x ∈ E, P(x). La plupart des théorèmes
mathématiques peuvent se mettre sous cette forme.
Vous avez le droit de ne pas savoir démontrer jusqu’au bout un tel théorème, mais vous n’avez pas le droit de ne pas savoir
comment commencer votre démonstration. Sans réfléchir, vous la commencerez par : « Soit x ∈ E ». Un élément x étant
ainsi fixé, vous tenterez de montrer que ce x a la propriété P. Si vous y parvenez, c’est terminé.
• Supposons qu’on veuille démontrer un théorème à base de ∃ de la forme : ∃ x ∈ E/ P(x).
Montrer l’existence d’un objet mathématique — ici, l’existence d’un élément x de E qui vérifie la propriété P — revient
à exhiber un tel objet. L’exemple suivant illustre la marche à suivre dans un tel contexte.

Exemple ∀x, y ∈ R, ∃ z ∈ R/ z > x + y.

En effet Prouvons cette proposition. La formulation « ∀x, y ∈ R » est un raccourci d’écriture pour dire
« ∀x ∈ R, ∀y ∈ R ».
Début de la démonstration : soient x, y ∈ R. Un x et un y étant fixés, nous devons montrer l’existence d’un
réel z tel que z > x + y. Or démontrer l’existence d’un objet revient à donner un exemple de tel objet. Ici nous
avons le choix : n’importe quel réel strictement supérieur à x + y convient. Par exemple, posons z = x + y + 1.
Alors z = x + y + 1 > x + y. C’est terminé.

$ $ $ Attention ! La lettre x de « ∀x, P(x) » ou « ∀y, P(x) » peut être remplacée par n’importe quel symbole
n’apparaissant pas dans P ; tout symbole figurant dans P est exclu.
Pour comprendre cela, fixons un entier naturel n (quelconque) et intéressons-nous au prédicat « être inférieur ou égal à n ».
Imaginons qu’on veuille répondre à la question : tous les entiers naturels sont-ils inférieurs ou égaux à n ? Bien sûr la réponse est
non, car par exemple n + 1 n’est pas inférieur ou égal à n. En tout cas, la proposition à démontrer s’écrit : ∀k ∈ N, k 6 n.
La lettre k pourrait ici être remplacée par les lettres x, p . . . mais pas par la lettre n. En effet, la proposition obtenue serait
alors : ∀n ∈ N, n 6 n, qui est vraie, tous les entiers naturels étant inférieurs ou égaux à eux-mêmes.

1.2.2 Négation


Négation du quantificateur universel : Les propositions « non ∀x ∈ E, P(x) » et « ∃ x ∈ E/ non P(x) »
sont équivalentes.

Exemple Ces deux phrases sont équivalentes :



« Il est faux que tout homme a les yeux bleus » — « non ∀x ∈ E, P(x) »
.
« Certains hommes n’ont pas les yeux bleus »/« Il existe au moins un homme qui n’a pas les yeux bleus » — « ∃ x ∈ E/ non P(x) »

Négation du quantificateur existentiel : Les propositions « non ∃ x ∈ E/ P(x) » et « ∀x ∈ E, non P(x) »
sont équivalentes.

Exemple Ces deux phrases sont équivalentes :



« Aucun homme n’a de cornes »/« Il est faux qu’il existe un homme à cornes » — « non ∃ x ∈ E/ P(x) »
.
« Tout homme est sans cornes » — « ∀x ∈ E, non P(x) »

   En pratique Pour nier une phrase contenant un ou plusieurs quantificateurs, on réécrit cette phrase : 1) en
remplaçant tous les « ∀ » par des « ∃ » et tous les « ∃ » par des « ∀ », et 2) en niant le prédicat final.

Exemple La négation de la proposition : "  √  #

 x 
∀ε > 0, ∃ α > 0/ ∀x ∈ R, |x| < α =⇒  x2 + 1  < ε


l l l l Négation
"  √  #
 x 
est : ∃ ε > 0/ ∀α > 0, ∃ x ∈ R/ |x| < α et  x2 + 1  > ε .
 

4
c Christophe Bertault - MPSI

1.2.3 Permutation des quantificateurs

On peut toujours permuter les quantificateurs universels ∀ entre eux, et les quantificateurs existentiels ∃ entre eux.

Exemple
• Les propositions « ∀x ∈ R+ , ∀y ∈ R− , x>y » et « ∀y ∈ R− , ∀x ∈ R+ , x > y » sont équivalentes.
• Les propositions « ∃ x ∈ R+ , ∃ y ∈ R− , x>y » et « ∃ y ∈ R− , ∃ x ∈ R+ , x > y » sont équivalentes.

$ $ $ Attention ! La permutation d’un ∀ et d’un ∃ n’est pas aussi facile. Voyons cela sur deux exemples.

• « Dans toute cerise il y a un noyau ». Formellement, cette proposition s’écrit :

∀c cerise, ∃ n noyau/ n est dans c.

Qu’arrive-t-il si nous permutons ∀ et ∃ ? Essayons : « ∃ n noyau/ ∀c cerise, n est dans c ». En bon français, cela
donne : « Il existe un noyau qui se trouve dans toutes les cerises ». Tiens donc : alors que nous étions convaincus de la
vérité de la proposition initiale, cette nouvelle proposition nous paraît clairement fausse.
Conclusion : quand une proposition de la forme « ∀∃ » est vraie, la proposition « ∃∀ » correspondante peut être fausse.
L’opération de permutation qui fait passer d’une configuration « ∀∃ » à une configuration « ∃∀ » est interdite.

• « Il existe une femme qui est la mère de tous les être humains » (faisons comme si Eve existait). Formellement, cette
proposition s’écrit :
∃ f femme/ ∀h être humain, f est la mère de h.
A présent permutons ∀ et ∃ : « ∀h être humain, ∃ f femme/ f est la mère de h ». En bon français, cela donne :
« Tout homme a une mère », proposition évidemment vraie. La permutation a ici fonctionné convenablement, mais la
proposition obtenue après permutation est beaucoup moins forte, beaucoup moins contraignante que celle dont nous
sommes partis : la première était vraie à condition qu’Eve ait existé ; la seconde au contraire est d’une banalité incroyable.
Conclusion : quand une proposition de la forme « ∃∀ » est vraie, la proposition « ∀∃ » est elle aussi vraie. Ce genre de
permutation est donc autorisé.

1.2.4 Le pseudo-quantificateur ∃ !

Parfois on ne veut pas seulement affirmer qu’un objet existe avec certaines propriétés, mais affirmer en outre qu’il est le
seul à posséder ces propriétés. La proposition « Il existe (un et) un seul élément de E qui possède la propriété P » s’écrit en
mathématiques : ∃ ! x ∈ E/ P(x) et se lit : « Il existe un unique x élément de E tel que x vérifie P ».

   En pratique Pour démontrer la proposition « ∃ ! x ∈ E/ P(x) », on a deux choses à démontrer : l’existence d’un
tel x et son unicité.
• Pour l’existence, on fait comme si on travaillait avec la proposition « ∃ x ∈ E/ P(x) ».
• Pour l’unicité, on suppose généralement que deux éléments x et x de E ont la propriété P et on montre alors que x = x0 .
0

Cela montre qu’il ne peut y avoir deux objets distincts possédant la propriété P, autrement dit qu’il n’y en a qu’un seul.

Exemple ∃ ! x ∈ R+ / x2 = 1.
En effet
• Existence : Posons x = 1. Alors x ∈ R+ et x2 = 1 comme voulu.
• Unicité : Soient x, x0 ∈ R+ . On suppose que x2 = x02 = 1. Montrons que x = x0 . Or puisque x2 = x02 , on
a x = x0 ou x = −x0 .
Peut-on avoir x = −x0 ? Si c’est le cas, alors comme x et x0 sont positifs, x = x0 = 0. Cela contredit le fait
que x2 = x02 = 1. On ne peut donc pas avoir x = −x0 . Par conséquent x = x0 comme voulu.

5
c Christophe Bertault - MPSI

1.3 Le raisonnement par récurrence

Soient P0 , P1 , P2 , . . . une suite infinie de propositions. Supposons qu’on veuille démontrer la proposition : ∀n ∈ N, Pn .
Le raisonnement par récurrence est la technique générale de démonstration adaptée à ce problème.

Initialisation Hérédité
z }| { z }| {
Principe de la récurrence : Si P0 est vraie, et si, pour tout n ∈ N, la vérité de Pn implique la vérité de Pn+1 ,
alors la proposition : ∀n ∈ N, Pn est vraie.
Plus généralement, n0 étant un entier naturel fixé, si Pn0 est vraie, et si, pour tout n ∈ N, n > n0 , la vérité de Pn implique
la vérité de Pn+1 , alors la proposition : ∀n ∈ N, n > n0 , Pn est vraie.

Exemple Soit (un )n∈N une suite géométrique de raison q, où q ∈ C. Montrons que pour tout n ∈ N : un = q n u0 .
En effet
• Initialisation : On a q 0 = 1 par convention, donc u0 = q 0 u0 .
• Hérédité : Soit n ∈ N. On suppose que un = q n u0 . Il s’agit de montrer que un+1 = q n+1 u0 .
Facile : un+1 = qun = q × q n u0 = q n+1 u0 comme voulu. Fin de la récurrence.

Exemple Par définition, un entier n ∈ Z est pair s’il existe k ∈ Z tel que n = 2k, et impair s’il existe k ∈ Z tel que n = 2k + 1.
Nous allons démontrer que tout entier est pair ou impair.
En effet
• Initialisation : L’entier 0 est pair car il s’écrit 0 = 2 × 0.
Hérédité : Soit n ∈ N. On suppose n pair ou impair. Il s’agit de montrer que (n + 1) est lui aussi pair ou
impair. Deux cas se présentent :
1) si n est pair, de la forme n = 2k où k ∈ Z, alors n + 1 = 2k + 1 donc (n + 1) est impair ;
2) si n est impair, de la forme n = 2k + 1 où k ∈ Z, alors n + 1 = (2k + 1) + 1 = 2(k + 1) avec
k + 1 ∈ Z et donc (n + 1) est pair.
Au final (n + 1) est pair ou impair comme voulu. Fin de la récurrence.

• Nous venons donc de montrer que tout entier naturel est pair ou impair. Qu’en est-il des entiers négatifs ?
Soit n un tel entier. Alors −n est un entier naturel, donc −n est pair ou impair :
1) si −n est pair, on peut l’écrire −n = 2k où k ∈ Z, donc n = 2(−k) est pair avec −k ∈ Z ;
2) si −n est impair, on peut l’écrire −n = 2k + 1 où k ∈ Z, donc n = −2k − 1 = 2(−k − 1) + 1 est
impair avec (−k − 1) ∈ Z.
Dans les deux cas n est pair ou impair. C’est terminé.

   En pratique Pour rédiger vos récurrences, je vous recommande d’adopter la rédaction des deux exemples précédents.
1) D’abord on initialise ; c’est généralement facile, mais il faut quand même le faire.
2) Ensuite on se donne un entier naturel n quelconque — « Soit n ∈ N » — et on suppose que la propriété à
démontrer est vraie au rang n. Il reste à démontrer, sous cette hypothèse, la proposition au rang (n + 1). Et c’est tout.

$ $ $ Attention ! Dans la partie hérédité d’une récurrence, ne commencez jamais par : « On suppose que pour tout
entier n, Pn est vraie. . . » Car si vous supposez ainsi le résultat qu’il faut montrer, vous ne le montrerez jamais. Cette erreur
est très grave.

Bien souvent, l’hypothèse que Pn est vraie ne suffit pas pour montrer que Pn+1 est vraie : on peut avoir besoin de Pn et
Pn−1 , voire de toute la suite P0 , P1 , . . . , Pn . Nous allons voir sur un exemple comment le raisonnement par récurrence peut être
adapté à de tels cas.

Exemple Soit (un )n∈N la suite réelle définie par u0 = −1, u1 = 5 et : ∀n ∈ N, un+2 = 3un+1 − 2un .
Alors : ∀n ∈ N, un = 6.2n − 7.
En effet
• Tout terme de la suite (un )n∈N ne peut être calculé que si les deux termes précédents sont déjà connus ; on
ne peut calculer un+2 que si l’on connaît un et un+1 . Quant à nous, nous voulons montrer la propriété Pn
« un = 6.2n − 7 » pour tout n ∈ N. Nous ne pouvons pas la démontrer par une récurrence classique, car
pour montrer Pn+1 , nous aurions besoin de supposer Pn et Pn−1 vraies.

• Pour tout n ∈ N, notons Qn la propriété « Pn et Pn+1 ». Supposons qu’on ait réussi à montrer que Qn est
vraie pour tout n ∈ N ; alors on a en fait montré que Pn est vraie pour tout n ∈ N. Montrer la proposition
« ∀n ∈ N, Pn » revient donc à montrer la proposition « ∀n ∈ N, Qn ». Mais alors que nous ne pouvions pas
montrer la première par une récurrence classique, nous allons pouvoir montrer la deuxième très simplement.

6
c Christophe Bertault - MPSI

P0 P1
z }| { z }| {
1) Initialisation : u0 = −1 = 6.20 − 7 et u1 = 5 = 6.21 − 7. Bref, Q0 est vraie.
2) Hérédité : Soit n ∈ N. Supposons Qn vraie. Cela revient à supposer Pn et Pn+1 vraies. Nous
devons montrer que Qn+1 est vraie, i.e. que Pn+1 et Pn+2 le sont. Mais comme Pn+1 est vraie par
hypothèse, il ne nous reste plus qu’à montrer que Pn+2 est vraie ; ce qui est facile :



un+2 = 3un+1 − 2un = 3 6.2n+1 − 7 − 2 6.2n − 7 = 9.2n+2 − 21 − 3.2n+2 + 14 = 6.2n+2 − 7.

Fin de la récurrence.

• En pratique, ne vous embêtez pas à définir proprement la propriété double Qn . Rédigez votre preuve de la
façon suivante :
1) Initialisation : Comme ci-dessus (double initialisation).
2) Hérédité : Soit n ∈ N. On suppose que un = 6.2n − 7 et que un+1 = 6.2n+1 − 7. Montrons que
un+2 = 6.2n+2 − 7. C’est facile : un+2 = . . . = 6.2n+2 − 7. Et voilà, c’est terminé.

Remarque On a souvent l’impression, quand on fait des récurrences, que les initialisations ne servent à rien. Quelle erreur
de le croire ! Tentons par exemple de montrer que : ∀n ∈ N, n = n + 1. Ce résultat est faux, bien entendu.
• Hérédité : Soit n ∈ N. Nous supposons que n = n + 1 et voulons montrer que n + 1 = (n + 1) + 1. C’est facile, il suffit
d’ajouter 1 aux deux membres de l’hypothèse de récurrence : puisque n = n + 1, alors n + 1 = n + 2. L’hérédité ne pose
donc aucun problème.
• Initialisation : En fait c’est l’initialisation qui pose problème, car l’égalité 0 = 1 est fausse.

1.4 Le raisonnement par l’absurde

Principe du raisonnement par l’absurde : Pour montrer que p est vraie, on suppose qu’elle est fausse et on
tâche d’en tirer une contradiction, i.e. la vérité de deux propositions q et « non q » ; une proposition et sa négation ne pouvant
être vraies toutes les deux, on en déduit que l’hypothèse selon laquelle p est fausse est fausse, i.e. que p est vraie.

Exemple Tout entier est pair ou impair, mais pas les deux.
En effet Soit n ∈ Z. Nous avons déjà vu que n est pair ou impair. Peut-il être les deux à la fois ? Pour montrer
1
que non, supposons que oui. Alors n s’écrit n = 2k = 2l + 1 où k, l ∈ Z. On a donc 2(k − l) = 1, et du coup est
2
un entier ; ce qui est faux. L’hypothèse selon laquelle n est à la fois pair et impair est donc fausse ; par conséquent
n est pair ou impair, mais pas les deux.

Exemple Rappelons qu’un nombre est dit rationnel s’il est le quotient d’un entier par un entier non nul, i.e. s’il est une
fraction d’entiers ; au contraire, un nombre est dit irrationnel s’il n’est pas rationnel.
√
Nous allons montrer ci-dessous que : 2 est irrationnel.
En effet
• Commençons par un petit lemme : pour tout n ∈ Z, n est pair si et seulement si n2 est pair. Fixons donc
n ∈ Z.
1) Si n est pair, alors on peut écrire n = 2k où k ∈ Z, et donc n2 = (2k)2 = 2(2k2 ) avec 2k2 ∈ Z ;
cela montre que n2 est pair.
2) Pour la réciproque, raisonnons par contraposition : cela revient à montrer que si n n’est pas pair,
alors n2 n’est pas pair. Si donc n n’est pas pair, alors n est impair comme nous l’avons vu, donc de la
forme n = 2k + 1 où k ∈ Z. On a alors n2 = (2k + 1)2 = 2(2k2 + 2k) + 1 avec (2k2 + 2k) ∈ Z, de sorte que
n2 est impair. L’exemple précédent implique aussitôt que n2 n’est pas pair.
√ √ p
• Supposons à présent, par l’absurde, que 2 est rationnel. Alors 2 peut s’écrire sous la forme
où p et q
q
p
sont deux entiers. Choisissons p et q de façon à ce que la fraction soit irréductible — aucune simplification
q
n’est plus possible.
√
2
1) L’égalité p2 = q 2 = 2q 2 montre que p2 est pair. Mais donc p est pair via le premier point et
0 0
s’écrit p = 2p avec p ∈ Z.

7
c Christophe Bertault - MPSI

 2  0 2
p 2p √
2
2) Du coup q 2 = √ = √ = p0 2 = 2p02 . Ceci montre que q 2 est pair, et donc q aussi
2 2
est pair, de la forme q = 2q 0 avec q 0 ∈ Z.
p
Concluons. Nous venons sans le voir de montrer que la fraction était réductible, contrairement à notre
q
0 0
p 2p p
hypothèse, puisque = 0 = 0 — contradiction.
q 2q q

2 Un peu de théorie des ensembles

2.1 Appartenance et inclusion E

b
x

Les notions intuitives d’ensemble et d’appartenance sont supposées connues : les ensembles sont des sacs de billes dont les
éléments sont. . . les billes. Pour tout ensemble E, la relation « x est un élément de E » ou « x appartient à E » est notée x ∈ E ;
/ E pour dire que x n’appartient pas à E. L’ensemble vide, i.e. qui n’a pas d’élément, est noté ∅.
on note x ∈

Exemple
• On note N l’ensemble des entiers naturels, Z l’ensemble des entiers relatifs, Q l’ensemble des rationnels, R l’ensemble des
réels et C l’ensemble des nombres complexes.
• On note en outre E+ l’ensemble des éléments positifs ou nuls de E quand E est l’un des ensembles Q ou R ; même principe
pour la notation E− .
• On note enfin E× l’ensemble des éléments non nuls de E quand E est l’un des ensembles N, Z, Q, Q+ , Q− , R, R+ , R− , C.

Définition (Egalité) Soient E et F deux
ensembles. On dit que E et F sont égaux s’ils possèdent exactement les mêmes
éléments, i.e. si : ∀x, x ∈ E ⇐⇒ x ∈ F .
Cette relation entre E et F est notée E = F .

Un ensemble peut être défini de deux façons : en extension ou en compréhension.

• Définir un ensemble en extension, c’est donner la liste complète explicite dentous ses
o éléments ; on note cette liste
entre accolades, l’ordre des éléments listés n’ayant aucune importance. Par exemple, 0, 1, 2 est un ensemble, le même que
n o  n o
2, 1, 0 . Un ensemble de la forme x , i.e. à seul élément, est appelé un singleton ; un ensemble de la forme x, y avec
x 6= y, i.e. à deux éléments, est appelé une paire. Il est bien évident qu’on ne peut définir en extension que des ensembles
ayant un nombre fini d’éléments, incapables que nous sommes d’écrire une liste infinie de symboles.
• Définir un ensemble en compréhension, c’est donner une propriété vérifiée par les éléments de cet ensemble et eux
seuls. Parler par
n exemple de l’ensemble
o des entiers naturels qui sont égaux à leur carré, c’est parler d’un ensemble unique
2
que l’on note n ∈ N/ n = n ; la lettre n pourrait être remplacée par n’importe quelle symbole ne figurant pas dans
la définition de l’ensemble. 
Les éléments d’un ensemble sont souvent repérés dans une liste par un ou plusieurs « paramètres ». Ainsi xi i∈I désigne
l’ensemble des éléments notésn xi repérés par un indice
o i décrivant un certain ensemble I. Décrit en compréhension,

cet ensemble s’écrit aussi x/ ∃ i ∈ I/ x = xi . Par exemple, 2n n∈N désigne l’ensemble constitué des éléments
20 , 21 , 22 , 23 . . .
Que ce soit bien clair : il n’y a pas deux sortes d’ensembles en mathématiques. Un même ensemble, s’il est fini, sera défini
tour à tour en extension ou en compréhension selon les contextes. Ainsi les quatre ensembles décrits ci-dessous sont égaux :
n o n o n o n o
0, 1 = n ∈ N/ n2 = n = z ∈ C/ z 2 = z = n ∈ Z/ n > 0 et n < 2 .

Définition (Inclusion) Soient E et F deux ensembles. On dit que E est inclus dans F si tout élément de E est un élément
de F , i.e. si : ∀x ∈ E, x ∈ F .
E F
Cette relation entre E et F est notée E ⊆ F . On dit aussi que F contient E ou que E est une partie de F .

Exemple Les inclusions suivantes sont bien connues : N ⊆ Z ⊆ Q ⊆ R ⊆ C.

8
c Christophe Bertault - MPSI

$ $ $ Attention ! L’erreur classique consiste à confondre l’appartenance ∈ et l’inclusion ⊆. Soyez vigilants !

n  o 
• L’ensemble 0, 0 est l’ensemble dont les éléments sont exactement 0 et 0 .
n  o n  o
1) Il est vrai que 0 ∈ 0, 0 car 0 est bien un élément de 0, 0 .
 n  o  n  o
2) Il est vrai que 0 ∈ 0, 0 car 0 est bien un élément de 0, 0 .
 n  o  
3) Il est vrai que 0 ⊆ 0, 0 . En effet, 0 a pour seul élément 0. Tout élément de 0 est donc bel et
n  o
bien élément de 0, 0 .
n o n  o n o 
4) Il est vrai enfin que 0 ⊆ 0, 0 . En effet, 0 a pour seul élément 0 . Tout élément de
n o n  o
0 est donc bel et bien élément de 0, 0 .
n o n o
• On a 0 ∈ N, mais 0 * N. On a − 1, 0, 1 ⊆ Z, mais − 1, 0, 1 ∈ / Z.

   En pratique Si vous devez montrer une inclusion E ⊆ F — vous aurez très souvent à le faire — commencer sans
réfléchir ainsi : « Soit x ∈ E. Montrons que x ∈ F . » Vous avez le droit de ne pas réussir à aller plus loin, mais vous devez au
moins penser à faire cela.

n o
Exemple x ∈ R/ ∃ y ∈ R+ / x>y ⊆ R+ .

En effet Soit x ∈ R pour lequel il existe y ∈ R+ tel que x > y. Montrons que x ∈ R+ .
Or y > 0 par hypothèse et x > y, donc x > 0. Cela montre bien que x ∈ R+ .

Exemple Si E est l’ensemble des entiers de la forme k(k + 1) où k ∈ N et si 2N est l’ensemble des entiers naturels pairs,
alors : E ⊆ 2N. En français, cela revient à dire que tout entier de la forme k(k + 1) avec k ∈ N est pair.
En effet Soit n ∈ E. Montrons que n ∈ 2N. Par définition, il existe k ∈ N tels que n = k(k + 1). Or l’un des
entiers k et (k + 1) est pair. En effet, k est pair ou impair, et si k est impair, alors k + 1 est pair. Par produit,
n = k(k + 1) est donc pair. En d’autres termes, n ∈ 2N comme annoncé.

Théorème Soient E et F deux ensembles. E et F sont égaux si et seulement si E ⊆ F et F ⊆ E.

   En pratique Pour démontrer l’égalité de deux ensembles E et F , deux possibilités :

1) soit vous raisonnez directement par équivalence : x ∈ E ⇐⇒ . . . ⇐⇒ x ∈ F ;
Il n’est malheureusement pas toujours possible de raisonner ainsi, cela peut s’avérer compliqué à rédiger.
2) soit vous raisonnez par double inclusion en vous appuyant sur le théorème précédent. Cela revient à raisonner
en deux temps. Premier temps : vous vous donnez un élément de E et vous montrez qu’il appartient à F .
Second temps : vous vous donnez un élément de F et vous montrez qu’il appartient à E.

L’exemple suivant illustre l’usage de la technique 2). La technique 1) sera illustrée plus loin par différents théorèmes.
n o
Exemple R− = x ∈ R/ ∀y ∈ R+ , x6y .

En effet
n o
• Montrons que R− ⊆ x ∈ R/ ∀y ∈ R+ , x 6 y .
Soit x ∈ R− . Nous devons montrer que : ∀y ∈ R+ , x 6 y. Soit donc y ∈ R+ . On a bien x 6 y comme
voulu, puisque x est négatif et y positif.
n o
• Montrons que x ∈ R/ ∀y ∈ R+ , x 6 y ⊆ R− .
Soit x ∈ R tel que : ∀y ∈ R+ , x 6 y. Alors en particulier x 6 0 (pour y = 0). Cela montre bien que
x ∈ R− .

Définition (Ensemble des parties) Soit E un ensemble. L’ensemble des parties de E est noté P(E).
Pour tout ensemble A, on a donc : A ∈ P(E) ⇐⇒ A ⊆ E.

$ $ $ Attention ! Dire que A appartient à P(E) équivaut à dire que A est incluse dans E. Il est ici particulièrement
important de comprendre la différence entre appartenance et inclusion.

9
c Christophe Bertault - MPSI

Exemple Soit E un ensemble. Alors E ∈ P(E) et ∅ ∈ P(E).

En effet
• Montrons que E ∈ P(E). Cela revient à montrer que E ⊆ E, ce qui est vrai car tout élément de E est un
élément de E.
• Montrons que ∅ ∈ P(E). Cela revient à montrer que tout élément de ∅ est un élément de E
; autrement
dit que, pour tout x, si x ∈ ∅, alors x ∈ E ; ce qui s’écrit encore : ∀x, x ∈ ∅ =⇒ x ∈ E .
Or par définition ∅ n’a pas d’élément. D’antécédent faux, l’implication « x ∈ ∅
=⇒ x ∈ E » est donc vraie
via la table de vérité de =⇒. Il est donc vrai que : ∀x, x ∈ ∅ =⇒ x ∈ E comme voulu.

2.2 Opérations sur les ensembles

Définition (Réunion, intersection) Soient A et B deux ensembles.

• On appelle réunion de A et B, notée A ∪ B, l’ensemble des x tels que : x∈A ou x ∈ B.
• On appelle intersection de A et B, notée A ∩ B, l’ensemble des x tels que : x∈A et x ∈ B.

A A

A∪B A∩B
B B


Ces définitions se généralisent au cas de plus de deux ensembles. Soit Ai i∈I un ensemble d’ensembles — cela veut dire que I
est un ensemble, et que pour tout i ∈ I, Ai est un ensemble.
[
• On appelle réunion des Ai , i ∈ I, notée Ai , l’ensemble des x tels que : ∃ i ∈ I/ x ∈ Ai .
i∈I
« x est dans l’un des Ai »
\
• On appelle intersection des Ai , i ∈ I, notée Ai , l’ensemble des x tels que : ∀i ∈ I, x ∈ Ai .
i∈I
« x est dans tous les Ai »

   Explication On notera bien les parallélismes suivants : ∪/ou/∃ d’une part, ∩/et/∀ d’autre part.

Définition (Ensembles disjoints) Soient E et F deux ensembles. On dit que E et F sont disjoints si E ∩ F = ∅, autrement
dit si E et F n’ont aucun élément commun.


Théorème (Distributivité de la réunion et de l’intersection l’une sur l’autre) Soient Ai i∈I un ensemble d’ensembles
[  [
 \  \

et B un ensemble. Ai ∩ B = Ai ∩ B et Ai ∪ B = Ai ∪ B .
i∈I i∈I i∈I i∈I

Démonstration Contentons-nous de démontrer la première égalité. La deuxième se montre de la même façon.

Soit x.
[  [

x∈ Ai ∩ B ⇐⇒ x∈ Ai et x ∈ B ⇐⇒ ∃ i ∈ I/ x ∈ Ai et x ∈ B
i∈I i∈I


⇐⇒ ∃ i ∈ I/ x ∈ Ai et x∈B ⇐⇒ ∃ i ∈ I/ x ∈ Ai ∩ B
[

⇐⇒ x∈ Ai ∩ B . 
i∈I

10
c Christophe Bertault - MPSI

Définition (Différence, complémentaire)

A
• Soient A et B deux ensembles.
ArB B
On appelle différence de B dans A, notée A r B, l’ensemble des x tels que : x∈A et x∈
/ B.

Ac
• Soient E un ensemble et A une partie de E. L’ensemble E rA est appelé le complémentaire
de A dans E. Il est noté Ac ou Ā quand il n’y a pas d’ambiguïté. A
E


Théorème (Relations de De Morgan) Soit Ai i∈I un ensemble de parties d’un même ensemble E.
 [ c \ c  \ c [
Ai = Ai et Ai = Aci .
i∈I i∈I i∈I i∈I

   Explication
Pourquoi appeler ces égalités
c « relations de De Morgan » ? Dans le cas de deux ensembles A et B, elles
c
s’écrivent : A ∪ B = Ac ∩ B c et A ∩ B = Ac ∪ B c .
Si nous voyons la réunion comme un « ou », l’intersection comme un « et » et le passage au complémentaire comme un « non »,
ces égalités nous rappellent les lois de De Morgan de notre introduction à la logique. — A méditer.

Démonstration Contentons-nous de démontrer la première égalité. Soit donc x ∈ E.

 [ c  [ 

x∈ Ai ⇐⇒ non x ∈ Ai ⇐⇒ non ∃ i ∈ I/ x ∈ Ai
i∈I i∈I

\
⇐⇒ ∀i ∈ I, non x ∈ Ai ⇐⇒ ∀i ∈ I, x ∈ Aci ⇐⇒ x∈ Aci . 
i∈I

Nous aurons l’occasion de revenir plus tard sur les définitions qui suivent. Contentons-nous ici d’une présentation intuitive.
Pour tout m, n ∈ Z tels que m 6 n, on note Jm, nK l’ensemble des entiers compris entre m et n (m et n inclus) ; si on veut
exclure m par exemple, on utilise la notation Km, nK ;

Définition (Famille)
• Soient E et I deux ensembles. Une suite d’éléments de E repérés chacun par un élément de I est appelée une famille
d’éléments de E indexée par I.
• Une telle famille est notée (xi )i∈I — xi ∈ E étant repéré par l’indice i ∈ I. Dans le cas où I = Jm, nK où m, n ∈ Z
sont tels que m 6 n, on la note plus couramment (xi )m6i6n ou (xm , xm+1 , . . . , xn ).
• Deux familles (xi )i∈I et (yi )i∈I d’éléments de E indexées par I sont égales si et seulement si : ∀i ∈ I, x i = yi .
L’élément xi est appelé la composante d’indice i de (xi )i∈I .

$ $ $ Attention !

• Ne confondez surtout pas la famille (xi )i∈I avec l’ensemble xi i∈I . Dans un ensemble, les éléments sont donnés sans
n o n o
ordre ; dans une famille l’ordre des éléments compte. Ainsi 1, 2, 3 = 2, 3, 1 , mais (1, 2, 3) 6= (2, 3, 1).
 
• Dans une famille du type (xi )m6i6n , il y a n − m +1 éléments, et non pas (n − m) comme on pourrait le penser.

Définition (Produit cartésien) Soient E1 , E2 , . . . , En des ensembles non vides. L’ensemble des familles (x1 , x2 , . . . , xn ) dans
lesquelles x1 ∈ E1 , x2 ∈ E2 , . . . xn ∈ En est appelé le produit (cartésien) de E1 , E2 , . . . , En et noté E1 × E2 × . . . × En .
Dans le cas où E1 = E2 = . . . = En = E, le produit E1 × E2 × . . . × En est généralement noté E n .

Remarque Les débuts de proposition « ∀x ∈ E1 , ∀y ∈ E2 , . . . » et « ∀(x, y) ∈ E1 × E2 , . . . » sont rigoureusement identiques.

11
c Christophe Bertault - MPSI

3 Un peu de calcul
P
3.1 Le symbole somme

3.1.1 Définition

P
Définition (Symbole ) Soient I un ensemble X fini et (zi )i∈I une famille de nombres complexes indexée par I. La somme
des zi , i parcourant l’ensemble I, est notée zi .
i∈I
n
X X
Dans le cas où I = Jm, nK où m, n ∈ Z sont tels que m 6 n, on la note plus couramment zk ou zk . Elle vaut
k=m m6k6n
zm + zm+1 + zm+2 + . . . + zn .
X
Dans le cas où I = Jm, nK × Jp, qK où m, n, p, q ∈ Z sont tels que m 6 n et p 6 q, on la note plus couramment zkl .
m6k6n
p6l6q

Remarque La lettre k peut être remplacée par tout symbole distinct des bornes m et n et ne figurant pas dans les zk .

P
   En pratique Le symbole est utilisé très souvent en mathématiques. Quand vous êtes bloqués devant une somme
quelconque, écrivez-la in extenso, i.e. en détaillant les termes qui la composent ; les choses peuvent vous paraître plus claires
n
X √ √ √ √ √ √
alors. Par exemple, pour étudier la somme k, on pourra l’écrire 1 + 2 + 3 + . . . + n − 1 + n.
k=1

k=m k=m+1 k=n (n−m+1) fois

n
X z }| {
z}|{ z}|{ z}|{
Exemple Soit α ∈ C. α = α + α + . . . + α = α + α + . . . + α = (n − m + 1)α.
k=m

n   n+1
X 1 1 1 1 1 1 1 1 1 1 1 1 X 1
Exemple −1+ = 1 + + + ... + + −1+ = + +...+ + + = .
k n+1 2 3 n−1 n n+1 2 3 n−1 n n+1 k
k=1 k=2

n
X n
X n
X
$ $ $ Attention ! Dans une somme du type zk , il convient de ne jamais confondre k et n. Ainsi k et n sont
k=1 k=1 k=1
n
X n
X
deux quantités tout à fait différentes : n = n + n + . . . + n 6= 1 + 2 + 3 + . . . + (n − 1) + n = k.
| {z }
k=1 k=1
n fois

3.1.2 Changements d’indice

Le changement d’indice est une opération très courante. Les exemples valent ici mieux qu’un long discours.

Exemple
n n+1
X 1 1 1 1 X 1
• 2
= 1 + 2
+ 2
+ . . . + 2
= . On a effectué ici le changement d’indice l = k + 1. Cela revient à
k=0
(k + 1) 2 3 (n + 1) l=1
l2
remplacer tous les k de la somme initiale par des l − 1. Mais il faut aussi changer les bornes. Quand k varie de 0 à n, que
fait l = k + 1 ? Il varie de 0 + 1 = 1 à n + 1.
9
X 7
X
• r r = 22 + 33 + 44 + . . . + 99 = (s + 2)s+2 . On a effectué ici le changement d’indice r = s + 2. Pendant que r varie
r=2 s=0
de 2 à 9, s = r − 2 varie de 0 à 7.

12
c Christophe Bertault - MPSI

3.1.3 Simplifications téléscopiques

Le résultat suivant est à la fois stupide et essentiel : les simplifications télescopiques sont partout.

Théorème (Simplifications télescopiques) Soit (zk )m6k6n+1 une famille de nombres complexes.
n
X
(zk+1 − zk ) = zn+1 − zm .
k=m

Démonstration
simplification simplification simplification
n
X z }| {z }| { z }| {
(zk+1 − zk ) = (zn+1 −zn ) + (zn −zn−1 ) + (zn−1 −zn−2 ) + . . . + (zm+2 −zm+1 ) + (zm+1 −zm ) = zn+1 − zm . 
k=m

n n  
X 1 X 1 1 1
Exemple = − =1− .
k=1
k(k + 1) k=1
k k + 1 n + 1

3.1.4 Sommes doubles

P
Théorème (Permutation des ) Soit (zij )16i,j6n une famille de nombres complexes.
n
n X n
n X n Xj n X n j−1
n X n−1 n
X X X X X X X X X X
zij = zij = zij , zij = zij = zij , zij = zij = zij .
16i6n i=1 j=1 j=1 i=1 16i6j6n j=1 i=1 i=1 j=i 16i<j6n j=2 i=1 i=1 j=i+1
16j6n

Démonstration
• Première série d’égalités : La famille (zij )16i,j6n peut être présentée sous la forme d’un tableau à deux
entrées :
j 1 2 3 ··· n X X
i Calculer la somme zij , notée aussi zij , c’est calcu-
16i6n 16i,j6n
1 z11 z12 z13 ··· z1n 16j6n
2 z21 z22 z23 ··· z2n ler la somme de tous les termes de ce tableau. On peut effec-
3 z31 z32 z33 ··· z3n tuer ce calcul de différentes manières. Voyons ce qui se passe si
.. .. .. .. .. .. on effectue d’abord la somme des termes de chaque ligne, avant
. . . . . .
d’additionner les résultats obtenus.
n zn1 zn2 zn3 ··· znn
n
X
Pour tout i ∈ J1, nK, la somme des termes de la ième ligne s’écrit zij ; c’est un certain nombre complexe
j=1
n X
X n
qui dépend de i. Faire la somme des résultats ainsi obtenus sur chaque ligne, c’est faire la somme zij .
i=1 j=1
X n X
X n
Ceci explique qu’on ait : zij = zij . On démontre la seconde égalité en sommant d’abord
16i6n i=1 j=1
16j6n
sur chaque colonne.
X
• Seconde série d’égalités : Calculer la somme zij , c’est calculer la somme de termes du tableau
16i6j6n
suivant :
Pour tout j ∈ J1, nK, la somme des termes de la j ème colonne
j
j 1 2 3 ··· n X
i de ce tableau s’écrit zij ; c’est un certain nombre complexe
i=1
1 z11 z12 z13 ··· z1n
qui dépend de j. Faire la somme des résultats ainsi obtenus sur
2 z22 z23 ··· z2n Xn X j
3 z33 ··· z3n chaque colonne, c’est faire la somme zij . Ceci explique
.. .. .. j=1 i=1
. . . j
n X
X X
n znn qu’on ait : zij = zij .
16i6j6n j=1 i=1
On démontre la seconde égalité en sommant d’abord sur chaque ligne.

13
c Christophe Bertault - MPSI

• Troisième série d’égalités : A vous de jouer ! Je vous donne juste le tableau correspondant :
j 1 2 3 ··· n
i
1 × z12 z13 ··· z1n
2 × z23 ··· z2n
3 × ··· z3n
.. .. ..
. . .
n ×


Q
3.2 Le symbole produit
P Q
Nous passerons plus vite sur les produits que sur les sommes ; car une fois qu’on a compris , on a compris .

Q
Définition (Symbole ) Soient I un Y ensemble fini et (zi )i∈I une famille de nombres complexes indexée par I. Le produit
des zi , i parcourant l’ensemble I, est noté zi .
i∈I

(n−m+1) fois
n
Y z }| {
Exemple Soit α ∈ C. α = α × α × . . . × α = αn−m+1 .
k=m

n
Y
Définition (Factorielle) Pour tout n ∈ N× , on appelle factorielle n, notée n!, le nombre n! = k = 1 × 2 × 3 × . . . × n.
k=1
Par convention, 0! = 1.

n
Y n
Y n
Y
$ $ $ Attention ! Dans un produit du type zk , il convient de ne jamais confondre k et n. Ainsi k et n sont
k=1 k=1 k=1
n
Y Yn
deux quantités tout à fait différentes : nn = n = n × n × . . . × n 6= 1 × 2 × 3 × . . . × (n − 1) × n = k = n!.
| {z }
k=1 k=1
n fois

Théorème (Simplifications télescopiques) Soit (zk )m6k6n+1 une famille de nombres complexes non nuls.
n
Y zk+1 zn+1
= .
k=m
z k zm

Q
Théorème (Permutation des ) Soit (zij )16i,j6n une famille de nombres complexes.
n
n Y n
n Y n Yj n Y n n j−1 n−1 n
Y Y Y Y Y Y Y Y Y Y Y
zij = zij = zij , zij = zij = zij , zij = zij = zij .
16i6n i=1 j=1 j=1 i=1 16i6j6n j=1 i=1 i=1 j=i 16i<j6n j=2 i=1 i=1 j=i+1
16j6n

Y Y
Exemple La notation (ij 2 ) est un résumé de la notation (ij 2 ).
16i,j6n 16i6n
16j6n

n Y
n n n
! n
! n
!n n
!n n
!2n
Y 2
Y 2
Y Y 2
Y Y 2
Y Y
(ij ) = (ij ) = n
i j = n
i j = i j = (n!)n (n!)2n = (n!)3n .
16i,j6n i=1 j=1 i=1 j=1 i=1 j=1 i=1 j=1

P Q
$ $ $ Attention ! Les symboles et ne peuvent être permutés en général. Ainsi :
n X
Y n n
Y n
X n Y
X n
1 = n = nn 6= n = 1 = 1.
i=1 j=1 i=1 j=1 j=1 i=1

Ce n’est pas étonnant, car c’est déjà faux avec deux termes : (a + b)(c + d) 6= ab + cd en général.

14
c Christophe Bertault - MPSI

3.3 Quelques formules à connaître par cœur

La définition et les formules suivantes sont en principe de simples rappels.

Définition (Coefficients binomiaux)

!
n
• Pour tous n, k ∈ N tels que k 6 n, on appelle (coefficient binomial) k parmi n, noté , le nombre :
k
!
n n!
= .
k k!(n − k)!
! !
n n
• Pour tout n ∈ N et pour tout k ∈ J0, nK : = .
k n−k
! ! ! ! ! !
n n n n n n n(n − 1)
• Pour tout n ∈ N : = = 1, = =n et = = .
0 n 1 n−1 2 n−2 2
! ! !
n n n+1
• Formule de Pascal : Pour n > 1, et pour tout k ∈ J1, nK : + = .
k−1 k k

   Explication On peut calculer tous les coefficients

! binomiaux à l’aide de la formule de Pascal, en construisant un
n
tableau qu’on appelle le triangle de Pascal. On y range dans la case qui se trouve à l’intersection de la ligne n et de la
k
colonne k.
k 0 1 2 3 4 5 ...
zoom ! !
n n n
0 1 +
k−1 k
1 1 1
2 1 2 1 zoom !
n+1
3 1 3 3 1 =
4 1 4 6 4 1 k
5 1 5 10 10 5 1
.. .. ..
. . . Formule de Pascal

n
!
n
X n k n−k
Théorème (Formule du binôme de Newton) Soient n ∈ N et a, b ∈ C. (a + b) = a b .
k
k=0

Démonstration Soient a, b ∈ C fixés. Raisonnons par récurrence.

! 0
!
0 0 0 0−0 X 0 k 0−k
• Initialisation : (a + b) = 1 = a b = a b .
0 k=0
k
n
!
X n k n−k
• Hérédité : Soit n ∈ N. On suppose que (a + b)n = a b .
k
k=0

n
! n
! n
!
n+1 n
X n k n−k X n k n−k X n l n−l
(a + b) = (a + b)(a + b) = (a + b) a b =a a b +b ab
k k l
k=0 k=0 l=0
n
! n
! n−1
! n
!
X n k+1 n−k X n l n−l+1 n+1
X n k+1 n−k X n l n−l+1
= a b + ab =a + a b + ab + bn+1
k=0
k l=0
l k=0
k l=1
l
n
! n
!
X n 0 0 X n l n−l+1
= an+1 + 0 −1
ak bn−k +1 + ab + bn+1 (changement d’indice k0 = k + 1)
k l
k0 =1 l=1
n
" ! !#
X n n
= an+1 + + ak b(n+1)−k + bn+1
k=1
k − 1 k

15
c Christophe Bertault - MPSI

n
!
n+1
X n + 1 k (n+1)−k
=a + a b + bn+1 (formule de Pascal)
k
k=1
n+1
!
X n + 1 k (n+1)−k
= a b . Fin de la récurrence. 
k=0
k

n n
X n(n + 1) X n(n + 1)(2n + 1)
Théorème Soit n ∈ N. k= , k2 = .
k=0
2 k=0
6

Démonstration
n
X
• Notons Sn = k. Effectuant dans Sn le changement d’indice l = n − k, nous obtenons la chaîne d’égalités
k=0
n n n
X X X n(n + 1)
Sn = (n − l) = n− l = n(n + 1) − Sn . Ceci montre que 2Sn = n(n + 1), donc que Sn = .
l=0 l=0 l=0
2

• Pour tout k ∈ J0, nK : (k + 1)3 − k3 = 3k2 + 3k + 1 via la formule du binôme de Newton.

n h
X i Xn n
X n
X
Sommons toutes ces identités, de k = 0 à k = n : (k + 1)3 − k3 = 3 k2 + 3 k+ 1. La
k=0 k=0 k=0 k=0
n
X
somme de gauche est le lieu d’une simplification télescopique ; d’autre part nous venons de calculer k et
k=0
n n
X X n(n + 1)
savons que 1 = (n + 1). Du coup : (n + 1)3 = 3 k2 + 3 + (n + 1).
k=0 k=0
2
n
X 2
Isolant k et simplifiant les calculs aisément, nous obtenons le résultat voulu. 
k=0

n−1
X
Théorème Soient n ∈ N et a, b ∈ C. an − bn = (a − b) ak bn−k−1 .
k=0

$ $ $ Attention ! Gare à ceux qui confondent cette formule avec la formule du binôme de Newton !

Démonstration Développons le membre de droite de la formule :

n−1
X n−1
X n−1
X n−1
X n−1
X
(a − b) ak bn−k−1 = a ak bn−k−1 − b ak bn−k−1 = ak+1 bn−(k+1) − ak bn−k
k=0 k=0 k=0 k=0 k=0
n n
=a −b par simplification télescopique. 

En particulier, pour b = 1, on obtient l’identité fondamentale suivante :

 n
n−1  q −1
X k si q 6= 1
Corollaire Pour tous n ∈ N et q ∈ C : q = q−1 .
 n si q = 1
k=0

   En pratique Souvent, on n’a pas affaire à des sommes dont l’indice inférieur est 0. Si par exemple on doit calculer
n
X
2k , on commence par mettre en facteur le premier terme puis on effectue un changement d’indice :
k=2

n n n−2
X X l=k−2
X 2n−1 − 1
2k = 22 2k−2 = 4 2l = 4 × = 2n+1 − 4.
k=2 k=2 l=0
2−1

16