« Approfondissements de lycée/Démonstrations » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Début de la traduction de l'article anglais
 
Ligne 6 : Ligne 6 :
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 [[w:Théorème d'incomplétude|ceci]]). Ce chapitre introduira les techniques de l'induction mathématique, la démontration par l'absurde et l'approche axiomatique des mathématiques.
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 [[w:Théorème d'incomplétude|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==
==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
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
* Tous les corbeaux sont des oiseaux noirs, et
Ligne 14 : Ligne 14 :
* Cette boule de billard bougera si je la frappe avec cette queue.
* Cette boule de billard bougera si je la frappe avec cette queue.


L'induction est l'opposé de la déduction. To induce, we observe how things behave in specific cases and from that we draw conclusions as to how things behave in the general case. For example:
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 :
:<math>1 + 2 + 3 + ... + n = \frac{(n + 1)n}{2} </math>
:<math>1 + 2 + 3 + ... + n = \frac{(n + 1)n}{2} </math>
Nous savons que c'est vrai pour tous les nombres, parceque [[w:Gauss|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.
We know it is true for all numbers, because [[w:Gauss|Gauss]] told us. But how do we show that it's true for all positive integers? Even if we can show the identity holds for numbers from one to a trillion or any larger number we can think of, we still haven't proved that it's true for all positive integers. This is where mathematical induction comes in, it works somewhat like the dominoes.


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.
If we can show that the identity holds for some number ''k'', and that mere fact implies that the identity also holds for ''k + 1'', then we have effectively shown that it works for all integers.


'''Example 1'''
'''Exemple 1'''
Montrer que l'identité
Show that the identity
:<math>1 + 2 + 3 + ... + n = \frac{(n + 1)n}{2} </math>
:<math>1 + 2 + 3 + ... + n = \frac{(n + 1)n}{2} </math>
reste valable pour tous les nombres entiers positifs.
holds for all positive integers.


'''Solution'''
'''Solution'''
Firstly, we show that it holds for integers 1, 2 and 3
D'abord, nous montrons qu'elle est valable pour les entiers 1, 2 et 3
:1 = 2&times;1/2
:<math>1 = 2 \times \frac{1}{2}\,</math>
:1 + 2 = 3&times;2/2
:<math>1 + 2 = 3 \times \frac{2}{2}\,</math>
:1 + 2 + 3 = 4&times;3/2 = 6
:<math>1 + 2 + 3 = 4 \times \frac{3}{2} = 6\,</math>
Supposons que l'identité reste valable pour un certain nombre ''k'', alors
Suppose the identity holds for some number ''k'', then
:<math>1 + 2 + 3 + ... + k = \frac{1}{2}(k + 1)k </math>
:<math>1 + 2 + 3 + ... + k = \frac{1}{2}(k + 1)k </math>
is true.
est vrai.


Nous devons montrer que :
We aim to show that:
:<math>1 + 2 + 3 + ... + k + (k + 1) = \frac{1}{2}(k + 2)(k + 1) </math>
:<math>1 + 2 + 3 + ... + k + (k + 1) = \frac{1}{2}(k + 2)(k + 1) </math>
est vrai également.
is also true.
C'est à dire :
We proceed
:<math>
:<math>
\begin{matrix}
\begin{matrix}
Ligne 49 : Ligne 49 :
\end{matrix}
\end{matrix}
</math>
</math>
which is what we have set out to show. Since the identity holds for 3, it also holds for 4 and since it holds for 4 it also holds for 5, and 6 and 7 and so on.
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.


There are two types of mathematical induction: strong and weak. In weak induction, you assume the identity holds for certain value k, and prove it for k+1. In strong induction, the identity must be true for any value lesser or equal to k, and then prove it for k+1.
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.


'''Example 2'''
'''Exemple 2'''
Show that n! > 2<sup>n</sup> for n &ge; 4.
Montrer que n! > 2<sup>n</sup> pour n &ge; 4.


'''Solution'''
'''Solution'''
The claim is true for n = 4. As 4! > 2<sup>4</sup>, i.e. 24 > 16.
L'énoncé est vrai pour n = 4. Comme 4! > 2<sup>4</sup>, i.e. 24 > 16.
Now suppose it's true for n = k, k &ge; 4, i.e.
Maintenant, supposons qu'il est vrai pour n = k, k &ge; 4, i.e.
:k! > 2<sup>k</sup>
:k! > 2<sup>k</sup>
il en découle que
it follows that
:(k+1)k! > (k+1)2<sup>k</sup> > 2<sup>k+1</sup>
:(k+1)k! > (k+1)2<sup>k</sup> > 2<sup>k+1</sup>
:(k+1)! > 2<sup>k+1</sup>
:(k+1)! > 2<sup>k+1</sup>
We have shown that if for n = k then it's also true for n = k + 1. Since it's true for n = 4, it's true for n = 5, 6, 7, 8 and so on for all n.
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.


'''Example 3'''
'''Exemple 3'''
Montrer que
Show that
:<math>1^3 + 2^3 + ...+ n^3 = \frac {(n+1)^2n^2}{4} </math>
:<math>1^3 + 2^3 + ...+ n^3 = \frac {(n+1)^2n^2}{4} </math>


'''Solution'''
'''Solution'''
Suppose it's true for n = k, i.e.
Supposons que cela est vrai pour n = k, i.e.
:<math>1^3 + 2^3 + ...+ k^3 = \frac {(k+1)^2k^2}{4} </math>
:<math>1^3 + 2^3 + ...+ k^3 = \frac {(k+1)^2k^2}{4} </math>
il en découle que
it follows that
:<math>
:<math>
\begin{matrix}
\begin{matrix}
Ligne 81 : Ligne 81 :
\end{matrix}
\end{matrix}
</math>
</math>
We have shown that if it's true for n = k then it's also true for n = k + 1. Now it's true for n = 1 (clear). Therefore it's true for all integers.
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.


=== Exercises ===
=== Exercices ===
1. Prove that <math>1^2 + 2^2 + ... + n^2 = \frac{ n(2n^2 + 3n +1)}{6} </math>
1. Démontrer que <math>1^2 + 2^2 + ... + n^2 = \frac{ n(2n^2 + 3n +1)}{6} </math>


2. Prove that for n &ge; 1,
2. Démontrer pour n &ge; 1,
:<math> (1 + \sqrt{5})^n = x_n + y_n\sqrt{5}</math>
:<math> (1 + \sqrt{5})^n = x_n + y_n\sqrt{5}</math>
where x<sub>n</sub> and y<sub>n</sub> are integers.
x<sub>n</sub> et y<sub>n</sub> sont des entiers.


3. Note that
3. Noter que
:<math>\sum_{i=1}^n[i^k - (i-1)^k] = n^k</math>
:<math>\sum_{i=1}^n[i^k - (i-1)^k] = n^k</math>
Démontrer qu'il existe une formule explicite pour
Prove that there exists an explicit formula for
:<math>\sum_{i=1}^ni^m</math> for all integer ''m''. E.g.
:<math>\sum_{i=1}^ni^m</math> pour tous les entiers ''m''. C.a.d.
<math>1^3 + 2^3 + ... + n^3 = \frac{n^2(n+1)^2}{4}</math>
<math>1^3 + 2^3 + ... + n^3 = \frac{n^2(n+1)^2}{4}</math>


4. The sum of all the angles of a triangle is <math>180^\circ</math>; the sum of all the angles of a rectangle is <math>360^\circ</math>. Prove that the sum of all the angles of a polygon with ''n'' sides, is <math>(n - 2)\cdot 180^\circ</math>.
4. La somme de tous les angles d'un triangle est <math>180^\circ</math>; La somme de tous les angles d'un rectangle est <math>360^\circ</math>. Démontrer que la somme de tous les angles d'un polygone à ''n'' cotés, est <math>(n - 2)\cdot 180^\circ</math>.


==Proof by contradiction==
==Proof by contradiction==

Version du 1 juin 2005 à 18:09

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 :

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é

reste valable pour tous les nombres entiers positifs.

Solution D'abord, nous montrons qu'elle est valable pour les entiers 1, 2 et 3

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

est vrai.

Nous devons montrer que :

est vrai également. C'est à dire :

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! > 2n pour n ≥ 4.

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

k! > 2k

il en découle que

(k+1)k! > (k+1)2k > 2k+1
(k+1)! > 2k+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

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

il en découle que

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

2. Démontrer pour n ≥ 1,

où xn et yn sont des entiers.

3. Noter que

Démontrer qu'il existe une formule explicite pour

pour tous les entiers m. C.a.d.

4. La somme de tous les angles d'un triangle est ; La somme de tous les angles d'un rectangle est . Démontrer que la somme de tous les angles d'un polygone à n cotés, est .

Proof by contradiction

"When you have eliminated the impossible, what ever remains, however improbable must be the truth." Sir Arthur Conan Doyle

The idea of a proof by contradiction is to:

  1. First, we assume that the opposite of what we wish to prove is true.
  2. Then, we show that the logical consequences of the assumption include a contradiction.
  3. Finally, we conclude that the assumption must have been false.

Irrationality of √2

As an example, we shall prove the irrationality of , i.e. is not a rational number. Recall that a rational number is a number which can be expressed in the form of p/q, where p and q are integers and q does not equal 0 (see the 'categorizing numbers' section here).

First, assume that is rational:


where a and b are coprimes (i.e. both integers with no common factors). If a and b are not coprimes, we remove all common factors. In other words, a/b is in simplest form. Now, continuing:

We have now found that a2 is some integer multiplied by two. Therefore, a2 must be divisible by two. If a2 is even, then so a must also be even, for an odd number squared yields an odd number. Now that we know that a is even, we write that a = 2c, where c is another integer.

We have discovered that b2 is also an integer multiplied by two. Following the aforementioned reasoning, b must be an even integer. Here, we have a contradiction. Both a and b are even integers. In other words, both have the common factor of 2. But we already said that a/b is in simplest form. Since such a contradiction has been established, we must conclude that our original assumption was false. Therefore, √2 is irrational.

Infinitude of primes

We have already presented a proof of the inifinitude of prime in the Primes and Modular Arithmetic chapter. Here is another one.

Suppose there are a finite number of primes, and we denote that number by n. We multiply the n primes together and add 1, and called the resulting number x. Now clearly, x is also a prime, so there are n + 1 primes! This is a contradiction, hence there must be infinitely many primes.

There are many ways to prove the same theorem.

Exercises

1.Prove that there is no perfect square number for 11,111,1111,11111......

2. Prove that there are infinitely number of k's such that, 4k + 3, is prime. (Hint: consider N = p1p2...pm + 3)

Axioms and Inference

We have, for too long, taken for granted the fact that zero times any number gives you zero. Nobody ever bothered to prove it. You never wondered why a negative number multiplied by a negative number gives you a positive number? In this section we introduce the idea of axiomatic mathematics (mathematics with simple assumptions) and the conclusions (inferences) we can draw from the axioms.

An axiom is a statement about a number system that we assume to be true. Let's consider the Real numbers, it has axioms Let a, b and c be real numbers

For a, b, and c taken from the real numbers
A1: a+b is in F also (closure)
A2: There exist 0, such that 0 + a = a for all a (existence of zero - an identity)
A3: For every a, there exist b (written -a), such that a + b = 0 (existence of an additive inverse)
A4: (a + b) + c = a + (b + c) (associativity of addition)
A5: a + b = b + a (commutativity of addition)
For a, b, and c taken from the real numbers excluding zero
M1: ab (closure)
M2: There exist an element, 1, such that 1a = a for all a (existence of one - an identity)
M3: For every a there exists a b such that ab = 1
M4: (ab)c = a(bc) (associativity of multiplication)
M5: ab = ba (commutativity of multiplication)
D1: a(b + c) = ab + ac (distributivity)

These are the minimums we assume to be true in this system. These are minimum in the sense that everything else that is true about this number system can be derived from those axioms!

Let's consider the following true identity

(x + y)z = xz + yz

which is not included in the axioms, but we can prove it using the axioms. We proceed:

Before we proceed any further, you will have notice that the real numbers are not the only numbers that satifies those axioms! For example the rational numbers also satify all the axioms. This leads to the abstract concept of a field. In simple terms, a field is a number system that satisfies all those axiom. Let's define a field more carefully:

A number system, F, is a field if it supports + and × operations such that:

For a, b, and c taken from F
A1: a+b is in F also (closure)
A2: There exist 0, such that 0 + a = a for all a (existence of zero - an identity)
A3: For every a, there exist b (written -a), such that a + b = 0 (existence of an additive inverse)
A4: (a + b) + c = a + (b + c) (associativity of addition)
A5: a + b = b + a (commutativity of addition)
For a, b, and c taken from F with the zero removed (sometimes written F*)
M1: ab (closure)
M2: There exist an element, 1, such that 1a = a for all a (existence of one - an identity)
M3: For every a there exists a b such that ab = 1 (inverses)
M4: (ab)c = a(bc) (associativity of multiplication)
M5: ab = ba (commutativity of multiplication)
D1: a(b + c) = ab + ac (distributivity)

Now, for M3, we do not let b be zero, since 1/0 has no meaning. However for the M axioms, we have excluded zero anyway.

For interested students, the requirements of closure, identity, having inverses and associativity on an operation and a set are known as a group. If F is a group with addition and F* is a group with multiplication, plus the distributivity requirement, F is a field. The above axioms merely state this fact in full.

Note that the natural numbers are not a field, as M5 is general not satified, i.e. not every natural number has an inverse that is also a natural number.

Please note also that (-a) denotes the inverse of a, it doesn't say that (-a) = (-1)(a), although we can prove that they are equivalent.

Example 1

Prove using only the axioms that 0 = -0, where -0 is the additive inverse of 0.

Solution 1

0 = 0 + (-0) by A3: existence of inverse
0 = (-0) by A2: 0 + a = a

Example 2

Let F be a field and a an element of F. Prove using nothing more than the axioms that 0a = 0 for all a.

Solution

0 = 0a + (-0a) by A3 existence of inverse
0 = (0 + 0)a + (-0a) by Example 1
0 = (0a + 0a) + (-0a) by distributivity and commutativity of multiplication
0 = 0a + (0a + (-0a)) by associativity of addition
0 = 0a + 0 by A3
0 = 0a by A2.

Alternatively

0a = a(x+-x) for some x in F, by A3
= ax+-ax, by D1
= w+-w, where w=ax, by M1
= 0, by 'A3.

Example 3

Prove that (-a) = (-1)a.

Solution 3

(-a) = (-a) + 0
(-a) = (-a) + 0a by Example 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

One wonders why we need to prove such obvious things (obvious since primary school). But the idea is not to prove that they are true, but to practise inferencing, how to logically join up arguments to prove a point. That is a vital skill in mathematics.

Exercises

1. Explain (or prove) why 1 ≠ 0 in any field

2. Prove using only the axioms if u + v = u + w then v = w (subtracting u from both sides is not accepted as a solution)

3. Prove that if xy = 0 then either x = 0 or y = 0

4. In F-, the operation + is defined to be the difference of two numbers and the × operation is defined to be the ratio of two numbers. E.g. 1 + 2 = -1, 5 + 3 = 2 and 9×3 = 3, 5×2; = 2.5. Is F- a field?

5. Explain why Z6 is not a field.

Problem Set

1. Prove

for

2. Prove by induction that

3. Prove by induction

where

and if . (logical and).

4. Prove by induction

5. Prove that if x and y are integers and n an odd integer then is an integer.

Many questions in other chapters require you to prove things. Be sure to try the techniques discussed in this chapter.