Le cours

L'essentiel

Une implication $P \Rightarrow Q$ n'est fausse que si $P$ est vraie et $Q$ fausse. Sa négation est « $P$ et $\text{non } Q$ ». Sa contraposée $\text{non } Q \Rightarrow \text{non } P$ lui est équivalente, sa réciproque non.
On nie une phrase quantifiée en échangeant $\forall$ et $\exists$ dans l'ordre, puis en niant la fin. Savoir nier sans hésiter la définition de la limite, de la continuité, de la borne supérieure.
L'ordre des quantificateurs change le sens : « $\forall x \in \R, \ \exists y \in \R, \ y > x$ » est vraie, « $\exists y \in \R, \ \forall x \in \R, \ y > x$ » est fausse.
Six modes de raisonnement : direct, contraposée, absurde, disjonction de cas, analyse-synthèse, récurrence (simple, double, forte).
Savoir refaire : si $n^2$ est pair alors $n$ est pair (contraposée), $\sqrt{2}$ est irrationnel (absurde), la décomposition paire-impaire d'une fonction (analyse-synthèse).
Une récurrence a trois étapes nommées : initialisation, hérédité, conclusion. Savoir rédiger une récurrence simple, double et forte.

Pourquoi ce chapitre

Toute démonstration de prépa repose sur un petit nombre de règles de logique et de schémas de raisonnement. Ce premier chapitre fixe le vocabulaire (proposition, connecteur, quantificateur) et les règles de négation. Il présente les six modes de raisonnement utilisés toute l'année : raisonnement direct, contraposée, absurde, disjonction de cas, analyse-synthèse et récurrence. Il fixe enfin les règles de rédaction, car une copie est jugée sur la validité de l'enchaînement logique, pas seulement sur le résultat.

1Propositions et connecteurs

Proposition

Définition 1.1Proposition

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

Exemple 1.2

« $2$ est pair » est une proposition vraie. « $3$ est pair » est une proposition fausse. En revanche, « $x$ est pair » n'est pas une proposition tant que $x$ n'est pas fixé.

Définition 1.3Prédicat

Un énoncé qui dépend d'une variable $x$ , comme « $x$ est pair », est un prédicat, noté $P(x)$ . Il devient une proposition quand on donne une valeur à $x$ , ou quand on quantifie $x$ (voir la section sur les quantificateurs).

Négation

Définition 1.4Négation

La négation d'une proposition $P$ , notée $\text{non } P$ , est la proposition qui est vraie exactement quand $P$ est fausse.

Propriété 1.5Double négation

Pour toute proposition $P$ , la proposition $\text{non}(\text{non } P)$ a la même valeur de vérité que $P$ .

Démonstration

Si $P$ est vraie, alors $\text{non } P$ est fausse, donc $\text{non}(\text{non } P)$ est vraie. Si $P$ est fausse, alors $\text{non } P$ est vraie, donc $\text{non}(\text{non } P)$ est fausse. Dans les deux cas, $\text{non}(\text{non } P)$ et $P$ ont la même valeur de vérité.

Conjonction et disjonction

Définition 1.6Conjonction, disjonction

Soient $P$ et $Q$ deux propositions.

La conjonction « $P$ et $Q$ » est vraie quand $P$ et $Q$ sont toutes les deux vraies, et fausse sinon.
La disjonction « $P$ ou $Q$ » est vraie dès que l'une au moins des deux est vraie, et fausse seulement quand les deux sont fausses.

On résume ces définitions dans une table de vérité, où V signifie vrai et F faux.

$\begin{array}{|c|c|c|c|} \hline P & Q & P \text{ et } Q & P \text{ ou } Q \\ \hline V & V & V & V \\ V & F & F & V \\ F & V & F & V \\ F & F & F & F \\ \hline \end{array}$

AttentionLe « ou » est inclusif

En mathématiques, le « ou » est inclusif : quand $P$ et $Q$ sont toutes les deux vraies, « $P$ ou $Q$ » est vraie. Il ne signifie pas « l'un ou l'autre, mais pas les deux » comme dans « fromage ou dessert ».

Proposition 1.7Règles de De Morgan

Soient $P$ et $Q$ deux propositions.

La négation de « $P$ et $Q$ » est « $\text{non } P$ ou $\text{non } Q$ ».
La négation de « $P$ ou $Q$ » est « $\text{non } P$ et $\text{non } Q$ ».

Démonstration

On compare les valeurs de vérité dans les quatre cas possibles.

$\begin{array}{|c|c|c|c|} \hline P & Q & \text{non}(P \text{ et } Q) & \text{non } P \text{ ou non } Q \\ \hline V & V & F & F \\ V & F & V & V \\ F & V & V & V \\ F & F & V & V \\ \hline \end{array}$

La colonne de $\text{non}(P \text{ et } Q)$ coïncide ligne à ligne avec celle de « $\text{non } P$ ou $\text{non } Q$ », ce qui prouve la première règle. Pour la seconde, on compare de même :

$\begin{array}{|c|c|c|c|} \hline P & Q & \text{non}(P \text{ ou } Q) & \text{non } P \text{ et non } Q \\ \hline V & V & F & F \\ V & F & F & F \\ F & V & F & F \\ F & F & V & V \\ \hline \end{array}$

Les deux colonnes coïncident : « $\text{non } P$ et $\text{non } Q$ » est vraie seulement quand $P$ et $Q$ sont fausses, sur la dernière ligne, exactement comme $\text{non}(P \text{ ou } Q)$ .

Exemple 1.8

Soit $x$ un réel. Dire que $x \in [0, 1]$ , c'est dire « $x \geqslant 0$ et $x \leqslant 1$ ». Par la règle de De Morgan, dire que $x \notin [0, 1]$ revient à dire « $x < 0$ ou $x > 1$ ».

Implication

Définition 1.9Implication

Soient $P$ et $Q$ deux propositions. L'implication « $P$ implique $Q$ », notée $P \Rightarrow Q$ , est fausse dans un seul cas : $P$ vraie et $Q$ fausse. Elle est vraie dans les trois autres cas, en particulier dès que $P$ est fausse.

$\begin{array}{|c|c|c|} \hline P & Q & P \Rightarrow Q \\ \hline V & V & V \\ V & F & F \\ F & V & V \\ F & F & V \\ \hline \end{array}$

Proposition 1.10Implication et disjonction

L'implication $P \Rightarrow Q$ a la même valeur de vérité que « $\text{non } P$ ou $Q$ ».

Démonstration

La proposition « $\text{non } P$ ou $Q$ » est fausse exactement quand $\text{non } P$ et $Q$ sont fausses toutes les deux, c'est-à-dire quand $P$ est vraie et $Q$ fausse. C'est exactement le seul cas où $P \Rightarrow Q$ est fausse. Les deux propositions sont donc vraies ou fausses en même temps.

Proposition 1.11Négation d'une implication

La négation de $P \Rightarrow Q$ est « $P$ et $\text{non } Q$ ».

Démonstration

D'après la proposition précédente, $P \Rightarrow Q$ a même valeur de vérité que « $\text{non } P$ ou $Q$ ». Par la règle de De Morgan, sa négation est « $\text{non}(\text{non } P)$ et $\text{non } Q$ », c'est-à-dire, par double négation, « $P$ et $\text{non } Q$ ».

