MathQuest — Maths pour l'ingénieur

💡

Pourquoi apprendre ça ?

Démontrer un théorème, c'est construire une chaîne de raisonnement irréfutable à partir d'hypothèses. Il existe plusieurs stratégies : attaquer de face (preuve directe), prouver l'opposé (contraposée), supposer l'absurde pour trouver une contradiction, ou généraliser par récurrence. Choisir la bonne stratégie est un art qui s'apprend.

🎯

Analogie

Imagine que tu veux prouver qu'une porte est verrouillée. Preuve directe : essayer la poignée. Contraposée : si la porte s'ouvre, elle n'est pas verrouillée — donc si elle ne s'ouvre pas... Preuve par l'absurde : supposer qu'elle est ouverte, mais alors quelqu'un serait entré, or la pièce est intacte — contradiction. Chaque méthode atteint la même conclusion par une voie différente.

📐

Théorie

La preuve directe est la méthode la plus naturelle. Pour démontrer $P \Rightarrow Q$ :

Supposer que $P$ est vraie (hypothèse)
Raisonner logiquement à partir de $P$ , étape par étape
Conclure que $Q$ est vraie

C'est la méthode à essayer en premier. Elle fonctionne quand la chaîne de $P$ vers $Q$ est directe et sans détour.

📝

La somme de deux entiers pairs est paire

Énoncé : Si $a$ et $b$ sont pairs, alors $a + b$ est pair.

Preuve directe :

Supposons $a$ et $b$ pairs.
Par définition, $\exists\, k, l \in \mathbb{Z}$ tels que $a = 2k$ et $b = 2l$ .
Alors $a + b = 2k + 2l = 2(k + l)$ .
Puisque $k + l \in \mathbb{Z}$ , la somme $a + b$ est bien paire. $\square$

📐

Théorie

La preuve par contraposée exploite l'équivalence logique fondamentale :

$P \Rightarrow Q \;\equiv\; \neg Q \Rightarrow \neg P$

Pour prouver $P \Rightarrow Q$ , on prouve à la place $\neg Q \Rightarrow \neg P$ :

Supposer que $Q$ est fausse ( $\neg Q$ )
En déduire que $P$ est fausse ( $\neg P$ )

Utile quand : il est plus facile de raisonner depuis la négation de la conclusion que depuis la prémisse.

📝

Si n² est pair alors n est pair

Énoncé : Pour tout $n \in \mathbb{Z}$ , si $n^2$ est pair, alors $n$ est pair.

Contraposée : "Si $n$ est impair, alors $n^2$ est impair."

Preuve de la contraposée :

Supposons $n$ impair : $\exists\, k \in \mathbb{Z},\ n = 2k + 1$ .
Alors $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ .
Puisque $2k^2 + 2k \in \mathbb{Z}$ , $n^2$ est impair.

La contraposée est prouvée, donc l'énoncé original est prouvé. $\square$

🧩

Checkpoint

Pour prouver 'Si P alors Q' par contraposée, on démontre :

📐

Théorie

La preuve par l'absurde (par contradiction) suppose que la conclusion est fausse et montre que cela mène à une impossibilité :

Pour prouver $Q$ :

Supposer $\neg Q$
Raisonner à partir de $\neg Q$ et des hypothèses connues
Aboutir à une contradiction ( $A$ et $\neg A$ simultanément vrais)
Conclure que $\neg Q$ est impossible, donc $Q$ est vraie

Idéale pour : les résultats d'impossibilité, d'irrationalité, d'infinité.

📝

√2 est irrationnel

Supposons par l'absurde que $\sqrt{2}$ est rationnel.

Il existe $p, q \in \mathbb{Z}$ , $q \neq 0$ , $\gcd(p,q)=1$ , tels que $\sqrt{2} = p/q$ .

$2 = p^2/q^2 \Rightarrow p^2 = 2q^2$ , donc $p^2$ est pair.
Donc $p$ est pair (lemme prouvé par contraposée) : $p = 2k$ .
Alors $4k^2 = 2q^2 \Rightarrow q^2 = 2k^2$ , donc $q^2$ est pair, donc $q$ est pair.
Mais $p$ et $q$ pairs $\Rightarrow \gcd(p,q) \geq 2$ . Contradiction !

Donc $\sqrt{2}$ est irrationnel. $\square$

📐

Théorie

La démonstration par récurrence prouve que $P(n)$ est vraie pour tout $n \geq n_0$ :

Étape 1 — Initialisation : Vérifier $P(n_0)$ (cas de base).

Étape 2 — Hérédité : Supposer $P(k)$ vraie pour un $k \geq n_0$ arbitraire fixé (hypothèse de récurrence, HR), puis prouver $P(k+1)$ .

Conclusion : Par le principe de récurrence, $P(n)$ est vraie pour tout $n \geq n_0$ .

Récurrence forte : supposer que $P(n_0), \ldots, P(k)$ sont toutes vraies pour prouver $P(k+1)$ .

📝

Somme des n premiers entiers

Énoncé : $\forall n \geq 1,\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$

Init. ( $n=1$ ) : $\sum_{k=1}^{1} k = 1 = \frac{1\cdot 2}{2}$ . ✓

Hérédité : Supposons $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ (HR). Alors :

$\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = (n+1)\!\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2}$

C'est la formule au rang $n+1$ . ✓ Par récurrence, la formule est vraie pour tout $n \geq 1$ . $\square$

⚠️

Piège : ne pas oublier l'initialisation

