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

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. 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:

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

We know it is true for all numbers, because 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.

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 Show that the identity

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

holds for all positive integers.

Solution Firstly, we show that it holds for integers 1, 2 and 3

1 = 2×1/2

1 + 2 = 3×2/2

1 + 2 + 3 = 4×3/2 = 6

Suppose the identity holds for some number k, then

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

is true.

We aim to show that:

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

is also true. We proceed

${\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}}$

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.

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.

Example 2 Show that n! > 2ⁿ for n ≥ 4.

Solution The claim is true for n = 4. As 4! > 2⁴, i.e. 24 > 16. Now suppose it's true for n = k, k ≥ 4, i.e.

k! > 2^k

it follows that

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

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

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.

Example 3 Show that

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

Solution Suppose it's true for n = k, i.e.

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

it follows that

${\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}}$

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.

Exercises

1. Prove that $1^{2}+2^{2}+...+n^{2}={\frac {n(2n^{2}+3n+1)}{6}}$

2. Prove that for n ≥ 1,

$(1+{\sqrt {5}})^{n}=x_{n}+y_{n}{\sqrt {5}}$

where x_n and y_n are integers.

3. Note that

$\sum _{i=1}^{n}[i^{k}-(i-1)^{k}]=n^{k}$

Prove that there exists an explicit formula for

$\sum _{i=1}^{n}i^{m}$ for all integer m. E.g.

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

4. The sum of all the angles of a triangle is $180^{\circ }$; the sum of all the angles of a rectangle is $360^{\circ }$. Prove that the sum of all the angles of a polygon with n sides, is $(n-2)\cdot 180^{\circ }$.

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 ${\sqrt {2}}$, i.e. ${\sqrt {2}}$ 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 ${\sqrt {2}}$ is rational:

${\sqrt {2}}={\frac {a}{b}}$

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:

${\begin{matrix}{\sqrt {2}}&=&a/b\\2&=&a^{2}/b^{2}\\2b^{2}&=&a^{2}\end{matrix}}$

We have now found that a² is some integer multiplied by two. Therefore, a² must be divisible by two. If a² 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.

${\begin{matrix}2b^{2}&=&a^{2}\\2b^{2}&=&(2c)^{2}\\2b^{2}&=&4c^{2}\\b^{2}&=&2c^{2}\end{matrix}}$

We have discovered that b² 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 = p₁p₂...p_m + 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:

${\begin{matrix}(x+y)z&=&z(x+y)\ {\mbox{by M5}}\\&=&zx+zy\ {\mbox{by D1}}\\&=&xz+yz\ {\mbox{by M5}}\\\end{matrix}}$

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 Z₆ is not a field.

Problem Set

1. Prove

${\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+...+{\frac {1}{\sqrt {n}}}\geq {\sqrt {n}}$

for $n\geq 1$

2. Prove by induction that $2n^{3}-3n^{2}+n+31\geq 0$

3. Prove by induction

${n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}$

where

${n \choose m}={\frac {n!}{m!(n-m)!}}$ and $n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 2\cdot 1$if $n\geq 1\land 0!=1$. ($\land =$logical and).

4. Prove by induction ${n \choose 0}+2{n \choose 1}+2^{2}{n \choose 2}+...+2^{n}{n \choose n}=3^{n}$

5. Prove that if x and y are integers and n an odd integer then ${\frac {x^{n}+y^{n}}{x+y}}$ is an integer.

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