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émontration 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 :

• C'est oiseau est un corbeaux, par conséquent il est noir.
• Cette boule de billard bougera si je la frappe avec cette queue.

L'induction est l'opposé de la déduction. Pour cela, nous observons comment les choses se comportent dans des cas particuliers et à partir de cela nous construisons des conclusions sur leur comportement dans les cas généraux. Par exemple :

$1+2+3+...+n={\frac {(n+1)n}{2}}$

Nous savons que c'est vrai pour tous les nombres, parceque 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 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, cela marche un peu comme les dominos.

Si nous pouvons montrer que l'identité reste valable pour un certain nombre k, et que ce fait implique que l'identité reste encore 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+...+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=2\times {\frac {1}{2}}\,$

$1+2=3\times {\frac {2}{2}}\,$

$1+2+3=4\times {\frac {3}{2}}=6\,$

Supposons que l'identité reste valable pour un certain nombre k, alors

$1+2+3+...+k={\frac {1}{2}}(k+1)k$

est vrai.

Nous devons montrer que :

$1+2+3+...+k+(k+1)={\frac {1}{2}}(k+2)(k+1)$

est vrai également. C'est à dire :

${\begin{matrix}1+2+3+...+k&&=&{\frac {1}{2}}(k+1)k\\\\1+2+3+...+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. Puisque l'identité reste valable pour 3, elle est aussi valable pour 4 et puisqu'elle est valable pour 4, elle reste valable pour 5, et 6 et 7 et ainsi de suite.

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.

Exemple 2 Montrer que n! > 2ⁿ pour n ≥ 4.

Solution L'énoncé est vrai pour n = 4. Comme 4! > 2⁴, i.e. 24 > 16. Maintenant, supposons qu'il est vrai pour n = k, k ≥ 4, i.e.

k! > 2^k

il en découle que

(k+1)k! > (k+1)2^k > 2^k+1

(k+1)! > 2^k+1

Nous avons montré que si n = k alors, il est vrai aussi pour n = k + 1. Puisqu'il est vrai pour n = 4, il est vrai pour n = 5, 6, 7, 8 et ainsi de suite pour tous les n.

Exemple 3 Montrer que

$1^{3}+2^{3}+...+n^{3}={\frac {(n+1)^{2}n^{2}}{4}}$

Solution Supposons que cela est vrai pour n = k, i.e.

$1^{3}+2^{3}+...+k^{3}={\frac {(k+1)^{2}k^{2}}{4}}$

il en découle que

${\begin{matrix}1^{3}+2^{3}+...+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. Maintenant, il est vrai pour n = 1 (évident), par conséquent, il est vrai pour tous les entiers.

Exercices

1. Démontrer que $1^{2}+2^{2}+...+n^{2}={\frac {n(2n^{2}+3n+1)}{6}}$

2. Démontrer pour n ≥ 1,

$(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}+...+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 coté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 :

1. Premièrement, nous supposons que l'opposé de ce que nous souhaitons démontré est vrai.
2. Puis, nous montrons que les conséquences logiques de la supposition amènent à une contradiction.
3. 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 p/q, où p et q sont des nombres entiers et q est différent de 0 (voir la section 'catégories de nombres' ici).

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'on 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, 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² est un certain entier multiplié par 2. Par conséquent, a² doit être divisible par 2. Si a² est pair, alors a doit être aussi pair, pour un nombre impair au carré, un nombre impair. Maintenant que nous savons que a est pair, nous écrivons 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² 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 pair. En d'autres termes, les deux ont un facteur commun 2. Mais nous avons déjà dit que a/b est sous forme irréductible. Puisqu'une telle contradiction a été établie, nous devons conclure que notre supposition d'origine était fausse. Par conséquent, ${\sqrt {2}}$ est irrationel.

Infinité de nombres premiers

Nous avons déjà présenté une démonstration de l'infinité des nombres premiers dans le chapitre Nombres premiers. En voici une autre.

Supposons qu'il existe un nombre fini de nombres premiers, et notons ce nombre par n. Nous multiplions les n nombres premiers ensemble, nous ajoutons 1, et nous appelons le nombre qui en résulte x. Maintenant, de façon claire, x est aussi un nombre premier, donc il existe n + 1 nombres premiers ! Ceci est une contradiction, donc il doit exister une infinité de nombres premiers.

Il existe plusieurs manières de démontrer le même théorème.

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₁p₂...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 F (clotûre)

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 (clotûre)

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 (cloture)

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 cloture, 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 M5 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'inverse

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'inverse

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 coté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₆ n'est pas un corps.

Ensemble de problèmes

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.