RemarqueContre-exemple

Pour prouver qu'une implication est fausse, on exhibe un cas où l'hypothèse est vraie et la conclusion fausse. C'est ce qu'on appelle un contre-exemple.

Exemple 1.12Hypothèse fausse

Une implication dont l'hypothèse est fausse est vraie. Ainsi « si $0 = 1$ alors $2 = 3$ » est une proposition vraie.

Définition 1.13Condition nécessaire, condition suffisante

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

Exemple 1.14

Pour un entier $n$ , « $n$ est multiple de $4$ » est une condition suffisante pour que « $n$ est pair ». Inversement, « $n$ est pair » est une condition nécessaire pour que « $n$ est multiple de $4$ ».

Réciproque et contraposée

Définition 1.15Réciproque, contraposée

Soit l'implication $P \Rightarrow Q$ .

Sa réciproque est l'implication $Q \Rightarrow P$ .
Sa contraposée est l'implication $\text{non } Q \Rightarrow \text{non } P$ .

AttentionRéciproque

Une implication et sa réciproque n'ont aucune raison d'être vraies en même temps. Pour un entier $n$ , l'implication « $n$ est multiple de $4 \Rightarrow n$ est pair » est vraie. Sa réciproque « $n$ est pair $\Rightarrow n$ est multiple de $4$ » est fausse : $n = 2$ est un contre-exemple.

Proposition 1.16Contraposée

Une implication et sa contraposée sont toujours vraies ou fausses en même temps.

Démonstration

La contraposée $\text{non } Q \Rightarrow \text{non } P$ a même valeur de vérité que « $\text{non}(\text{non } Q)$ ou $\text{non } P$ », c'est-à-dire, par double négation, que « $Q$ ou $\text{non } P$ ». Comme le « ou » ne dépend pas de l'ordre de ses termes, c'est « $\text{non } P$ ou $Q$ », qui a même valeur de vérité que $P \Rightarrow Q$ .

Cette proposition est la base du raisonnement par contraposée, étudié plus loin.

Équivalence

Définition 1.17Équivalence

Soient $P$ et $Q$ deux propositions. L'équivalence $P \Leftrightarrow Q$ est la proposition « $P \Rightarrow Q$ et $Q \Rightarrow P$ ». On dit que $P$ et $Q$ sont équivalentes, ou que $P$ est une condition nécessaire et suffisante pour $Q$ .

RemarqueDémontrer une équivalence

Pour démontrer une équivalence, on démontre en général les deux implications séparément. On peut enchaîner des équivalences seulement quand chaque étape du calcul est réversible.

AttentionDes équivalences qui n'en sont pas

Il ne faut pas enchaîner des « $\Leftrightarrow$ » alors qu'une étape n'est qu'une implication. Trois opérations ne conservent qu'une implication : élever au carré, multiplier par une expression qui peut s'annuler, appliquer une fonction non injective. Par exemple $x = 1 \Rightarrow x^2 = 1$ est vraie, mais $x^2 = 1$ n'entraîne pas $x = 1$ : le réel $x = -1$ est un contre-exemple.

2Quantificateurs

Quantificateur universel

Définition 2.1Quantificateur universel

Soient $E$ un ensemble et $P(x)$ un prédicat portant sur les éléments $x$ de $E$ . La proposition « pour tout $x$ de $E$ , $P(x)$ », notée $\forall x \in E, \ P(x),$ affirme que $P(x)$ est vraie pour chaque élément $x$ de $E$ .

RemarqueDémontrer une proposition universelle

Pour démontrer « $\forall x \in E, \ P(x)$ », on prend un $x$ quelconque de $E$ (« soit $x$ dans $E$ ») et on prouve $P(x)$ sans rien supposer de particulier sur $x$ .

Quantificateur existentiel

Définition 2.2Quantificateur existentiel

La proposition « il existe $x$ dans $E$ tel que $P(x)$ », notée $\exists x \in E, \ P(x),$ affirme qu'au moins un élément $x$ de $E$ vérifie $P(x)$ . La notation $\exists !\, x \in E, \ P(x)$ signifie « il existe un unique $x$ dans $E$ tel que $P(x)$ ».

RemarqueDémontrer une proposition existentielle

Pour démontrer « $\exists x \in E, \ P(x)$ », on exhibe un $x$ précis et on vérifie $P(x)$ , ou bien on utilise un théorème d'existence.

Négation d'une phrase quantifiée

Proposition 2.3Négation des quantificateurs

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

Démonstration

La proposition « $\forall x \in E, \ P(x)$ » est fausse exactement quand $P(x)$ n'est pas vraie pour chaque élément de $E$ , c'est-à-dire quand il existe au moins un $x$ de $E$ pour lequel $P(x)$ est fausse, soit $\text{non } P(x)$ vraie. C'est la première règle. Pour la seconde, on applique la première au prédicat $\text{non } P(x)$ : la négation de « $\forall x \in E, \ \text{non } P(x)$ » est « $\exists x \in E, \ \text{non}(\text{non } P(x))$ », c'est-à-dire « $\exists x \in E, \ P(x)$ ». En niant les deux membres, la négation de « $\exists x \in E, \ P(x)$ » est donc « $\forall x \in E, \ \text{non } P(x)$ ».

RemarqueRègle pratique

On nie une phrase à plusieurs quantificateurs en changeant chaque quantificateur en l'autre, dans l'ordre, puis en niant la proposition finale. Les ensembles auxquels appartiennent les variables ne changent pas.

Exemple 2.4Négation de la convergence

Soient $(u_n)$ une suite réelle et $\ell$ un réel. La suite $(u_n)$ converge vers $\ell$ signifie : $\forall \varepsilon > 0, \ \exists N \in \N, \ \forall n \geqslant N, \ \abs{u_n - \ell} \leqslant \varepsilon.$ La négation est : $\exists \varepsilon > 0, \ \forall N \in \N, \ \exists n \geqslant N, \ \abs{u_n - \ell} > \varepsilon.$ Savoir écrire cette négation sans hésiter est un exigible.

AttentionNier la condition « $\varepsilon > 0$ »

La négation porte sur la proposition finale, pas sur le domaine des variables. La négation de « $\forall \varepsilon > 0, \ldots$ » commence par « $\exists \varepsilon > 0$ », et non par « $\exists \varepsilon \leqslant 0$ ».

Ordre des quantificateurs

Propriété 2.5Ordre des quantificateurs

On peut permuter deux quantificateurs de même nature : « $\forall x, \ \forall y, \ P(x, y)$ » équivaut à « $\forall y, \ \forall x, \ P(x, y)$ », et de même avec deux $\exists$ . On ne peut pas, en général, permuter un $\forall$ et un $\exists$ .

Exemple 2.6Échanger les quantificateurs change le sens

La proposition « $\forall x \in \R, \ \exists y \in \R, \ y > x$ » est vraie : pour un réel $x$ donné, $y = x + 1$ convient. La proposition « $\exists y \in \R, \ \forall x \in \R, \ y > x$ » est fausse : il n'existe pas de réel plus grand que tous les réels, puisqu'un tel $y$ devrait vérifier $y > y$ en prenant $x = y$ .

RemarqueDépendance

