01.0 Méthodes de démonstration et raisonnement mathématique

Définition

Un énoncé qui n’a comme réponse que vrai ou faux

Exemple

• Il existe une infinité de nombres premiers
• $\cos (2x)=2\cos x,\forall x\in \mathbb{R}$

Définition

Une démonstration est une suite d’implications logiques ($⟹$) prouvant la proposition à partir d’axiomes ou des propositions connues

Méthode 1: Directe $P⟹\cdots ⟹Q$

Méthode 2: Par contraposée $(P⟹Q)⟺(\neg Q⟹\neg P)$

M

Pour montrer que $P⟹Q$, on sépare l’hypothèse en plusieurs cas, qui couvrent toutes les possibilités.

M

Pour montrer que $P⟺Q$ on a deux options :

• Montrer $P⟹Q$ et $Q⟹P$ (mieux)
• Faire une chaîne d’équivalences $P⟺R_1⟺\cdots ⟺Q$

Méthode : Démonstration par l'absurde

Pour démontrer une proposition $P$, on peut essayer de démontrer que $\neg P$ est vraie et que cela implique une proposition $F$ qui est fausse $\neg P⟹F$

Méthode : Le principe des tiroirs (Pigeonhole Principle)

Pour $n+1$ objets placés dans $n$ tiroirs, alors au moins un tiroir contient $2$ objets

Plus généralement, on a $n$ objets dans $k$ tiroirs, alors on a au moins un tiroir avec $\lceil n/k\rceil$ objets

Méthode : Démonstration par récurrence

Pour prouver que $P(n)$ est vrai, on suppose que c’est vrai et on le prouve par

• Prouvant que $P(n_0)$ est vrai
• Prouvant que $P(n+1),\forall n\ge n_0$ est vrai

Méthode : Recurrence forte

Soit un $n_0\in \mathbb{N}$ et une proposition $P(n)$ une proposition qui dépend de $n\in N:n\ge n_0$

1. On suppose que $P(n_0)$ est vraie
2. $\{P(n_0),P(n_0+1),\dots ,P(n)\}$ impliquent que $P(n+1)$ pour tout $n\ge n_0,n\in \mathbb{N}$

Méthode : Recurrence sur deux variables

On a trois manières de faire des démonstrations à 2 variables:

1. La méthode carrée
2. On a $P(0,0)$ vraie
3. $P(n,0)⟹P(n+1,0)\forall n\ge 0$
4. $\forall m,nP(n,m)⟹P(n,m+1)$
5. La méthode diagonale
6. $P(0,0)$ est vraie
7. $P(n,0)⟹P(n+1,0)\forall n\ge 0$
8. $\forall m,nP(n+1,m)⟹P(n,m+1)$
9. La méthode des deux directions
10. $P(0,0)$ est vraie
11. $\forall m,nP(n,m)⟹P(n,m+1)$ et $P(n,m)⟹P(n+1,m)$