# Approfondissements de lycée/Démonstrations

Approfondissements de lycée
          "C'est par la logique que nous démontrons, mais par l'intuition que nous découvrons."

## Introduction

Les mathématiciens ont été, durant des siècles, obsédés par les démonstrations. Ils veulent tout prouver, et par ce processus, ils ont démontré qu'ils ne pouvaient pas tout démontrer (voir ceci). Ce chapitre introduira les techniques de l'induction mathématique, la démonstration par l'absurde et l'approche axiomatique des mathématiques.

## Induction mathématique ou raisonnement par récurrence

Le raisonnement déductif est le processus de recherche de conclusion qu'il est garanti d'obtenir. Par exemple, si nous savons que
* Tous les corbeaux sont des oiseaux noirs, et
* Pour chaque action, il existe une réaction égale et opposée
alors nous pouvons conclure :
* Cet oiseau est un corbeau, par conséquent il est noir.
* Cette boule de billard bougera si je la frappe avec cette queue.
L'induction est l'opposée de la déduction. Lorsque nous raisonnons par induction, nous observons comment les choses se comportent dans des cas particuliers et, à partir de là, nous construisons des conclusions sur leur comportement dans les cas généraux. Par exemple :
    $1+2+3+\dotsb +n={\frac {(n+1)n}{2}}$
Nous savons que c'est vrai pour tous les nombres, parce que Gauss nous l'a dit. Mais comment montrons-nous que c'est vrai pour tous les nombres entiers positifs ? Même si nous pouvons montrer que l'identité reste valable pour les nombres de un à milliard, ou pour tout nombre plus grand que nous pouvons penser, nous n'avons pas encore démontré que cela est vrai pour tous les nombres entiers positifs. C'est ici que l'induction mathématique intervient.
Si nous pouvons montrer que, lorsque l'identité est valable pour un certain nombre k, alors l'identité est aussi valable pour k + 1, alors nous avons effectivement montré qu'elle marche pour tous les nombres entiers.
Exemple 1 Montrer que l'identité
    $1+2+3+\dotsb +n={\frac {(n+1)n}{2}}$
reste valable pour tous les nombres entiers positifs.
Solution D'abord, nous montrons qu'elle est valable pour les entiers 1, 2 et 3:
    $1={\frac {2\times 1}{2}}\,$
    $1+2={\frac {3\times 2}{2}}\,$
    $1+2+3={\frac {4\times 3}{2}}=6\,$
Supposons que l'identité reste valable pour un certain nombre k strictement positif, alors
    $1+2+3+\dotsb +k={\frac {(k+1)k}{2}}$
est vrai.
Nous devons montrer que :
    $1+2+3+...+k+(k+1)={\frac {(k+2)(k+1)}{2}}$
est vrai également.
Or, nous avons supposé :
    ${\begin{matrix}1+2+3+\dotsb +k&&=&{\frac {1}{2}}(k+1)k\\\end{matrix}}$
Donc nous pouvons déduire :
    ${\begin{matrix}1+2+3+\dotsb +k&+(k+1)&=&{\frac {1}{2}}(k+1)k+(k+1)\\\\&&=&(k+1)({\frac {k}{2}}+1)\\\\&&=&{\frac {1}{2}}(k+1)(k+2)\end{matrix}}$
qui est ce que nous devions montrer. Nous savons donc que, si la formule est vraie pour un entier k strictement positif, elle est alors valable pour k + 1. Puisque l'identité reste valable pour 3, on peut maintenant conclure qu'elle est aussi valable pour 4 et, puisqu'elle est valable pour 4, elle reste valable pour 5, 6, 7 et ainsi de suite.
Exemple 2 Montrer que n! > 2$^n$ pour n ≥ 4.
Solution Tout d'abord, montrons que l'énoncé est vrai pour n = 4. Nous avons 4! = 4*3*2 = 24, et 2$^4$ = 16. Comme 24 > 16, nous savons alors que 4! est supérieur à 2$^4$, et donc que l'énoncé est vrai quand n vaut 4.
Maintenant, supposons qu'il est vrai pour une valeur k supérieure ou égale à 4. Nous avons alors
    k! > 2$^k$