Dans « $\forall x, \ \exists y$ », le $y$ peut dépendre de $x$ . Dans « $\exists y, \ \forall x$ », le $y$ est le même pour tous les $x$ . C'est pourquoi on écrit parfois $y_x$ pour rappeler cette dépendance.

Règles d'écriture

AttentionLes quantificateurs ne sont pas des abréviations

On ne mélange pas les symboles $\forall$ et $\exists$ à une phrase en français. On écrit soit une phrase complète en français, soit une formule entièrement symbolique. « Pour tout réel $x$ , $x^2 \geqslant 0$ » et « $\forall x \in \R, \ x^2 \geqslant 0$ » sont corrects, un mélange des deux ne l'est pas.

RemarqueVariable muette

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

3Les modes de raisonnement

Raisonnement direct

RemarqueRaisonnement direct (déduction)

Pour prouver $P \Rightarrow Q$ , on suppose $P$ vraie et on en déduit $Q$ par une chaîne d'implications vraies. C'est le mode par défaut.

Exemple 3.1

Soit $n$ un entier pair. Montrons que $n^2$ est pair. Par hypothèse, il existe $k \in \Z$ tel que $n = 2k$ . Alors $n^2 = 4k^2 = 2(2k^2)$ avec $2k^2 \in \Z$ , donc $n^2$ est pair.

Raisonnement par contraposée

Pour prouver $P \Rightarrow Q$ , on prouve $\text{non } Q \Rightarrow \text{non } P$ , ce qui suffit puisque les deux implications ont même valeur de vérité. C'est utile quand la négation de $Q$ est plus maniable que $P$ .

Proposition 3.2Parité d'un carré

Soit $n$ un entier. Si $n^2$ est pair, alors $n$ est pair.

Démonstration

Raisonnons par contraposée : montrons que si $n$ est impair, alors $n^2$ est impair. Supposons $n$ impair. Il existe $k \in \Z$ tel que $n = 2k + 1$ . Alors $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,$ avec $2k^2 + 2k \in \Z$ , donc $n^2$ est impair. La contraposée est prouvée, donc l'implication aussi : si $n^2$ est pair, alors $n$ est pair.

Raisonnement par l'absurde

Pour prouver une proposition $P$ , on suppose $\text{non } P$ et on aboutit à une contradiction, c'est-à-dire à une proposition à la fois vraie et fausse. On en conclut que $\text{non } P$ est fausse, donc que $P$ est vraie.

Proposition 3.3Irrationalité de $\sqrt{2}$

Le réel $\sqrt{2}$ est irrationnel.

Démonstration

Raisonnons par l'absurde et supposons $\sqrt{2}$ rationnel. Comme $\sqrt{2} > 0$ , on peut écrire $\sqrt{2} = \frac{p}{q}$ avec $p$ et $q$ des entiers naturels non nuls premiers entre eux (on simplifie la fraction autant que possible). En élevant au carré, $2 = \frac{p^2}{q^2}$ , donc $p^2 = 2q^2.$ Ainsi $p^2$ est pair, donc $p$ est pair d'après la proposition sur la parité d'un carré, démontrée par contraposée. Il existe donc un entier $m$ tel que $p = 2m$ . En reportant, $4m^2 = 2q^2$ , soit $q^2 = 2m^2$ . Donc $q^2$ est pair, et par la même proposition $q$ est pair. Alors $2$ divise à la fois $p$ et $q$ , ce qui contredit le fait que $p$ et $q$ sont premiers entre eux. L'hypothèse est donc fausse : $\sqrt{2}$ est irrationnel.

AttentionContraposée ou absurde

Il ne faut pas confondre les deux. La contraposée démontre une implication en la retournant. L'absurde démontre n'importe quelle proposition en supposant son contraire. Le raisonnement par l'absurde est souvent moins lisible : quand une contraposée suffit, on la préfère.

Disjonction de cas

Pour prouver une proposition $P$ , on découpe la situation en cas qui couvrent toutes les possibilités, et on prouve $P$ dans chaque cas.

Proposition 3.4

Pour tout entier $n$ , l'entier $n(n + 1)$ est pair.

Démonstration

Soit $n$ un entier. Tout entier est pair ou impair, donc les deux cas suivants couvrent toutes les possibilités.

Si $n$ est pair, il existe $k \in \Z$ tel que $n = 2k$ , et $n(n + 1) = 2\big(k(n + 1)\big)$ est pair.
Si $n$ est impair, alors $n + 1$ est pair : il existe $k \in \Z$ tel que $n + 1 = 2k$ , et $n(n + 1) = 2(nk)$ est pair.

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

AttentionDes cas exhaustifs

Il faut vérifier, et écrire, que les cas étudiés sont exhaustifs. Un cas oublié rend la preuve fausse.

Analyse-synthèse

RemarquePrincipe de l'analyse-synthèse

Pour déterminer tous les objets vérifiant une propriété, on procède en deux temps.

Analyse : on suppose qu'un objet convient, et on en déduit, par implications, la forme qu'il doit avoir. On obtient des candidats. À ce stade on n'a prouvé qu'une chose : si une solution existe, elle est parmi les candidats. C'est une condition nécessaire.
Synthèse : on vérifie quels candidats conviennent réellement, en les reportant dans la propriété de départ. C'est une condition suffisante.

Quand l'analyse aboutit à un seul candidat, elle prouve l'unicité, et la synthèse prouve l'existence.

Proposition 3.5Décomposition paire-impaire

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

Démonstration

Soit $f : \R \to \R$ .

Analyse. Supposons que $f = p + i$ avec $p : \R \to \R$ paire et $i : \R \to \R$ impaire. Pour tout réel $x$ , $f(x) = p(x) + i(x) \quad \text{et} \quad f(-x) = p(-x) + i(-x) = p(x) - i(x).$ En ajoutant puis en soustrayant ces deux égalités, on obtient pour tout réel $x$ : $p(x) = \frac{f(x) + f(-x)}{2}, \qquad i(x) = \frac{f(x) - f(-x)}{2}.$ Les fonctions $p$ et $i$ sont donc entièrement déterminées par $f$ : si une décomposition existe, elle est unique.

Synthèse. Définissons $p$ et $i$ sur $\R$ par les formules précédentes. Pour tout réel $x$ , $p(-x) = \frac{f(-x) + f(x)}{2} = p(x), \qquad i(-x) = \frac{f(-x) - f(x)}{2} = -i(x),$ donc $p$ est paire et $i$ est impaire. De plus $p(x) + i(x) = \frac{2f(x)}{2} = f(x)$ , donc $p + i = f$ . Une décomposition existe.

L'existence et l'unicité sont établies.

Raisonnement par récurrence

Théorème 3.6Principe de récurrence

Soient $n_0 \in \N$ et $P(n)$ un prédicat défini pour les entiers $n \geqslant n_0$ . On suppose :

initialisation : $P(n_0)$ est vraie ;
hérédité : pour tout entier $n \geqslant n_0$ , si $P(n)$ est vraie, alors $P(n + 1)$ est vraie.

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

Démonstration

On admet la propriété fondamentale de $\N$ : toute partie non vide de $\N$ possède un plus petit élément.

