Analyse 1, techniques de démonstration

✐ Récurrence

$\quad$ Cette technique repose sur le fait que toute partie de $\mathbb N$ a un plus petit élément. Soit $R(n)$ une propriété dépendant d'un entier $n$. On suppose que \begin{array}{ll} \quad 1. \text{ la relation $R(0)$ est vraie,}\\ \quad 2. \text{ la relation $R(n)\implies R(n+1)$ est vraie.}\\ \end{array} On en déduit alors que $\bf {R(n)}$ est vraie pour tout n.

En effet si $A$, l'ensemble des entiers $n$ pour lesquels $R(n)$ est fausse, n'est pas vide, il a un plus petit élément qu'on note $p$. Mais alors $p-1$ n'est pas dans $A$ donc $R(n-1)$ est vraie et par suite $R(p-1+1)=R(p)$ est vraie (à cause de l'hypothèse $(2)$) ce qui contredit le fait que $p\in A$. D'où $A$ est vide.

Exemple :

$\quad$ Soit $R(n)$ la relation “ $2^{n}+1$ est divisible par $3$ ” . Il s'agit de montrer que $R(n)$ est vraie pour tout entier $n$ impair. \begin{array}{ll} \text{Pour $n=1$, on a $2^1+1=3$ donc divisible par $3$. Donc l'hypothèse $(1)$ est vraie,}\\ \text{Supposons que $R(n)$ est vraie avec $n$ impair, c'est-à-dire que l'on peut écrire $2^n+1 = 3k$ avec $k\in \mathbb N$.}\\ \text{Alors $2^n=3k-1.$ L'entier impair suivant de $n$ est $n+2$.}\\ \text{On a $2^{n+2} = 4\times 2^n = 4(3k-1)=12k-4=3(4k-1)-1.$ }\\ \text{D'où $2^{n+2}-1 = 3(4k-1). $ C'est-à-dire $R(n+2)$ est vraie.}\\ \text{Et par récurrence la propriété est démontrée .}\\ \end{array}

✐ Contraposée

$\quad$ C'est. l'équivalence : $$\left( P \implies Q \right) \; \iff \; \left( \text{ non } Q \implies \text{ non } P \right)$$

Exemple :

$\quad$ un entier est premier s'il n'est divisible que par $1$ et lui même.
On veut montrer que si $2^n+1$ est premier alors $n$ est pair.
Ici non $Q$ est “ $n$ est impair ”, on vient de voir qu'alors $2^n+1$ est divisible par $3$ (section précédant), donc n'est pas premier, c'est non $P$, c'est-à-dire $\; P \implies Q\;$ où $P$ est la relation “ $2^n+1$ est premier ”
et $Q$ est la relation “ $n$ est pair ”.

✐ Démonstration par l'absurde

$\quad$ On veut montrer que $R$ est vraie. Pour cela on suppose que $R$ est fausse. D'autre part supposons que l'on déduit à partir de cette hypothèse, c'est-à-dire $\left(\text{ non } R\right)$ vraie, une propriété $S$ et que l'on sait que $S$ est fausse. En termes formels cela veut dire que $$\left(\text{ non } R\right) \implies S \text{ vraie }\;\; \text{et $S$ fausse.}$$ Ainsi la seule ligne de la table de vérités \begin{array}{|c|c|c|c|c|} \hline R & S & R\implies S & \text{ non } R & \text{ non } R \implies S \\ \hline V&V&V&F&V\\ \hline V&F&F&F&V\\ \hline F&V&V&V&V\\ \hline F&F&V&V&F\\ \hline \end{array} $\quad$ ayant ces valeurs de vérités (c-à-d $S$ fausse et $\text{ non } R \implies S$ vraie ) est la deuxième ligne. Donc $R$ est vraie.
$\quad$ En d'autre termes si on arrive à déduire un résultat faux $S$ à partir de la négation de $R$, alors $R$ est vraie.

Exemple :

$\quad$ Montrons que $\sqrt{2}$ est irrationnel, Supposons que $\sqrt{2}$ est rationnel. Il existe alors deux entiers positifs $a, b$ tels que $\sqrt{2}={a\over b}$. Si $a$ et $b$ sont pairs, on peut simplifier la fraction ${a\over b}$ par $2$. En simplifiant par $2$ autant que possible, on arrive au cas où au moins un des deux entiers $a$ ou $b$ est impair. En élevant au carré l’égalité $\sqrt{2}={a\over b}$, on arrive à $$2b^2=a^2.$$ Donc $a^2$ est pair, et par suite $a$ est pair, donc non peut écrire $a=2k$, ce qui donne $2b^2=4k^2$ et en simplifiant par $2$, on obtient $$b^2=2k^2$$ En déduit que $b$ est aussi pair. On a donc une contradiction et $\sqrt{2}$ ne peut pas être rationnel.
Autrement, si on considère les deux relations \begin{array}{ll} R : \sqrt{2} \text{ est irrationnel }\\ S : \sqrt{2}={a\over b}, \; a \text{ ou } b \text{ est impair. }\\ \end{array} D’après ce qu’est précède on a montrer que $\left(\text{ non } R\right) \implies S \text{ vraie }\;\; \text{et $S$ fausse.}$ D’où $R$ est vraie.