Il en découle que
    (k + 1)*k! > (k+1)*2$^k$
Comme k est supérieur à 1, on sait que k + 1 est supérieur à 2, et donc
    (k + 1)*2$^k$ > 2$^{k+1}$
Par transitivité, on a donc :
    (k + 1)*k! > 2$^{k+1}$
D'où, finalement :
    (k + 1)! > 2$^{k+1}$
Nous avons donc montré que, si n = k alors, il est vrai aussi pour n = k + 1. Puisqu'il est vrai pour n = 4, il est alors vrai pour n = 5, 6, 7, 8 et ainsi de suite pour tous les entiers n supérieurs ou égaux à 4.
Exemple 3 Montrer que
    $1^{3}+2^{3}+\dotsb +n^{3}={\frac {(n+1)^{2}n^{2}}{4}}$
Solution On commence par vérifier que la formule est vraie pour n = 1, ce qui est évident.
Supposons maintenant que cela est vrai pour n = k, i.e.
    $1^{3}+2^{3}+\dotsb +k^{3}={\frac {(k+1)^{2}k^{2}}{4}}$
Il en découle que
    ${\begin{matrix}1^{3}+2^{3}+\dotsb +k^{3}+(k+1)^{3}&=&{\frac {(k+1)^{2}k^{2}}{4}}+(k+1)^{3}\\&=&(k+1)^{2}({\frac {k^{2}}{4}}+(k+1))\\&=&{\frac {1}{4}}(k+1)^{2}(k^{2}+4k+4)\\&=&{\frac {1}{4}}(k+1)^{2}(k+2)^{2}\end{matrix}}$
Nous avons montré que s'il est vrai pour n = k alors il est vrai aussi pour n = k + 1. Comme il est vrai pour n = 1, il est vrai pour tous les entiers positifs.
Il existe deux types d'inductions mathématiques : la forte et la faible. En induction faible, vous supposez que l'identité reste valable pour une certaine valeur k, et vous la démontrez pour k+1. En induction forte, l'identité doit être vraie pour toute valeur inférieure ou égale à k, et vous la démontrez pour k+1.

### Exercices

1. Démontrer que $1^{2}+2^{2}+\dotsb +n^{2}={\frac {n(n+1)(2n+1)}{6}}$
2. Démontrer que, pour tout n ≥ 1, on peut exprimer $(1+{\sqrt {5}})^{n}$ sous la forme
    $(1+{\sqrt {5}})^{n}=x_{n}+y_{n}{\sqrt {5}}$
où x$_n$ et y$_n$ sont des entiers.
3. Noter que
    $\sum _{i=1}^{n}[i^{k}-(i-1)^{k}]=n^{k}$
Démontrer qu'il existe une formule explicite pour
    $\sum _{i=1}^{n}i^{m}$ pour tous les entiers m. C.a.d.
$1^{3}+2^{3}+\dotsb +n^{3}={\frac {n^{2}(n+1)^{2}}{4}}$
4. La somme de tous les angles d'un triangle est $180^{\circ }$; La somme de tous les angles d'un rectangle est $360^{\circ }$. Démontrer que la somme de tous les angles d'un polygone à n côtés, est $(n-2)\cdot 180^{\circ }$.

## Démonstration par l'absurde

    "Lorsque vous avez éliminé l'impossible, ce qu'il reste, même improbable doit être vrai." Sir Arthur Conan Doyle
L'idée d'une démonstration par l'absurde est :
* Premièrement, nous supposons que l'opposé de ce que nous souhaitons démontrer est vrai.
* Puis, nous montrons que les conséquences logiques de la supposition amènent à une contradiction.
* Finalement, nous concluons que la supposition devait être fausse.

### Irrationalité de √2

Comme exemple, nous démontrerons l'irrationalité de ${\sqrt {2}}$, i.e. ${\sqrt {2}}$ n'est pas un nombre rationnel. Rappelons-nous qu'un nombre rationnel est un nombre qui peut être exprimé sous la forme ${\frac {p}{q}}$, où p et q sont des nombres entiers et q est différent de 0 (voir la section Catégories de nombres). 1ère méthode :
Tout d'abord, supposons que ${\sqrt {2}}$ est rationnel :
    ${\sqrt {2}}={\frac {a}{b}}$