Raisonnons par l'absurde et supposons que $P(n)$ soit fausse pour au moins un entier $n \geqslant n_0$ . L'ensemble $A = \{ n \in \N \mid n \geqslant n_0 \text{ et } P(n) \text{ est fausse} \}$ est alors une partie non vide de $\N$ . Elle possède donc un plus petit élément $m$ . Comme $P(n_0)$ est vraie, $m \neq n_0$ , donc $m > n_0$ , soit $m - 1 \geqslant n_0$ . Comme $m - 1 < m$ et que $m$ est le plus petit élément de $A$ , on a $m - 1 \notin A$ , donc $P(m - 1)$ est vraie. L'hérédité appliquée au rang $m - 1$ donne alors $P(m)$ vraie, ce qui contredit $m \in A$ . Donc $P(n)$ est vraie pour tout entier $n \geqslant n_0$ .

Remarque

Aucune construction ni axiomatique de $\N$ n'est exigible. La propriété du plus petit élément est admise.

Une récurrence se rédige en trois étapes nommées.

Initialisation : on vérifie $P(n_0)$ .
Hérédité : on suppose $P(n)$ vraie pour un entier $n \geqslant n_0$ fixé (c'est l'hypothèse de récurrence) et on prouve $P(n + 1)$ .
Conclusion : par le principe de récurrence, $P(n)$ est vraie pour tout $n \geqslant n_0$ .

Proposition 3.7Somme des premiers entiers

Pour tout entier $n \geqslant 1$ , $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.$

Démonstration

Pour $n \geqslant 1$ , notons $P(n)$ la proposition « $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$ ». Raisonnons par récurrence sur $n \geqslant 1$ .

Initialisation : pour $n = 1$ , le membre de gauche vaut $1$ et celui de droite vaut $\frac{1 \times 2}{2} = 1$ . Donc $P(1)$ est vraie.

Hérédité : soit $n \geqslant 1$ un entier fixé tel que $P(n)$ soit vraie. Alors $1 + \cdots + n + (n + 1) = \frac{n(n + 1)}{2} + (n + 1) = \frac{(n + 1)(n + 2)}{2},$ ce qui est $P(n + 1)$ .

Conclusion : par récurrence, $P(n)$ est vraie pour tout entier $n \geqslant 1$ .

Propriété 3.8Récurrence double

Soient $n_0 \in \N$ et $P(n)$ un prédicat défini pour $n \geqslant n_0$ . Si $P(n_0)$ et $P(n_0 + 1)$ sont vraies, et si pour tout $n \geqslant n_0$ , « $P(n)$ et $P(n + 1)$ » entraîne $P(n + 2)$ , alors $P(n)$ est vraie pour tout $n \geqslant n_0$ .

Démonstration

Pour $n \geqslant n_0$ , notons $Q(n)$ la proposition « $P(n)$ et $P(n + 1)$ ». On prouve $Q(n)$ pour tout $n \geqslant n_0$ par récurrence simple. Initialisation : $Q(n_0)$ est « $P(n_0)$ et $P(n_0 + 1)$ », vraie par hypothèse. Hérédité : soit $n \geqslant n_0$ tel que $Q(n)$ soit vraie. Alors $P(n + 1)$ est vraie, et $P(n)$ et $P(n + 1)$ entraînent $P(n + 2)$ , donc $Q(n + 1)$ est vraie. Par récurrence, $Q(n)$ est vraie pour tout $n \geqslant n_0$ , donc en particulier $P(n)$ .

Exemple 3.9Suites récurrentes linéaires d'ordre deux

La récurrence double sert pour les suites définies par $u_{n+2} = a u_{n+1} + b u_n$ . Par exemple, si $u_0 = 0$ , $u_1 = 1$ et $u_{n+2} = 3u_{n+1} - 2u_n$ , on montre par récurrence double que $u_n = 2^n - 1$ pour tout $n \in \N$ . Initialisation : $2^0 - 1 = 0 = u_0$ et $2^1 - 1 = 1 = u_1$ . Hérédité : si $u_n = 2^n - 1$ et $u_{n+1} = 2^{n+1} - 1$ , alors $u_{n+2} = 3(2^{n+1} - 1) - 2(2^n - 1) = 3 \cdot 2^{n+1} - 2^{n+1} - 1 = 2^{n+2} - 1.$

Propriété 3.10Récurrence forte

Soient $n_0 \in \N$ et $P(n)$ un prédicat défini pour $n \geqslant n_0$ . Si $P(n_0)$ est vraie, et si pour tout $n \geqslant n_0$ , la vérité de $P(k)$ pour tout entier $k$ compris entre $n_0$ et $n$ entraîne $P(n + 1)$ , alors $P(n)$ est vraie pour tout $n \geqslant n_0$ .

Démonstration

Pour $n \geqslant n_0$ , notons $Q(n)$ la proposition « pour tout entier $k$ tel que $n_0 \leqslant k \leqslant n$ , $P(k)$ est vraie ». On prouve $Q(n)$ par récurrence simple. Initialisation : $Q(n_0)$ est $P(n_0)$ , vraie. Hérédité : si $Q(n)$ est vraie, alors l'hypothèse donne $P(n + 1)$ , et $Q(n)$ avec $P(n + 1)$ donne $Q(n + 1)$ . Par récurrence, $Q(n)$ est vraie pour tout $n \geqslant n_0$ , et $Q(n)$ contient $P(n)$ .

Proposition 3.11Existence d'un diviseur premier

Tout entier $n \geqslant 2$ admet un diviseur premier.

Démonstration

Raisonnons par récurrence forte sur $n \geqslant 2$ , avec $P(n)$ : « $n$ admet un diviseur premier ».

Initialisation : $2$ est premier et se divise lui-même, donc $P(2)$ est vraie.

Hérédité : soit $n \geqslant 2$ tel que $P(k)$ soit vraie pour tout entier $k$ compris entre $2$ et $n$ . Si $n + 1$ est premier, il est lui-même un diviseur premier de $n + 1$ . Sinon, $n + 1$ s'écrit $n + 1 = ab$ avec $a$ et $b$ entiers et $2 \leqslant a < n + 1$ , soit $2 \leqslant a \leqslant n$ . Par hypothèse de récurrence forte, $a$ admet un diviseur premier $p$ . Comme $p$ divise $a$ et $a$ divise $n + 1$ , $p$ divise $n + 1$ . Dans les deux cas, $P(n + 1)$ est vraie.

Conclusion : par récurrence forte, tout entier $n \geqslant 2$ admet un diviseur premier.

AttentionOublier l'initialisation

La propriété $P(n)$ : « $n = n + 1$ » est héréditaire, puisque $n = n + 1$ entraîne $n + 1 = n + 2$ . Elle est pourtant fausse pour tout $n$ . Sans initialisation, l'hérédité ne prouve rien.

AttentionHypothèse ou conclusion

Écrire « supposons $P(n)$ vraie pour tout $n$ » est une faute : c'est la conclusion, pas l'hypothèse. On écrit « soit $n \geqslant n_0$ un entier fixé tel que $P(n)$ soit vraie ». Il faut aussi préciser à partir de quel rang $n_0$ la récurrence démarre.

4Rédiger une démonstration

Les règles suivantes valent pour toutes les copies.

Annoncer le mode de raisonnement : « par contraposée », « par récurrence sur $n$ », « raisonnons par l'absurde ».
Introduire chaque objet avant de l'utiliser : « soit $x$ un réel », « soit $\varepsilon > 0$ ».
Distinguer hypothèse et conclusion, en particulier dans une récurrence.
Ne jamais écrire une équivalence si une seule implication est justifiée.
Conclure explicitement : la dernière ligne doit être la proposition à démontrer.