Une hérédité sans initialisation ne prouve rien. Exemple célèbre : la "preuve" que tous les chevaux sont de la même couleur. L'hérédité semble fonctionner sauf exactement au passage de $n=1$ à $n=2$ où le raisonnement échoue silencieusement. L'initialisation n'est pas une formalité — elle est indispensable à la validité de toute preuve par récurrence.

📐

Théorie

Récapitulatif des méthodes :

| Méthode | Structure | Idéale pour | |---------|-----------|-------------| | Directe | Supposer $P$ , déduire $Q$ | Raisonnement naturel | | Contraposée | Supposer $\neg Q$ , déduire $\neg P$ | Quand $\neg Q$ est plus maniable | | Absurde | Supposer $\neg Q$ , trouver contradiction | Impossibilité, irrationalité | | Récurrence | Base + hérédité | Propriétés sur $\mathbb{N}$ | | Contre-exemple | Exhiber $x_0$ tel que $\neg P(x_0)$ | Réfuter un $\forall$ |

🧩

Checkpoint

Dans une preuve par récurrence, l'hypothèse de récurrence (HR) consiste à :

📐

Théorie

Double implication : Pour prouver $P \Leftrightarrow Q$ , il faut prouver les deux implications séparément :

$P \Rightarrow Q$ (sens direct)
$Q \Rightarrow P$ (sens réciproque)

On peut utiliser des méthodes différentes pour chaque sens (directe pour l'un, contraposée pour l'autre, etc.).

Preuves par cas : Quand une hypothèse se divise en sous-cas exhaustifs, on traite chaque cas séparément. Si la situation implique " $A_1$ ou $A_2$ ou $\ldots$ ou $A_k$ " (disjonction exhaustive), on prouve la conclusion dans chacun des $k$ cas.

Contre-exemple : Pour réfuter " $\forall x,\ P(x)$ ", un seul $x_0$ tel que $\neg P(x_0)$ suffit. Il ne faut pas confondre "vérifier sur quelques cas" (non concluant) et "exhiber un contre-exemple" (réfutation définitive).

📝

Double implication — parité de n²

Énoncé : $n^2$ est pair $\Leftrightarrow$ $n$ est pair.

Sens $(\Rightarrow)$ : prouvé par contraposée. Si $n$ est impair ( $n = 2k+1$ ), alors $n^2 = 4k^2+4k+1$ est impair. Donc si $n^2$ est pair, $n$ est pair.

Sens $(\Leftarrow)$ : preuve directe. Si $n = 2k$ , alors $n^2 = 4k^2 = 2(2k^2)$ , qui est pair. $\square$

Les deux sens étant établis : $n^2$ pair $\Leftrightarrow$ $n$ pair.

📝

Preuve par cas — valeur absolue

Énoncé : Pour tout réel $x$ , $|x| \geq 0$ .

Cas 1 : $x \geq 0$ . Alors $|x| = x \geq 0$ . ✓

Cas 2 : $x < 0$ . Alors $|x| = -x > 0$ . ✓

Les deux cas couvrent $\mathbb{R}$ entier, donc $|x| \geq 0$ pour tout $x$ . $\square$

📐

Théorie

Récurrence forte : Pour prouver $P(n)$ pour tout $n \geq n_0$ , on peut supposer que toutes les propriétés $P(n_0), \ldots, P(k)$ sont vraies (HR forte) et en déduire $P(k+1)$ .

Récurrence double : Quand une suite est définie par une relation faisant intervenir les deux termes précédents (ex. Fibonacci : $F_{n+1} = F_n + F_{n-1}$ ), on :

Initialise en $n_0$ et $n_0 + 1$ .
Suppose $P(k-1)$ et $P(k)$ vrais pour déduire $P(k+1)$ .

Règle générale : Le nombre de cas de base nécessaires est égal au nombre de rangs précédents impliqués dans la relation de récurrence.

📝

Suite de Fibonacci — récurrence double

Fibonacci : $F_0 = 0,\ F_1 = 1,\ F_{n+1} = F_n + F_{n-1}$ .

Énoncé : $\forall n \geq 0,\ F_n < 2^n$ .

Init. : $F_0 = 0 < 1 = 2^0$ ✓ ; $F_1 = 1 < 2 = 2^1$ ✓.

Hérédité : Supposons $F_k < 2^k$ et $F_{k-1} < 2^{k-1}$ . Alors : $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 3 \cdot 2^{k-1} < 4 \cdot 2^{k-1} = 2^{k+1} \quad \square$

🧩

Checkpoint

Pour prouver , quelle structure minimale est requise ?

🧩

Checkpoint

Pour la suite de Fibonacci (), combien de cas de base faut-il vérifier dans une preuve par récurrence ?

⭐

À retenir

Directe : supposer $P$ , déduire $Q$ — méthode à essayer en premier.
Contraposée : prouver $\neg Q \Rightarrow \neg P$ — logiquement équivalent à $P \Rightarrow Q$ .
Absurde : supposer $\neg Q$ , aboutir à une contradiction — idéal pour les impossibilités (ex. $\sqrt{2}$ irrationnel).
Double implication : prouver $P \Rightarrow Q$ ET $Q \Rightarrow P$ séparément.
Récurrence : initialisation + hérédité ; version double si la relation implique plusieurs rangs précédents.
Contre-exemple : un seul suffit à réfuter un énoncé universel $\forall x,\ P(x)$ .

Méthodes de démonstration

Preuve directe

Preuve par contraposée

Preuve par l'absurde

Récurrence

Double implication et preuves par cas

Récurrence double et induction forte