High School Mathematics Extensions/Mathematical Proofs

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

"It is by logic that we prove, but by intuition that we discover."

Introduction

Mathematicians have been, for the past five hundred years or so, obsessed with proofs. They want to prove everything, and in the process proved that they can't prove everything (see this). This chapter will introduce the axiomatic approach to mathematics, and several types of proofs.

Direct proof

The direct proof is relatively simple — by logically applying previous knowledge, we directly prove what is required.

Example 1

Prove that the sum of any two even integers $x$ and $y$ is even.

Solution 1

We know that since $x$ and $y$ are even, they must have 2 as a factor. Then, we can write the following:

Let $x=2a$ , $y=2b$ , for some integers $a,b$

Then:

${\begin{matrix}x+y&=&2a+2b\\&=&2(a+b)\end{matrix}}$

by the distributive property of integers

The number $2(a+b)$ clearly has 2 as a factor, which implies it is even. Therefore, $x+y$ is even.

Example 2

Prove the following statement for non-zero integers $a,b,c$:

If $a$ divides $b$ and $b$ divides $c$ , then $a$ divides $c$ .

Solution 2

If an integer $x$ divides an integer $y$ , then we can write $y=qx$ , for some non-zero integer $q$ . So let's say that $b=qa$ and $c=rb$ , for some non-zero integers $q$ and $r$ . Then:

${\begin{matrix}c&=&rb\\&=&r(qa)\\&=&(rq)a\end{matrix}}$

by the associative property of integer multiplication.

But since $q$ and $r$ are integers, their product $qr$ must also be an integer. Therefore, $c$ is the product of some integer multiplied by $a$ , so we get that $a$ divides $c$ .

Mathematical induction

Deductive reasoning is the process of reaching a conclusion that is guaranteed to follow. For example, if we know

• All ravens are black birds, and
• For every action, there is an equal and opposite reaction

then we can conclude:

• This bird is a raven, therefore it is black.
• This billiard ball will move when struck with a cue.

Induction is the opposite of deduction. 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.

Suppose we want to show that a statement (let us call it $S$ for easier notation) is true for all natural numbers. This is how induction a proof by induction works:

1. First, we show that $S$ is true for the natural number 1. This is usually called the basis or the base case.
2. Then, we show that $S$ is true for natural number $n+1$ whenever it is true for natural number $n$ .
3. By mathematical induction, $S$ is true for all natural numbers.

To understand how the last step works, notice the following

• $S$ is true for 1 (due to step 1)
• $S$ is true for 2 because it is true for 1 (due to step 2)
• $S$ is true for 3 because it is true for 2 (due to previous)
• $S$ is true for 4 because it is true for 3 (due to previous)
• $S$ is true for 5 because it is true for 4 (due to previous)
• and so on...

Example 1 Show that the identity

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

holds for all positive integers.

Solution Firstly, we show that it holds for 1

$1={\frac {(1+1)1}{2}}={\frac {2}{2}}=1$

Suppose the identity holds for some natural number k:

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

This supposition is known as the induction hypothesis. We assume it is true, and 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 of the interior 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.

√2 is irrational

As an example, we shall prove that ${\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 coprime (i.e. integers with no common factors, with greatest common divisor 1). If a and b are not coprime, 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 2. Therefore, a² must be divisible by two. If a² is even, then a must also be even, for an odd number squared yields an odd number. Therefore we can write 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. It follows that b must be even. 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, with no common factors. Since such a contradiction has been established, we must conclude that our original assumption was false. Therefore, √2 is irrational.

Contrapositive

Some propositions that take the form of if xxx then yyy can be hard to prove. It is sometimes useful to consider the contrapositive of the statement. Before I explain what contrapositive is let us see an example

"If x² is odd then x is also odd"

is harder to prove than

"if x is even then x² is also even"

although they mean the same thing. So instead of proving the first proposition directly, we prove the second proposition instead.

If A and B are two propositions, and we aim to prove

If A is true then B is true

we may prove the equivalent statement

If B is false then A is false

instead. This technique is called proof by contrapositive.

To see why those two statements are equivalent, we show the following boolean algebra expressions is true (see Logic)

$p\Rightarrow q\equiv q'\Rightarrow p'\!$

(to be done by the reader).

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)