AttentionExemple et contre-exemple

Un contre-exemple suffit à réfuter une propriété universelle. Un exemple ne suffit jamais à la prouver. Ainsi « pour tout entier $n$ , $n^2 + n + 41$ est premier » est vrai pour $n = 0, 1, \ldots, 39$ , mais faux pour $n = 40$ puisque $40^2 + 40 + 41 = 41^2$ .

Méthodes

MéthodeNier une phrase quantifiée

Écrire la phrase entièrement en symboles, quantificateurs en tête.
Changer chaque $\forall$ en $\exists$ et chaque $\exists$ en $\forall$ , dans le même ordre, sans toucher aux ensembles ni aux conditions comme $\varepsilon > 0$ .
Nier la proposition finale : « et » devient « ou » et inversement (De Morgan), $P \Rightarrow Q$ devient « $P$ et $\text{non } Q$ », $\leqslant$ devient $>$ .
Relire en français pour vérifier le sens.

MéthodeDémontrer une implication

Essayer d'abord le raisonnement direct : supposer $P$ , en déduire $Q$ .
Si la négation de $Q$ est plus maniable que $P$ , passer à la contraposée : supposer $\text{non } Q$ , en déduire $\text{non } P$ . L'annoncer.
Pour réfuter une implication, chercher un contre-exemple : un cas où $P$ est vraie et $Q$ fausse.

MéthodeDémontrer une équivalence

Démontrer séparément les deux implications $P \Rightarrow Q$ et $Q \Rightarrow P$ .
N'enchaîner des $\Leftrightarrow$ que si chaque étape est réversible. Se méfier d'une élévation au carré, d'une multiplication par une quantité qui peut s'annuler, d'une fonction non injective.

MéthodeDémontrer une proposition quantifiée

Pour « $\forall x \in E, \ P(x)$ » : écrire « soit $x \in E$ » et prouver $P(x)$ sans rien supposer d'autre sur $x$ .
Pour « $\exists x \in E, \ P(x)$ » : exhiber un $x$ précis et vérifier $P(x)$ , ou invoquer un théorème d'existence.
Pour « $\forall x, \ \exists y$ » : on a le droit de choisir $y$ en fonction de $x$ .

MéthodeProuver une proposition sans prise directe

Si l'étude se découpe naturellement (parité, signe, position), faire une disjonction de cas en justifiant qu'ils sont exhaustifs.
Sinon, raisonner par l'absurde : supposer le contraire, chercher une contradiction, puis conclure.

MéthodeTrouver tous les objets vérifiant une propriété

Raisonner par analyse-synthèse. En analyse, supposer qu'un objet convient et en déduire sa forme : on obtient une liste de candidats (condition nécessaire), et l'unicité si cette liste n'a qu'un élément. En synthèse, vérifier quels candidats conviennent : on obtient l'existence (condition suffisante). Conclure en donnant exactement l'ensemble des solutions.

MéthodeMontrer une propriété pour tous les entiers à partir d'un rang

Définir clairement $P(n)$ et le rang de départ $n_0$ .
Choisir le type de récurrence : simple si $P(n + 1)$ ne dépend que de $P(n)$ , double si elle dépend de $P(n)$ et $P(n - 1)$ , forte si elle dépend de rangs quelconques plus petits.
Rédiger les trois étapes nommées : initialisation (deux rangs pour une récurrence double), hérédité avec un $n$ fixé, conclusion.

Exercices d'application

Exercice 1. Négation d'une continuité

Soient $f : \R \to \R$ et $a \in \R$ . La continuité de $f$ en $a$ s'écrit $\forall \varepsilon > 0, \ \exists \delta > 0, \ \forall x \in \R, \ \abs{x - a} \leqslant \delta \Rightarrow \abs{f(x) - f(a)} \leqslant \varepsilon.$ Écrire la négation de cette proposition.

Voir le corrigé

On échange chaque quantificateur dans l'ordre, sans toucher aux conditions $\varepsilon > 0$ et $\delta > 0$ , puis on nie l'implication finale. La négation de « $A \Rightarrow B$ » est « $A$ et $\text{non } B$ ». On obtient : $\exists \varepsilon > 0, \ \forall \delta > 0, \ \exists x \in \R, \ \abs{x - a} \leqslant \delta \ \text{ et } \ \abs{f(x) - f(a)} > \varepsilon.$ En français : il existe un $\varepsilon > 0$ tel que, aussi petit que soit $\delta > 0$ , on trouve un réel $x$ à distance au plus $\delta$ de $a$ dont l'image est à distance strictement plus grande que $\varepsilon$ de $f(a)$ .

Exercice 2. Ordre des quantificateurs

Dire si chacune des deux propositions est vraie ou fausse, en justifiant.

$\forall n \in \N, \ \exists m \in \N, \ m \geqslant n^2$ .
$\exists m \in \N, \ \forall n \in \N, \ m \geqslant n^2$ .

Voir le corrigé

Vraie. Soit $n \in \N$ . Posons $m = n^2$ , qui est un entier naturel. Alors $m \geqslant n^2$ . L'entier $m$ dépend de $n$ , ce qui est permis.
Fausse. Montrons sa négation : $\forall m \in \N, \ \exists n \in \N, \ m < n^2$ . Soit $m \in \N$ . Posons $n = m + 1$ . Alors $n^2 = m^2 + 2m + 1 \geqslant m + 1 > m$ . La négation est vraie, donc la proposition est fausse. Les deux propositions ne diffèrent que par l'ordre des quantificateurs, et elles n'ont pas la même valeur de vérité.

Exercice 3. Contraposée

Soit $n$ un entier. Montrer par contraposée que si $n^2 - 1$ n'est pas divisible par $8$ , alors $n$ est pair.

Voir le corrigé

La contraposée est : si $n$ est impair, alors $8$ divise $n^2 - 1$ . Supposons $n$ impair, et écrivons $n = 2k + 1$ avec $k \in \Z$ . Alors $n^2 - 1 = 4k^2 + 4k = 4k(k + 1).$ D'après la proposition démontrée par disjonction de cas, $k(k + 1)$ est pair : il existe $j \in \Z$ tel que $k(k + 1) = 2j$ . Donc $n^2 - 1 = 8j$ est divisible par $8$ . La contraposée est démontrée, donc l'implication aussi : si $n^2 - 1$ n'est pas divisible par $8$ , alors $n$ est pair.

Exercice 4. Analyse-synthèse

Déterminer toutes les fonctions $f : \R \to \R$ telles que, pour tous réels $x$ et $y$ , $f(x + y) = f(x) + y$ .

Voir le corrigé

Analyse. Soit $f$ une solution. Pour tout réel $y$ , en prenant $x = 0$ , on obtient $f(y) = f(0) + y$ . En notant $c = f(0)$ , on a donc $f(y) = y + c$ pour tout réel $y$ . Les seules solutions possibles sont les fonctions $x \mapsto x + c$ , avec $c$ réel.

Synthèse. Soient $c \in \R$ et $f : x \mapsto x + c$ . Pour tous réels $x$ et $y$ , $f(x + y) = x + y + c = (x + c) + y = f(x) + y.$ Donc $f$ est solution.