où a et b sont premiers entre eux (i.e. les deux entiers n'ont pas de facteurs en commun). Si a et b ne sont pas premiers entre eux, nous enlevons tous les facteurs communs. En d'autres mots, la fraction ${\frac {a}{b}}$ est sous la forme irréductible. Maintenant, continuons :
    ${\begin{matrix}{\sqrt {2}}&=&a/b\\2&=&a^{2}/b^{2}\\2b^{2}&=&a^{2}\end{matrix}}$
Nous avons maintenant trouvé que a$^2$ est un certain entier multiplié par 2. Par conséquent, a$^2$ doit être divisible par 2; autrement dit, il est pair. Comme le carré d'un nombre impair est lui-même impair, a doit être pair lui aussi. Nous pouvons maintenant écrire que a = 2c, où c est un autre entier.
    ${\begin{matrix}2b^{2}&=&a^{2}\\2b^{2}&=&(2c)^{2}\\2b^{2}&=&4c^{2}\\b^{2}&=&2c^{2}\end{matrix}}$
Nous avons découvert que b$^2$ est aussi un entier multiplié par 2. En suivant le raisonnement précédent, b doit être un entier pair. Ici, nous avons une contradiction: les deux nombres entiers a et b sont pairs. En d'autres termes, nous venons de démontrer que ces deux nombres ont un facteur commun: 2. Mais nous avons déjà supposé que ces deux nombres n'avaient pas de facteur commun! Puisqu'une telle contradiction a été établie, nous devons conclure que notre supposition d'origine était fausse. Par conséquent, on ne peut trouver deux entiers a et b premiers entre eux tels qu'on puisse écrire ${\sqrt {2}}$ sous la forme ${\frac {a}{b}}$, c'est-à-dire que ${\sqrt {2}}$ est irrationnel. 2ème méthode : voir si dessous

### Infinité de nombres premiers

Nous avons déjà présenté une démonstration de l'infinité des nombres premiers dans le chapitre Nombres premiers. Comme souvent, il existe plusieurs démonstrations de ce théorème, en voici une autre qui repose sur un raisonnement par l'absurde.
Supposons qu'il existe un nombre fini de nombres premiers, et notons ce nombre par N. Nous multiplions ensuite ces N nombres premiers ensemble, nous ajoutons 1 à ce produit, et nous appelons le nombre qui en résulte x.
Pour tout nombre premier p, on peut donc écrire x sous la forme: $x=p\times a+1$ où a est le produit des (N - 1) autres nombres premiers.
De façon claire, x n'est divisible par aucun nombre premier, il est donc lui aussi un nombre premier! On en déduit qu'il existe N + 1 nombres premiers. Ceci est une contradiction, donc notre hypothèse de départ ne peut qu'être fausse, et on a ainsi démontré qu'il existe donc un nombre infini de nombres premiers.

### Exercices

1. Démontrer qu'il n'existe pas de carré parfait pour 11,111,1111,11111......
2. Démontrer qu'il existe une infinité de nombre k' tels que, 4k + 3, est premier. (Astuce : considérer N = p$_1$p$_2$...p$_m$ + 3)

## Axiomes et inférence

Nous avons, il y a longtemps, admis pour vrai le fait que zéro fois n'importe quel nombre nous donne zéro. Personne ne nous l'a démontré. Ne vous êtes vous pas émerveillé pourquoi un nombre négatif multiplié par un nombre négatif vous donne un nombre positif ? Dans cette section, nous introduirons l'idée de mathématiques axiomatiques (mathématiques avec de simples suppositions) et les conclusions (inférences) que nous pouvons tirer à partir des axiomes.
Un axiome est un énoncé à propos d'un ensemble de nombres que nous supposons vrai. Considérons les nombres réels $\mathbb {R} \,$ , il possède les axiomes Soient a, b et c des nombres réels
    Pour a, b, et c réels
    A1: a+b est aussi dans $\mathbb {R} \,$ (clôture)
    A2: Il existe 0, tel que 0 + a = a pour tout a (existence de zéro - une identité)
    A3: Pour chaque a, il existe b (écrit -a), tel que a + b = 0 (existence d'un opposé)
    A4: (a + b) + c = a + (b + c) (associativité de l'addition)
    A5: a + b = b + a (commutativité de l'addition)
    Pour a, b, et c réels en excluant zéro
    M1: ab est aussi dans l'ensemble des réels (zéro exclut) (clôture)
    M2: Il existe un élément, 1, tel que 1a = a pour tout a (existence de un - une identité)
    M3: Pour chaque a il existe a b tel que ab = 1
    M4: (ab)c = a(bc) (associativité de la multiplication)
    M5: ab = ba (commutativité de la multiplication)
    D1: a(b + c) = ab + ac (distributivité de la multiplication par rapport à l'addition)
Ceux-ci sont les axiomes minimums que nous supposons vrai dans ce système. Ils sont minimum dans le sens que chaque chose qui est vraie dans ce système de nombre peut être dérivé à partir de ces axiomes !
Considérons l'identité vraie suivante
    $(x+y)z=xz+yz$
qui n'est pas inclue dans les axiomes, mais que nous pouvons démontrer en les utilisant.
    ${\begin{matrix}(x+y)z&=&z(x+y)\ {\mbox{par M5}}\\&=&zx+zy\ {\mbox{par D1}}\\&=&xz+yz\ {\mbox{par M5}}\\\end{matrix}}$
Avant d'aller plus loin, nous noterons que les nombres réels ne sont pas les seuls nombres qui satisfont ces axiomes ! Par exemple, les nombres rationnels les satisfont aussi. Ceci conduit au concept abstrait de corps. En termes simples, un corps est un ensemble de nombres qui satisfait à tous ces axiomes. Définissons un corps avec plus d'attention :
   Un ensemble de nombres, F, est un corps s'il admet les opérations + et x tel que :
       Pour a, b, et c issus de F
       A1: a+b est aussi dans F (clôture)
       A2: Il existe 0, tel que 0 + a = a pour tout a (existence de zéro - une identité)
       A3: Pour chaque a, il existe b (écrit -a), tel que a + b = 0 (existence d'un opposé)
       A4: (a + b) + c = a + (b + c) (associativité de l'addition)
       A5: a + b = b + a (commutativité de l'addition)
       Pour a, b, et c issus de F sans zéro (quelquefois écrit F$^*$)
       M1: ab (cloture)
       M2: Il existe un élément, 1, tel que 1a = a pour tout a (existence of one - an identity)
       M3: Pour chaque a il existe un b tel que ab = 1 (inverses)
       M4: (ab)c = a(bc) (associativité de la multiplication)
       M5: ab = ba (commutativité de la multiplication)
       D1: a(b + c) = ab + ac (distributivité)
Maintenant, pour M3, b doit être différent de zéro, puisque 1/0 n'a pas de sens. Néanmoins pour les axiomes M, nous avons exclu zéro de toute façon.
Pour les étudiants intéressés, les concepts de clôture, identité, avoir des inverses et associativité d'une opération et un ensemble sont connus comme un groupe. Si F est un groupe muni de l'addition et F$^*$ est un groupe muni de la multiplication, plus le concept de la distributivité, F est un corps. Les axiomes ci-dessus établissent simplement ce fait.
Noter que l'ensemble des nombres naturels n'est pas un corps, comme M3 n'est en général pas satisfait, i.e. chaque nombre naturel n'a pas d'inverse qui est aussi un nombre naturel.
Noter aussi, s'il vous plaît, que (-a) représente l'inverse de a, cela ne signifie pas que (-a) = (-1)(a), bien que nous puissions démontrer qu'ils sont équivalent.
Exemple 1
Démontrer en utilisant seulement les axiomes que 0 = -0, où -0 est l'opposé de 0.
Solution 1
    0 = 0 + (-0) par A3 : existence de l'opposé
    0 = (-0) par A2 : 0 + a = a
Exemple 2
Soit F, un corps et a un élément de F. Démontrer en n'utilisant rien de plus que les axiomes que 0a = 0 pour tout a.
Solution
    0 = 0a + (-0a) par A3 existence de l'opposé
    0 = (0 + 0)a + (-0a) par l'exemple 1
    0 = (0a + 0a) + (-0a) par distributivité et commutativité de la multiplication
    0 = 0a + (0a + (-0a)) par associativité de l'addition
    0 = 0a + 0 par A3
    0 = 0a par A2.
D'une manière différente
    0a = a(x+-x) pour un certain x de F, par A3
       = ax+-ax, par D1
       = w+-w, où w=ax, par M1
       = 0, par 'A3.
Exemple 3
Démontrer que (-a) = (-1)a.
Solution 3
    (-a) = (-a) + 0
    (-a) = (-a) + 0a par l'exemple 2
    (-a) = (-a) + (1 + (-1))a
    (-a) = (-a) + (1a + (-1)a)
    (-a) = (-a) + (a + (-1)a)
    (-a) = ((-a) + a) + (-1)a
    (-a) = 0 + (-1)a
    (-a) = (-1)a
On peut s'étonner pourquoi nous avons besoin de démontrer de telles choses évidentes (évidentes depuis le primaire). Mais l'idée n'est pas de démontrer qu'elles sont vraies, mais de pratiquer l'inférence, comment joindre logiquement des arguments pour démontrer un point. C'est une expérience vitale en mathématiques.

### Exercices

1. Expliquer (ou démontrer) pourquoi 1 ≠ 0 dans tout corps
2. Démontrer en utilisant seulement les axiomes si u + v = u + w alors v = w (soustraire u à partir des deux côtés n'est pas accepté comme solution)
3. Démontrer que si xy = 0 alors soit x = 0 ou y = 0
4. Dans F-, l'opération + est définie comme la différence de deux nombres et l'opération x est définie comme le rapport de deux nombres. C.a.d. 1 + 2 = -1, 5 + 3 = 2 et 9 x 3 = 3, 5 x 2 = 2,5. F- est-il un corps ?
5. Expliquer pourquoi Z$_6$ n'est pas un corps.

## Ensemble de problèmes

"""" Démontrer que ${\sqrt {2}}$ n'appartient pas a Q sans utiliser le raisonnement par l'absurde """
1. Démontrer que
    ${\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+...+{\frac {1}{\sqrt {n}}}\geq {\sqrt {n}}$
pour $n\geq 1$
2. Démontrer par induction que $2n^{3}-3n^{2}+n+31\geq 0$
3. Démontrer par induction
    ${n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}$
où
    ${n \choose m}={\frac {n!}{m!(n-m)!}}$ et $n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 2\cdot 1$ si $n\geq 1\land 0!=1$. ($\land =$ Et logique).
4. Démontrer par induction ${n \choose 0}+2{n \choose 1}+2^{2}{n \choose 2}+...+2^{n}{n \choose n}=3^{n}$
5. Démontrer que si x et y sont des entiers et n un entier impair alors ${\frac {x^{n}+y^{n}}{x+y}}$ est un entier.
Beaucoup de questions dans d'autres chapitres vous demandent de démontrer des choses. Assurez-vous d'essayer les techniques exposées dans ce chapitre.
"""" Démontrer que ${\sqrt {2}}$ n'appartient pas a Q sans utiliser le raisonnement par l'absurde """
solution
rappel : soit p(x) un polynôme de degré n ,si p/q est une racine rationnelle irréductible de p(x) alors p divise an et q divise a0.
on considère le polynôme p(x) = x² - 2 = 0
si le polynôme admet une solution rationnelle p/q alors p divise 1 et q divise 2
donc p = 1 ou -1 et q = 2 ou -2 ou 1 ou ,-1
or ni 1/2 ni -1/2 n'est solution de p(X)
alors p (x) n'admet pas une racine rationnelle irréductible
puisque ${\sqrt {2}}$ est une racine de p(x) alors il n'est pas rationnel