Méthodes de démonstration

pour prouver $P \Rightarrow Q$, on suppose $P$ vraie et on montre par une suite d'implications que $Q$ est vraie.

pour prouver $P \Rightarrow Q$, on démontre l'implication équivalente $\neg Q \Rightarrow \neg P$.

pour prouver une proposition $P$, on suppose $\neg P$ et on aboutit à une contradiction. On conclut que $P$ est vraie.

méthode pour prouver une propriété $P(n)$ pour tout $n \geq n_0$ ($n \in \N$). Elle se fait en deux étapes : initialisation et hérédité.

on découpe l'ensemble des possibilités en plusieurs cas exhaustifs et on prouve la propriété dans chaque cas.

pour réfuter une proposition $\forall x, P(x)$, il suffit d'exhiber un $x_0$ tel que $P(x_0)$ est fausse.

Soit $P(n)$ une propriété dépendant d'un entier $n \geq n_0$. Si :

Si $P(n_0)$ est vraie et si $\big(P(n_0) \land P(n_0+1) \land \dots \land P(n)\big) \Rightarrow P(n+1)$, alors $P(n)$ est vraie pour tout $n \geq n_0$.

pour toute proposition $P$, $P \lor \neg P$ est vraie. C'est la base de la démonstration par l'absurde.

• Énoncer clairement $P(n)$ (la propriété à démontrer).
• Initialisation : vérifier $P(n_0)$ (souvent $n_0 = 0$ ou $1$).
• Hérédité : soit $n \geq n_0$. Supposer $P(n)$ vraie (hypothèse de récurrence) et démontrer $P(n+1)$.
• Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \geq n_0$.

• Énoncer ce qu'on veut prouver : $P$.
• Supposer $\neg P$.
• Dérouler les conséquences jusqu'à une contradiction (par exemple $0 = 1$, ou un élément à la fois dans et hors d'un ensemble).
• Conclure que l'hypothèse $\neg P$ est fausse, donc $P$ est vraie.

• Objectif : prouver $P \Rightarrow Q$.
• Écrire la contraposée $\neg Q \Rightarrow \neg P$.
• Supposer $\neg Q$ et démontrer $\neg P$ directement.
• Conclure que $P \Rightarrow Q$ est vraie.

• Identifier une partition exhaustive (ex : $n$ pair ou impair ; $x > 0$, $x = 0$ ou $x < 0$).
• Prouver la propriété dans chaque cas.
• Conclure.

Montrons que $P(n)$ : $\displaystyle \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ pour tout $n \geq 1$.

pour $n = 1$ : $\sum_{k=1}^{1} k = 1$ et $\frac{1 \cdot 2}{2} = 1$. $P(1)$ est vraie.

supposons $P(n)$ vraie. Alors :

par récurrence, $P(n)$ est vraie pour tout $n \geq 1$.

Montrons que $\sqrt{2}$ est irrationnel. Supposons par l'absurde que $\sqrt{2} = \frac{p}{q}$ avec $p, q \in \N^*$ premiers entre eux. Alors $p^2 = 2q^2$, donc $p^2$ est pair, donc $p$ est pair : $p = 2k$. D'où $4k^2 = 2q^2$, soit $q^2 = 2k^2$, donc $q$ est pair. Mais alors $p$ et $q$ sont tous deux pairs, ce qui contredit l'hypothèse qu'ils soient premiers entre eux. $\sqrt{2}$ est donc irrationnel.

Contraposée : « si $n$ impair, alors $n^2$ impair ». Si $n = 2k+1$, alors $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$ est impair. Donc l'énoncé de départ est vrai.

une récurrence sans initialisation ne démontre rien. Vérifier systématiquement le premier cas.

on suppose $P(n)$ vraie uniquement pour un $n$ quelconque fixé, pas pour tous les $n$. L'objectif est alors de démontrer $P(n+1)$.

la contraposée prouve $P \Rightarrow Q$ en démontrant $\neg Q \Rightarrow \neg P$. L'absurde suppose $\neg P$ pour aboutir à une contradiction.

la récurrence fonctionne sur $\N$ (ou un sous-ensemble de $\N$). On ne peut pas faire une récurrence directement sur $\R$.

un contre-exemple réfute uniquement une proposition universelle. Il ne démontre jamais une proposition positive.

Je connais les 4 méthodes principales : directe, contraposée, absurde, récurrence.

Je sais écrire une démonstration par récurrence avec initialisation, hérédité et conclusion.

Je sais utiliser l'hypothèse de récurrence correctement dans l'étape d'hérédité.

Je sais faire une démonstration par l'absurde (supposer le contraire, chercher contradiction).

Je sais reformuler une implication via sa contraposée quand c'est plus simple.

Je sais qu'un contre-exemple réfute $\forall x, P(x)$ mais ne prouve rien de positif.