Conclusion. Les solutions sont exactement les fonctions $x \mapsto x + c$ , où $c$ décrit $\R$ .

Exercice 5. Récurrence simple

Montrer que pour tout entier $n \geqslant 4$ , $2^n \geqslant n^2$ .

Voir le corrigé

Pour $n \geqslant 4$ , notons $P(n)$ la proposition « $2^n \geqslant n^2$ ». Raisonnons par récurrence sur $n \geqslant 4$ .

Initialisation : $2^4 = 16$ et $4^2 = 16$ , donc $P(4)$ est vraie.

Hérédité : soit $n \geqslant 4$ un entier fixé tel que $P(n)$ soit vraie. Alors $2^{n+1} = 2 \times 2^n \geqslant 2n^2$ . Il suffit de montrer que $2n^2 \geqslant (n + 1)^2$ , c'est-à-dire $n^2 - 2n - 1 \geqslant 0$ . Or $n^2 - 2n - 1 = (n - 1)^2 - 2 \geqslant 3^2 - 2 = 7 > 0$ puisque $n - 1 \geqslant 3$ . Donc $2^{n+1} \geqslant (n + 1)^2$ , et $P(n + 1)$ est vraie.

Conclusion : par récurrence, $2^n \geqslant n^2$ pour tout entier $n \geqslant 4$ . Le rang de départ compte : pour $n = 3$ , $2^3 = 8 < 9 = 3^2$ .

Méthodes et exercices

Les résultats à connaître

Ce chapitre contient peu de théorèmes et beaucoup de règles. Le programme demande de savoir les appliquer sans hésiter, et en particulier de savoir nier n'importe quelle proposition.

Règles de De Morgan : non (P et Q) équivaut à (non P ou non Q), non (P ou Q) équivaut à (non P et non Q). Exigible, se vérifie par table de vérité.
Lecture de l'implication : P ⇒ Q équivaut à (non P ou Q). Exigible, table de vérité.
Négation d'une implication : non (P ⇒ Q) équivaut à (P et non Q). Exigible, conséquence immédiate de la précédente.
Contraposée : P ⇒ Q et (non Q ⇒ non P) ont toujours la même valeur de vérité. Exigible, table de vérité.
Négation des quantificateurs : non (∀x ∈ E, P(x)) équivaut à ∃x ∈ E, non P(x), et non (∃x ∈ E, P(x)) équivaut à ∀x ∈ E, non P(x). Exigible, c'est la règle la plus utilisée de l'année.
Permutation des quantificateurs : deux ∀ ou deux ∃ consécutifs se permutent. Un ∀ et un ∃ ne se permutent pas. En revanche « ∃y, ∀x, P(x, y) » entraîne toujours « ∀x, ∃y, P(x, y) ». Exigible.
Principe de récurrence, simple, double et forte : exigible. Le programme le relie au fait que toute partie non vide de N admet un plus petit élément, propriété admise. Toute construction de N est hors programme.
Résultats d'exemple exigibles avec preuve : si n² est pair alors n est pair (contraposée), √2 est irrationnel (absurde), décomposition unique d'une fonction en somme d'une fonction paire et d'une fonction impaire (analyse-synthèse).

Clés de démonstration

Équivalence entre une implication et sa contraposée. On dresse la table de vérité à quatre lignes. P ⇒ Q est fausse dans le seul cas P vraie, Q fausse. La contraposée non Q ⇒ non P est fausse dans le seul cas non Q vraie, non P fausse, c'est-à-dire Q fausse, P vraie. Ce sont les mêmes lignes. Astuce : ne jamais chercher à « comprendre » ce cas, dresser la table.

Négation d'une phrase quantifiée. On lit la phrase de gauche à droite, on remplace chaque ∀ par ∃ et chaque ∃ par ∀ sans changer l'ordre, puis on nie la proposition finale. Astuce : ne toucher aux quantificateurs qu'à la fin, quand la proposition finale est niée proprement, sinon on oublie une négation.

Principe de récurrence à partir du plus petit élément. Soit A l'ensemble des entiers n ≥ n₀ pour lesquels P(n) est fausse. Si A est non vide, il a un plus petit élément m, qui vaut au moins n₀ + 1 grâce à l'initialisation. Alors P(m − 1) est vraie par minimalité, et l'hérédité donne P(m) vraie, contradiction. Astuce : c'est un raisonnement par l'absurde sur l'ensemble des contre-exemples, dit du plus petit contre-exemple.

n² pair implique n pair. On prouve la contraposée. Si n est impair, n = 2k + 1, alors n² = 2(2k² + 2k) + 1 est impair. Astuce : la négation de « pair » est « impair », ce qui s'écrit avec un entier k, alors que l'hypothèse « n² pair » ne dit rien d'exploitable sur n.

√2 irrationnel. On suppose √2 = p/q avec p et q entiers premiers entre eux. Alors p² = 2q² est pair, donc p est pair, p = 2m, donc q² = 2m² est pair, donc q est pair. Contradiction avec p et q premiers entre eux. Astuce : le choix d'une fraction irréductible dès le départ est ce qui fournit la contradiction.

Décomposition paire-impaire. Analyse : si f = g + h avec g paire et h impaire, on écrit f(x) et f(−x) et on résout le système de deux équations en g(x) et h(x). Synthèse : on vérifie que les deux fonctions trouvées ont la parité voulue et que leur somme vaut f. Astuce : évaluer la relation en x et en −x, c'est le geste de toute analyse-synthèse avec une symétrie.

Exemples et contre-exemples à connaître

« Si 0 = 1 alors 2 = 3 » est une implication vraie. Une implication dont l'hypothèse est fausse est vraie, et cela n'a rien de paradoxal.
« n multiple de 4 ⇒ n pair » est vraie, sa réciproque est fausse (n = 2). Une implication et sa réciproque sont indépendantes.
« ∀x ∈ R, ∃y ∈ R, y > x » est vraie, « ∃y ∈ R, ∀x ∈ R, y > x » est fausse. L'ordre des quantificateurs est un sens.
La propriété « n = n + 1 » est héréditaire et fausse pour tout n. Une récurrence sans initialisation ne prouve rien.
x = 1 implique x² = 1, mais x² = 1 n'implique pas x = 1. Élever au carré ne conserve qu'une implication.
« Pour tout n, n² − n + 41 est premier » est vraie pour n de 0 à 40 et fausse pour n = 41. Quarante et un exemples ne font pas une preuve.
Le « ou » mathématique est inclusif : « x ≥ 0 ou x ≤ 0 » est vraie pour tout réel, y compris x = 0.
La négation de « f est croissante » n'est pas « f est décroissante » mais « il existe x < y tels que f(x) > f(y) ».
Une suite qui ne converge pas vers l n'a pas forcément une limite différente de l, elle peut n'avoir aucune limite. Nier une convergence ne donne pas une convergence.

Techniques du chapitre

Technique 1 : nier une phrase quantifiée. Mini-exercice : nier « f est bornée sur R », c'est-à-dire « ∃M ∈ R, ∀x ∈ R, |f(x)| ≤ M ». Réponse : ∀M ∈ R, ∃x ∈ R, |f(x)| > M. On a échangé les deux quantificateurs dans l'ordre, et remplacé ≤ par >.