Reading higher mathematics

This is some basic information to help with reading other higher mathematical literature. ... to be expanded

Quantifiers

Sometimes we need propositions that involve some description of rough quantity, e.g. "For all odd integers x, x² is also odd". The word all is a description of quantity. The word "some" is also used to describe quantity.

Two special symbols are used to describe the quanties "all" and "some"

$\forall$ means "for all" or "for any"

$\exists$ means "there are some" or "there exists"

Example 1
The proposition:

For all even integers x, x² is also even.

can be expressed symbolically as:

$(\forall x)(x{\mbox{ is even}}\Rightarrow x^{2}{\mbox{ is even}})$

Example 2
The proposition:

There are some odd integers x, such that x² is even.

can be expressed symbolically as:

$(\exists x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is even}})$

This proposition is false.

Example 3
Consider the proposition concerning (z = x'y' + xy):

For any value of x, there exist a value for y, such that z = 1.

can be expressed symbolically as:

$(\forall x)(\exists y)(z=1)$

This proposition is true. Note that the order of the quantifiers is important. While the above statement is true, the statement

$(\exists y)(\forall x)(z=1)$

is false. It asserts that there is one value of y which is the same for all x for which z=1. The first statement only asserts that there is a y for each x, but different values of x may have different values of y.

Negation

Negation is just a fancy word for the opposite, e.g. The negation of "All named Britney can sing" is "Some named Britney can't sing". What this says is that to disprove that all people named Britney can sing, we only need to find one named Britney who can't sing. To express symbolically:

Let p represent a person named Britney

$[(\forall p)(p{\mbox{ can sing}})]'=(\exists p)(p{\mbox{ cannot sing}})$

Similarly, to disprove

$(\forall x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is even}})$

we only need to find one odd number that doesn't satisfy the condition. Three is odd, but 3×3 = 9 is also odd, therefore the proposition is FALSE and

$(\exists x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is odd}})$

is TRUE

In summary, to obtain the negation of a proposition involving a quantifier, you replace the quantifier by its opposite (e.g. $\forall$ with $\exists$) and the quantified proposition (e.g. "x is even") by its negation (e.g. "x is odd").

Example 1

$(\forall x)(\exists y)(x(x+1)(x+2)(x+3)+1=y^{2})$

is a true statement. Its negation is

$(\exists x)(\forall y)(x(x+1)(x+2)(x+3)+1\neq y^{2})$

Axioms and Inference

If today's mathematicians were to describe the greatest achievement in mathematics in the 20th century in one word, that word will be abstraction. True to its name, abstraction is a very abstract concept (see Abstraction).

In this chapter we shall discuss the essence of some of the number systems we are familiar with. For example, the real numbers and the rational numbers. We look at the most fundamental properties that, in some sense, define those number systems.

We begin our discussion by looking at some of the more obscure results we were told to be true

• 0 times any number gives you 0
• a negative number multiplied by a negative number gives you a positive number

Most people simply accept that they are true (and they are), but the two results above are simple consequences of what we believe to be true in a number system like the real numbers!

To understand this we introduce the idea of axiomatic mathematics (mathematics with simple assumptions). An axiom is a statement about a number system that we assume to be true. Each number system has a few axioms, from these axioms we can draw conclusions (inferences).

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 a real number 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 is a real number also (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 satisfies those axioms! For example the rational numbers also satisfy 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 is in F (closure)

M2: There exist an element, 1, such that 1a = a for all a (existence of one - the 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 M3 is generally not satisfied, i.e. not every natural number has an inverse that is also a natural number.

Please note also that (-a) denotes the additive 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.

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. Describe a field in which 1 = 0

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₆ (modular arithmetic modular 6) 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$

and 0! = 1 by definition.

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.

6. Prove that (n~m) = n!/((n-m)!m!) is an integer. Where n! = n(n-1)(n-2)...1. E.g. 3! = 3×2×1 = 6, and (5~3) = (5!/3!)/2! = 10.

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

Feedback

What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.