Technique 2 : choisir la contraposée quand la conclusion se nie bien. Mini-exercice : soit x réel, montrer que si x² ≤ 1 alors x ≤ 1. Contraposée : si x > 1 alors x² > 1. Preuve : x > 1 > 0 donc x² > x > 1, par produit d'inégalités entre nombres positifs.

Technique 3 : démontrer une équivalence par deux implications. Mini-exercice : pour x réel, montrer que x² = x équivaut à x ∈ {0, 1}. Sens direct : x² − x = x(x − 1) = 0 donc x = 0 ou x = 1. Sens réciproque : 0² = 0 et 1² = 1. Les deux sens sont écrits, on peut conclure.

Technique 4 : disjonction de cas exhaustive. Mini-exercice : montrer que pour tout entier n, n(n + 1)(n + 2) est multiple de 3. Cas n = 3k : c'est n qui est multiple de 3. Cas n = 3k + 1 : n + 2 = 3(k + 1). Cas n = 3k + 2 : n + 1 = 3(k + 1). Les trois cas couvrent tous les entiers.

Technique 5 : analyse-synthèse pour une équation fonctionnelle. Mini-exercice : trouver les réels x tels que √(x + 2) = x. Analyse : si x convient, alors x ≥ 0 et x + 2 = x², donc x² − x − 2 = (x − 2)(x + 1) = 0, donc x = 2 (x = −1 est exclu par x ≥ 0). Synthèse : √4 = 2, donc x = 2 convient. Unique solution : 2.

Technique 6 : rédiger une récurrence avec la propriété nommée. Mini-exercice : montrer que pour tout n ≥ 4, 2ⁿ ≥ n². On pose P(n) : « 2ⁿ ≥ n² ». Initialisation : 16 ≥ 16. Hérédité : soit n ≥ 4 avec P(n). Alors 2ⁿ⁺¹ = 2·2ⁿ ≥ 2n², et 2n² ≥ (n + 1)² équivaut à n² − 2n − 1 ≥ 0, vrai dès n ≥ 3. Donc P(n + 1). Conclusion : P(n) pour tout n ≥ 4.

Technique 7 : prouver une unicité en supposant deux objets. Mini-exercice : montrer qu'une fonction a au plus un point fixe si elle vérifie |f(x) − f(y)| < |x − y| pour tous x ≠ y. Si a et b sont deux points fixes distincts, |a − b| = |f(a) − f(b)| < |a − b|, absurde. Donc a = b.

Exercices classiques corrigés

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

Exercice 1. Négations à écrire sans hésiter

Classiques de khôlle et concours · Khôlle

Écrire la négation des propositions suivantes. (a) La suite (u_n) est majorée. (b) La fonction f est croissante sur R. (c) La suite (u_n) converge vers l. (d) Pour tout ε > 0, il existe δ > 0 tel que pour tous x, y avec |x − y| ≤ δ, |f(x) − f(y)| ≤ ε.

Technique négation des quantificateurs dans l'ordre.

Voir le corrigé

(a) s'écrit ∃M, ∀n, u_n ≤ M. Négation : ∀M, ∃n, u_n > M.
(b) s'écrit ∀x, ∀y, (x ≤ y ⇒ f(x) ≤ f(y)). Négation : ∃x, ∃y, x ≤ y et f(x) > f(y). On a utilisé la négation d'une implication.
(c) : ∃ε > 0, ∀N ∈ N, ∃n ≥ N, |u_n − l| > ε.
(d) : ∃ε > 0, ∀δ > 0, ∃x, ∃y, |x − y| ≤ δ et |f(x) − f(y)| > ε.

piège : Dans (b), écrire « f(x) ≥ f(y) » au lieu de « f(x) > f(y) ». La négation de ≤ est >, stricte.

Exercice 2. Parité et divisibilité par contraposée

Classiques de khôlle et concours · Khôlle

Soit n un entier. Montrer que si n² est divisible par 3, alors n est divisible par 3.

Technique contraposée plus disjonction de cas.

Voir le corrigé

Contraposée : si n n'est pas divisible par 3, alors n² ne l'est pas.
Si n n'est pas multiple de 3, alors n = 3k + 1 ou n = 3k + 2 pour un entier k.
Cas n = 3k + 1 : n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, non multiple de 3.
Cas n = 3k + 2 : n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1, non multiple de 3.
Dans les deux cas n² n'est pas multiple de 3, ce qui prouve la contraposée.

piège : Oublier un des deux cas, ou tenter une preuve directe à partir de « 3 divise n² » sans outil d'arithmétique.

Exercice 3. Irrationalité de √2 + √3

Classiques de khôlle et concours · Khôlle

Montrer que √6 est irrationnel, puis que √2 + √3 est irrationnel.

Technique raisonnement par l'absurde, deux fois.

Voir le corrigé

Supposons √6 = p/q avec p, q entiers naturels non nuls et premiers entre eux. Alors p² = 6q².
p² est pair, donc p est pair (exercice de cours), p = 2m. Alors 4m² = 6q², soit 2m² = 3q².
3q² est pair, donc q² est pair (car 3 est impair et un produit d'impairs est impair), donc q est pair. Contradiction avec p et q premiers entre eux.
Supposons maintenant √2 + √3 = r rationnel. En élevant au carré, 5 + 2√6 = r², donc √6 = (r² − 5)/2 serait rationnel. Contradiction avec l'étape 3.

piège : À l'étape 4, l'élévation au carré est licite car on cherche seulement une conséquence, pas une équivalence. Il faut le dire.

Exercice 4. Équation fonctionnelle par analyse-synthèse

Classiques de khôlle et concours · Khôlle

Déterminer toutes les fonctions f de R dans R telles que, pour tout réel x, f(x) + 2 f(1 − x) = x².

Technique analyse-synthèse, évaluation en x et en 1 − x.

Voir le corrigé

Analyse. Soit f une solution. En remplaçant x par 1 − x, on obtient pour tout x : f(1 − x) + 2 f(x) = (1 − x)².
On a un système linéaire en les deux inconnues f(x) et f(1 − x). En multipliant la seconde relation par 2 et en soustrayant la première : 3 f(x) = 2(1 − x)² − x² = x² − 4x + 2.
Donc f(x) = (x² − 4x + 2)/3 pour tout x. Il y a au plus une solution.
Synthèse. Soit f définie par cette formule. Alors f(1 − x) = ((1 − x)² − 4(1 − x) + 2)/3 = (x² + 2x − 1)/3, et f(x) + 2 f(1 − x) = (x² − 4x + 2 + 2x² + 4x − 2)/3 = x². La fonction convient.
Conclusion : unique solution, f(x) = (x² − 4x + 2)/3.

piège : S'arrêter après l'analyse. Sans la synthèse, on n'a prouvé qu'une condition nécessaire.

Exercice 5. Le sens des quantificateurs

Classiques de khôlle et concours · Khôlle

Soit f une fonction de [0, 1] dans R. On considère les deux propositions A : « ∀x ∈ [0, 1], ∃M ∈ R, |f(x)| ≤ M » et B : « ∃M ∈ R, ∀x ∈ [0, 1], |f(x)| ≤ M ». Montrer que A est toujours vraie, que B entraîne A, et donner une fonction sur ]0, 1] pour laquelle l'analogue de B est fausse.

Technique lecture de la dépendance entre variables.

Voir le corrigé

A : soit x ∈ [0, 1]. Le nombre M = |f(x)| convient. Donc A est vraie, quelle que soit f. Le M dépend de x.
B ⇒ A : si un M convient pour tous les x, alors pour chaque x ce même M convient. C'est le sens toujours valable, ∃∀ entraîne ∀∃.
Sur ]0, 1], prenons f(x) = 1/x. Pour tout M, l'élément x = 1/(|M| + 1) de ]0, 1] vérifie f(x) = |M| + 1 > M. Donc « ∀M, ∃x, f(x) > M » est vraie, ce qui est la négation de B.

piège : Croire que A dit que f est bornée. A ne dit rien du tout, elle est toujours vraie.

Exercice 6. Une identité impossible modulo 4

Classiques de khôlle et concours · Khôlle

Montrer qu'il n'existe pas d'entiers relatifs a et b tels que a² − 4b = 2.

Technique absurde et disjonction de cas sur la parité.

Voir le corrigé

Supposons que de tels entiers existent. Alors a² = 4b + 2 est pair, donc a est pair, a = 2c.
Alors 4c² = 4b + 2, soit 2c² = 2b + 1. Le membre de gauche est pair, celui de droite est impair. Contradiction.

piège : Conclure « a² pair donc a pair » sans avoir démontré ou cité ce résultat. C'est la contraposée de l'exercice de cours.

Exercice 7. Récurrence double et nombre d'or

Classiques de khôlle et concours · Écrit CCINP

On pose u₀ = 1, u₁ = 1 et u_n+2 = u_n+1 + u_n pour tout n. On note a = (1 + √5)/2. Montrer que pour tout n, u_n ≤ aⁿ.

Technique récurrence double, en utilisant a² = a + 1.

Voir le corrigé

Vérification préliminaire : a est racine de x² − x − 1 = 0, donc a² = a + 1. De plus a > 1.
On pose P(n) : « u_n ≤ aⁿ ». Initialisation double : u₀ = 1 ≤ 1 = a⁰, et u₁ = 1 ≤ a puisque a > 1.
Hérédité : soit n tel que P(n) et P(n + 1) soient vraies. Alors u_n+2 = u_n+1 + u_n ≤ aⁿ⁺¹ + aⁿ = aⁿ (a + 1) = aⁿ · a² = aⁿ⁺². Donc P(n + 2).
Conclusion : par récurrence double, u_n ≤ aⁿ pour tout n.

piège : Faire une récurrence simple avec une seule hypothèse, alors que le passage au rang n + 2 utilise deux rangs. Et oublier la seconde initialisation.

Exercice 8. Renforcer l'hypothèse de récurrence

Classiques de khôlle et concours · Écrit CCINP

Montrer que pour tout n ≥ 1, la somme des 1/k² pour k de 1 à n est inférieure ou égale à 2 − 1/n. En déduire qu'elle est inférieure à 2. Expliquer pourquoi la récurrence directe sur « somme ≤ 2 » échoue.

Technique récurrence sur une propriété plus forte que celle visée.

Voir le corrigé

P(n) : « S_n ≤ 2 − 1/n ». Initialisation : S₁ = 1 ≤ 1.
Hérédité : soit n ≥ 1 avec P(n). Alors S_n+1 = S_n + 1/(n + 1)² ≤ 2 − 1/n + 1/(n + 1)².
Il suffit de montrer que 1/(n + 1)² ≤ 1/n − 1/(n + 1) = 1/(n(n + 1)). Cela équivaut à n ≤ n + 1, vrai. Donc S_n+1 ≤ 2 − 1/(n + 1).
Conclusion : P(n) pour tout n ≥ 1, et comme 1/n > 0, S_n < 2.
La récurrence sur « S_n ≤ 2 » échoue : de S_n ≤ 2 on tire S_n+1 ≤ 2 + 1/(n + 1)², ce qui ne redonne pas 2. L'hypothèse plus forte laisse une marge 1/n qui absorbe le nouveau terme.

piège : Écrire la chaîne d'inégalités dans le mauvais sens à l'étape 3, en partant de ce qu'on veut prouver sans utiliser d'équivalences.

Exercice 9. Une existence sans exemple

Approfondissement · Type oral Centrale

Montrer qu'il existe deux réels irrationnels a et b tels que a^b soit rationnel. On admet que √2 est irrationnel et on utilise seulement les règles de calcul sur les puissances.

Technique disjonction de cas non constructive.

Voir le corrigé

On pose c = √2 puissance √2. Ce réel est rationnel ou irrationnel, et on ne cherche pas à savoir lequel.
Cas 1 : c est rationnel. Alors a = b = √2 conviennent.
Cas 2 : c est irrationnel. On pose a = c et b = √2. Alors a^b = √2 puissance (√2 × √2) = √2 puissance 2 = 2, rationnel. Les deux réels a et b sont irrationnels.
Dans chaque cas on a trouvé un couple convenable. L'existence est démontrée.

piège : Se croire obligé de décider quel cas est le bon. La disjonction de cas prouve une existence sans exhiber l'objet, c'est légitime.

Erreurs fréquentes

Enchaîner des ⇔ quand une étape n'est qu'un ⇒ (carré, multiplication par une expression pouvant s'annuler). Le correcteur enlève les points de toute la chaîne.
Nier « ∀x, P(x) » en « ∀x, non P(x) ». La négation d'un « pour tout » est un « il existe ».
Écrire « supposons P(n) vraie pour tout n » dans l'hérédité. On suppose P(n) pour un n fixé, sinon on suppose la conclusion.
Confondre contraposée et réciproque. La contraposée est équivalente à l'implication, la réciproque ne l'est pas.
Utiliser une variable non introduite. Toute lettre doit être précédée d'un « soit », d'un « il existe » ou d'un « pour tout ». Une variable muette ne sort jamais de sa formule.

Logique et raisonnement

L'essentiel

1Propositions et connecteurs

Proposition

Négation

Conjonction et disjonction

Implication

Réciproque et contraposée

Équivalence

2Quantificateurs

Quantificateur universel

Quantificateur existentiel

Négation d'une phrase quantifiée

Ordre des quantificateurs

Règles d'écriture

3Les modes de raisonnement

Raisonnement direct

Raisonnement par contraposée

Raisonnement par l'absurde

Disjonction de cas

Analyse-synthèse

Raisonnement par récurrence

4Rédiger une démonstration

Méthodes

Exercices d'application

Exercice 1. Négation d'une continuité

Exercice 2. Ordre des quantificateurs

Exercice 3. Contraposée

Exercice 4. Analyse-synthèse

Exercice 5. Récurrence simple

Les résultats à connaître

Clés de démonstration

Exemples et contre-exemples à connaître

Techniques du chapitre

Exercices classiques corrigés

Exercice 1. Négations à écrire sans hésiter

Exercice 2. Parité et divisibilité par contraposée

Exercice 3. Irrationalité de √2 + √3

Exercice 4. Équation fonctionnelle par analyse-synthèse

Exercice 5. Le sens des quantificateurs

Exercice 6. Une identité impossible modulo 4

Exercice 7. Récurrence double et nombre d'or

Exercice 8. Renforcer l'hypothèse de récurrence

Exercice 9. Une existence sans exemple

Erreurs fréquentes