Slides

Course Notes
for
MS4111/MS4132
Discrete Mathematics 1
J. Kinsella
February 5, 2002
0-0
MS4111/MS4132 Discrete Mathematics 1 0-1
Contents
1 Preamble 1
1.1 Availability of Notes . . . . . . . . . . . . . . . . . . . . . 1
1.2 Aims/Objectives . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Prime Text . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Syllabus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Tutorials & Assessment . . . . . . . . . . . . . . . . . . . 5
1.6 Warning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.7 In Praise of Lectures . . . . . . . . . . . . . . . . . . . . . 7
2 Elementary Logic 8
2.1 Statement Calculus . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Connectives . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Rules of Statement Calculus . . . . . . . . . . . . . 23
2.1.3 Tautologies and Contradictions . . . . . . . . . . . 30
2.2 Predicate Calculus . . . . . . . . . . . . . . . . . . . . . . 32
2.2.1 Quantiers . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Revision Exercises . . . . . . . . . . . . . . . . . . . . . . 40
3 Proof Techniques 50
3.1 Direct Enumeration . . . . . . . . . . . . . . . . . . . . . 57
3.2 Direct Proof . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3 Contrapositive Proof . . . . . . . . . . . . . . . . . . . . . 62
3.4 Proof by Contradiction . . . . . . . . . . . . . . . . . . . . 63
3.5 Proof by Induction . . . . . . . . . . . . . . . . . . . . . . 66
3.5.1 A Variation on the Principle of Induction . . . . . 78
4 Set Theory 92
4.1 Equality of Sets . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2 Set Operators . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.3 Paradoxes in Naive Set Theory . . . . . . . . . . . . . . . 100
4.3.1 Russells Paradox . . . . . . . . . . . . . . . . . . . 100
4.4 Power Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5 Functions 106
5.1 Domain, Co-domain & Range . . . . . . . . . . . . . . . . 111
5.2 Properties of Functions . . . . . . . . . . . . . . . . . . . 115
5.3 Operations on Functions . . . . . . . . . . . . . . . . . . . 121
6 Recurrence Relations 127
6.1 Sequences and Recurrence Relations . . . . . . . . . . . . 127
6.2 Derivation of a Recurrence Relation . . . . . . . . . . . . 132
6.3 Iteration Technique . . . . . . . . . . . . . . . . . . . . . . 137
6.4 Substitution Technique Introduction . . . . . . . . . . 140
6.5 Substitution Technique Details . . . . . . . . . . . . . . 144
6.5.1 Two Distinct Real Roots . . . . . . . . . . . . . . 145
6.5.2 Equal Real Roots . . . . . . . . . . . . . . . . . . . 145
6.5.3 Complex Roots . . . . . . . . . . . . . . . . . . . . 148
6.6 Substitution Technique Inhomogeneous Case . . . . . . 152
6.6.1 Polynomial Inhomgeneous Term . . . . . . . . . . 157
6.6.2 Trigonometrical Inhomogeneous Term . . . . . . . 159
7 Application: Analysis of Algorithms 164
7.1 Selection Sort Algorithm . . . . . . . . . . . . . . . . . . . 170
7.2 Binary Search algorithm . . . . . . . . . . . . . . . . . . . 174
7.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.4 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 186
A Supplementary Material 206
A.1 In Praise of Lectures . . . . . . . . . . . . . . . . . . . . . 206
A.2 Wiles Proof . . . . . . . . . . . . . . . . . . . . . . . . . . 228
MS4111/MS4132 Discrete Mathematics 1 1
'
&
$
%
1 Preamble
1.1 Availability of Notes
The Notes for this course are freely available via the Web at
http://jkcray.maths.ul.ie/ms4111.html. You may also access
the notes (and other related material) on the local area network
(L.A.N.) via the network share: JKCRAY PUBLIC in the
folder MS4111. You will need to use the Map Network Drive
command available by right-clicking on the My Computer or
ITD Computer icon on the top left of the display. Enter the
network share above, the system will allocate a drive letter. Press
OK and a window will open showing the folders available. Select
the folder MS4111 and double-click on the le Slides.
'
&
$
%
1.2 Aims/Objectives
To introduce students to the language of Discrete Mathematics.
To show its relevance, particularly in Computer Science.
To reinforce development of problem-solving skills.
'
&
$
%
1.3 Prime Text
Discrete Mathematics
R. Johnsonbaugh
Maxwell Macmillan
Available in Bookshop
'
&
$
%
1.4 Syllabus
1. Elementary Logic
2. Proof Techniques
3. Set Theory
4. Functions
5. Recurrence Relations
6. Application: Analysis of Algorithms
'
&
$
%
1.5 Tutorials & Assessment
Two lectures/week.
One tutorial/week - to be assigned.
Problems will be assigned each week on Thursday to be
attempted for the following weeks tutorial.
The module will be assessed via at least one mid-term
assessment together with an end-of-semester assessment.
'
&
$
%
1.6 Warning
It should be pointed out that St. Augustine warned the faithful as
follows:
The Good Christian should beware of Mathematicians
and those who make empty prophecies. The danger
already exists that the Mathematicians have made a
covenant with the devil to darken the spirit and to conne
man in the bonds of Hell.
Caveat emptor.
'
&
$
%
1.7 In Praise of Lectures
See Appendix A.1 for an interesting discussion on the pros & cons
of attending lectures & taking notes.
'
&
$
%
2 Elementary Logic
Denition 2.1 A statement in logic is an English (or any
natural language) sentence which has a denite truth value i.e is
either true or false. The terms statement, proposition & assertion
are all equivalent.
Example 2.1 Here are some English sentences. Some are
statements, some not.
'
&
$
%
Sentence Statement?
Two is a number Yes
x is positive No
Mathematics is interesting Yes
God exists Yes
Please pay attention No
There is life on Mars Yes
Figure 2.1: Example sentences
'
&
$
%
2.1 Statement Calculus
Statements are the fundamental building blocks of The Calculus
of Propositions or Statement Calculus. We consider in this
subsection calculations using/concerning statements.
2.1.1 Connectives
We need to introduce connectives to combine simple statements
into compound statements. Introduce a simple symbolic notation
where capital letters (A,B,C,..) can stand for any statement. First,
we dene the concept of equality for statements:
'
&
$
%
Denition 2.2 (Equality) Two statements are equal if they have
the same truth value irrespective of the truth values of their
component statements, if any.
We use the symbol instead of = to represent equality for
statements to remind ourselves that we are doing Statement
Calculus, not Arithmetic.
'
&
$
%
AND Connective
Denition 2.3 The AND connective is dened by saying A AND
B is TRUE only when both A and B are TRUE: otherwise A AND
B is FALSE.
Notation: Use T to represent the truth value TRUE and use F to
represent the truth value FALSE. Use the symbol to represent
the AND connective. We now introduce the device known as a
truth table which allows unambiguous denitions in statement
calculus. Simply list all 2
n
possible combinations of truth values for
the n component statements.
'
&
$
%
A B A B
T T T
T F F
F T F
F F F
Figure 2.2: Truth Table for AND
The statement A B is our rst example of a compound
statement. This is called the conjunction of A and B.
'
&
$
%
Example 2.2 Life is real and life is earnest.
We parse the sentence into its component statements A Life is
real and B Life is earnest and write it as A B. The compound
statement A B is true when both A & B are true and false
otherwise.
'
&
$
%
OR Connective
Denition 2.4 A OR B (A B) is FALSE only when both A, B
are FALSE and is TRUE otherwise.
A B A B
T T T
T F T
F T T
F F F
Figure 2.3: Truth Table for OR
'
&
$
%
We refer to A OR B as the disjunction of A & B. This is an
Inclusive OR i.e A B is TRUE when either A or B or both
are TRUE. An exclusive OR XOR can also be dened, as in
the following example.
Example 2.3 Either A it will rain this evening or B I will
cut the grass. This does not correspond to A B but to
(A B) (A B)
.
Here the quote mark is the symbol used for the NOT connective,
which we now dene. (NOT A is also often written

A.)
'
&
$
%
NOT Connective
Denition 2.5 The statement NOT A is TRUE when A is
FALSE and vice-versa.
A A
T F
F T
Figure 2.4: Truth Table for NOT
'
&
$
%
IMPLICATION Connective In ordinary English usage, we
understand the statement A implies B to be true if both A & B
are true and false if A is true and B is not. What if A is false? This
case is not usually of interest in ordinary conversation but for
implies to be a connective, A implies B must have a denite
truth value for all values of A & B.
We say that A implies B is vacuously true if A F;
irrespective of the truth value of B. Consider the following
example:
Example 2.4 If every day is Christmas Day then I am Santa
Claus is TRUE!
'
&
$
%
We use the symbol to stand for the implication connective.
We can now dene A B using a truth table.
A B A B
T T T
T F F
F T T
F F T
Figure 2.5: Truth Table for
'
&
$
%
We need to dene the terms necessary and sucient which are
often used in mathematical discussions.
Denition 2.6 Say that A is sucient for B if A B.
Denition 2.7 Say that A is necessary for B if B A.
'
&
$
%
EQUIVALENCE Connective
Denition 2.8 We say that A is equivalent to B if A is
necessary and sucient for B.
We use the symbol to stand for the equivalence connective. It
should be clear that Denition 2.8 corresponds to the following
truth table:
A B A B
T T T
T F F
F T F
F F T
Figure 2.6: Truth Table for
'
&
$
%
Note that A B is T precisely when A and B have the same truth
value. A nal note on equivalence is a connective, is not.
Put simply, connectives can be used to combine statements into
more complex statements; relational operators like allow us
to compare statements.
'
&
$
%
2.1.2 Rules of Statement Calculus
We have dened a set of connectives (operators) analogously to the
denitions of +, , , in arithmetic. Corresponding to the
familiar rules of Arithmetic, we can list the Rules of Statement
Calculus.
'
&
$
%
First recall the Rules of Arithmetic: (a, b, c stand for any real
number)
Commutative Law
_
_
_
a +b = b +a
a b = b a
(2.1)
Associative Law
_
_
_
a + (b +c) = (a +b) +c
a (b c) = (a b) c
(2.2)
Distributive Law
_
a (b +c) = (a b) + (a c) (2.3)
Zero-One Law
_
_
a 0 = 0
a 1 = a
a + 0 = a
(2.4)
'
&
$
%
(There are, of course, other rules in Arithmetic in particular
those involving Division but they are not of interest here.)
'
&
$
%
We now list the corresponding Laws for Statement Calculus
each must be checked by constructing a truth table. (In the
following T & F are used as abbreviations for TRUE & FALSE
respectively.
'
&
$
%
Commutative Law
_
_
_
A B B A
A B B A
(2.5)
Associative Law
_
_
_
A (B C) (A B) C
A (B C) (A B) C
(2.6)
Distributive Law
_
_
_
A (B C) (A B) (A C)
A (B C) (A B) (A C)
(2.7)
'
&
$
%
Identity Law
_
_
_
A T A
A F A
(2.8)
Complement Law
_
_
_
A A
F
A A
T
(2.9)
'
&
$
%
Exercise 2.1 Check the ve Laws using Truth Tables.
The importance of the Laws are that they allow us to do algebra
with statements, i.e. to manipulate so-called Boolean or Logical
expressions like a (b (c a)
) and simplify them where

possible.
'
&
$
%
2.1.3 Tautologies and Contradictions
Denition 2.9 A tautology is a statement which has the truth
value T irrespective of the truth values of its component statements
if any.
Example 2.5
T T (2.10)
A A
T (2.11)
(A B) (B
) T (2.12)
Denition 2.10 A contradiction is a statement which has truth
value F irrespective of the truth values of its component statements
if any.
'
&
$
%
Example 2.6
F F (2.13)
A A
F (2.14)
(A B) (B
F (2.15)
Exercise 2.2 Construct a truth table for the compound statement
(A
B). Can we draw any conclusions?

'
&
$
%
2.2 Predicate Calculus
The following are examples of statements:
1. Everybody likes mathematics.
2. Just because you are paranoid doesnt mean they are not out
to get you.
3. All integers of the form 2 x, where x is an integer are even.
4. All integers of form 2
n
1; where n is a positive integer are
prime.
They have in common the property that they refer to classes (or
sets) of objects. This makes the techniques we have developed so
far (Statement Calculus) inadequate. (Consider example 2 in the
list above.)
'
&
$
%
The key idea is that of a predicate. A predicate is a logical
expression which contains one or more free variables. When
values are assigned to the free variable(s), we obtain a statement.
For example, If x (free variable) is an integer, then 2 x is an
even integer is an example of a predicate. We can use a familiar
notation (function notation) to refer to predicates: for example let
the above predicate be represented as e(x); then e(3) stands for the
statement If 3 is an integer, then 2 3 is an even integer.
'
&
$
%
2.2.1 Quantiers
Denition 2.11 Given a predicate, p(x), the statement For all
x, p(x) is true only if the predicate p(x) becomes a true statement
for any value x = x
0
of the free variable x.
We use the notation x, p(x) to represent For all x, p(x). The
symbol is referred to as the universal quantier.
Example 2.7 x,
_
(x RR R) x
2
0
_
is a TRUE statement.
An alternative and neater notation for the above example is:
Example 2.8 x RR R, x
2
0
'
&
$
%
In general, given a predicate p(x), we can restrict the range of
variation of the free variable by either:
x,
_
(x S) p(x)
_
or we can use a more economical notation:
Denition 2.12
x S, p(x) x,
_
(x S) p(x)
_
'
&
$
%
We now dene our second quantier, :
Denition 2.13 Given a predicate, p(x), the statement There is
an x, such that p(x) is true only if the predicate p(x) becomes a
true statement for at least one value of the free variable x, say x
0
.
We use the notation x[p(x) to represent There is an x, such that
p(x). The symbol is referred to as the existential quantier.
Again, we can restrict the range of possible values for the free
variable by either:
x[
_
(x S) p(x)
_
or, again more economically, by:
Denition 2.14
x S[p(x) x[
_
(x S) p(x)
_
'
&
$
%
Rules for negating quantiers The following rules explain
how the negation of a statement formed with quantiers can be
obtained.
Theorem 2.1 (Negating Quantiers)
_
x, p(x)
_
x[p
(x) (2.16)
_
x[p(x)
_
x, p
(x) (2.17)
Proof: (Eq. 2.16)
If
_
x, p(x)
_
T, then
_
x, p(x)
_
F and so it is not true that
for all x, p(x) T. Therefore there must be at least one choice (say
x
0
) such that p(x
0
) F or equivalently p
(x
0
) T. We conclude
that x[p
(x) is true, as required.

Exercise 2.3 Construct the corresponding argument for Eq. 2.17
'
&
$
%
Comment 2.1 Of course we have not yet said what we mean by a
theorem or proof !
Example 2.9 Consider again the Just because you are paranoid
doesnt mean they are not out to get you example above. Dene
the two predicates x is paranoid = p(x) and They are out to get
x = b(x). Now the English statement translates into
_
x, [p(x) b
(x)]
_
= x[[p(x) b
(x)]
x[[p
(x) b
(x)]
x[[p(x) b(x)]
Translate this back into English!
'
&
$
%
Example 2.10 Start with the (?) true statement: Everybody likes
maths. Let m(x) be the predicate: x likes mathematics. In
symbolic form, we get: x, m(x). To negate this, use the
appropriate rule above, yielding: x[m(x)
. In English; There is
someone who dislikes maths.
Question: How do we negate predicates of form: x S, p(x) or
x S[pXx). Just use the more explicit notation above
(Denitions 2.12 and 2.14) to derive the following results:
Exercise 2.4
_
x S, m(x)
_
_
x S[m(x)
_
_
x S[m(x)
_
_
x S, m(x)
_
'
&
$
%
2.3 Revision Exercises
1. Find the antecedent and consequent in each of the following
statements.
(a) Healthy plant growth follows from sucient water.
(b) Increased availability of microcomputers is a necessary
condition for further technological progress.
(c) Errors will be introduced only if there is a modication of
the program.
(d) Fuel savings imply good insulation or wearing overcoats
indoors.
'
&
$
%
2. Several forms of negation are given for each of the following
statements. Which are correct?
(a) Some people like mathematics.
i. Some people dislike mathematics.
ii. Everybody dislikes mathematics.
iii. Everybody likes mathematics.
(b) The answer is either 2 or 3.
i. Neither 2 nor 3 is the answer.
ii. The answer is not 2 or 3.
iii. The answer is not 2 and it is not 3.
(c) All people are tall and thin.
i. Someone is short and fat.
ii. No one is tall and thin.
iii. Someone is short or fat.
'
&
$
%
3. Let P be the statement Eliminating unemployment is a key
element of public policy, let Q be the statement There will
be an election soon and let R be the statement The
important thing is not to rock the boat. Give simple English
sentences for each of the following statements.
P
(P Q)
(P Q) R
(P (Q R))
(P R)
'
&
$
%
4. Let P be the statement Whales are aquatic mammals. Let Q
be the statement Fish is a healthy food. Let R be the
statement It is wrong to eat animals. Represent each of the
following English sentences symbolically:
(a) If whales are aquatic animals, then it is wrong to eat
animals.
(b) Either sh is a healthy food or it is the case both that
whales are not aquatic animals and that it is not wrong to
eat animals.
(c) It is not the case that if whales are aquatic mammals and it
is wrong to eat animals, then sh is not a healthy food.
5. Given that in Question 3, P is false, Q is true and R is true;
determine the truth value of each of the compound statements
(i) to (vi) given there using either truth tables or the calculus
of propositions.
'
&
$
%
6. Using letters for the component statements, translate the
following compound statements into symbolic notation.
(a) If prices go up, then housing will be plentiful and expensive;
but if housing is not expensive, then it will still be plentiful.
(b) Either going to bed or going swimming is a sucient
condition for changing clothes; however, changing clothes
does not mean going swimming.
(c) Either it will rain or it will snow, but not both.
(d) If Janet wins or if she loses, she will be tired.
(e) Just because you are paranoid doesnt mean they arent out
to get you.
'
&
$
%
7. Construct truth tables for the following statements, where A, B
and C are statements. Note any tautologies or contradictions.
(A B) A
B. (A B) C A (B C).
A (A
A B A
.
(A B)
_
(A C) (B C)
_
(A B) (B A).
8. Suppose that A, B and C are conditions that will be true or
false when a certain computer program is executed. Suppose
further that you want the program to carry out a certain task
only when A or B is true (but not both) and C is false. Using
A, B and C and the connectives AND, OR and NOT, write a
statement which will be true only under these conditions (in
the language of your choice).
9. Prove that
_
B
(A B)
_
A
is a tautology.
'
&
$
%
10. A certain island exists (but where?) whose inhabitants are all
either knights or knaves. Knights always tell the truth, knaves
always lie, (declare to be true what is false and vice versa). An
intrepid logician lands on the island and meets some
inhabitants. The rst (A) says I am a knight. The second
(B) says If I am a knave, then the Prime Minister (P) is a
knight. The third (C) says I am a knight, the Emperor (E) is
a knave, and if the Grand Vizier (V) is a knave, then I am a
knave. What conclusions can the logician draw as to the
aliation (knight or knave) of A, B, C, E, P and V ?.
11. The logician falls asleep and dreams that a native of the island
speaks to him and says I am a knave. Can this dream be
true?
'
&
$
%
12. Let S represent the assertion S is a knight. Let s stand for
any assertion made by speaker S. Show that S s is a
tautology. With this observation, solve the problems given in
question 7 using symbolic notation. (Dicult!)
13. Transcribe each of the following English sentences into logical
notation using quantiers: (Use x to represent cat and p(x)
to represent the predicate x has whiskers).
(a) All cats have whiskers.
(b) There exists a cat without whiskers.
(c) There does not exist a cat without whiskers.
(d) No cat has whiskers.
'
&
$
%
14. Transcribe each of the following English sentences into logical
notation using quantiers: (Use x to represent person, p(x)
to represent the predicate x is truthful, q(x) for x is
forgetful and r(x) for x is successful).
(a) If everyone is truthful, then everyone is successful.
(b) It is true of all people that if they are truthful, then they
are successful.
(c) It is not the case that there is a person who is both forgetful
and truthful.
(d) If there is a person who is both forgetful and truthful, then
that person is successful.
'
&
$
%
15. Negate each of the following statements in symbolic notation.
Simplify the resulting statements using the appropriate rules
from predicate calculus and explain which you are using.
x[y, f(x) > g(y) y, x[x
2
= y
3
xy, [(y > 0) (xy > 0)
_
16. Let p(x) be the predicate x 1 and let q(x) be the predicate
x 3. Let r(x) be the predicate x < 1. Determine which
of the following statements are true and which false if the
universe of discourse is the set of real numbers:
x,
_
(p(x) q(x)
_ _
x, p(x)
_
_
x, q(x)
_
.
_
x[p(x)
_
_
x[r(x)
_
x[
_
p(x) r(x)
_
17. Write the converse and the contrapositive of each statement in
Q.l.
18. All statements contained in this Question are false. Discuss.
'
&
$
%
3 Proof Techniques
We begin with a general discussion. Results in mathematics can
always be expressed in the form P Q where P, Q are statements,
or more generally in the form x, y, ; p(x, y, ) q(x, y, ),
where p, q are predicates and x, y, are the free variables. For
example; the uncontroversial result the product of 2 even integers
is an even integer can be stated as x, y; (x, y E) (xy E).
(This can of course be written in a more usual notation as
x, y E; x y E.) In the following discussions, we will use the
simple compound statement P Q as our prototype theorem
but in practice theorems are usually stated using predicates and
quantiers as they will generally make claims about classes or sets
of objects; for example the natural numbers.
'
&
$
%
Denition 3.1 (Theorem) To assert that the statement P Q
(or more generally x, y, ; p(x, y, ) q(x, y, ) is a theorem
is just to say that it is a tautology i.e. that it has the truth value
T.
Denition 3.2 (Proof ) To prove a theorem is to show that the
truth value is indeed T..
We know from the denition of the implication connective that it
has truth value T unless P T and Q F. So a proof consists in
showing that if P T then so is Q. If the theorem is stated using
predicates and quantiers: x, y, ; p(x, y, ) q(x, y, )
then we need to show that irrespective of the choice of values
x
0
, y
0
, for the free variables x, y, ; that if the statement
p(x
0
, y
0
, ) is true, then so is the statement q(x
0
, y
0
, ).
Denition 3.3 Terminology: We call P (or more generally p the
hypothesis and Q (q) the conclusion.
'
&
$
%
A textbook proof usually is an example of deductive reasoning -
i.e. a logically valid sequence of steps which establish the truth of
Q from the truth of P.
Denition 3.4 Terminology: A conjecture is an implication
P Q which has not been veried/proved. Once proved, a
conjecture is called a theorem.
Example 3.1 Consider the conjecture all odd numbers are
prime. Check 1 is odd, 1 is prime. OK. 3 is odd, 3 is prime. OK.
5 is odd, 5 is prime. OK. 7 is odd, 7 is prime. OK
So the conjecture is true......? and so is a theorem....?
'
&
$
%
The moral is that conjectures about sets of numbers must must be
checked for all possible elements of the set. If the set is innite, this
is clearly not possible. What to do? The solution is to recognise
that the denition 2.11 of the universal quantier requires that the
implication p(x) q(x) be true for any choice x
0
of the free
variable x. So we simple take a xed but arbitrary choice of x,
say x
0
, and try to show that from p(x
0
) we can conclude q(x
0
).
'
&
$
%
Example 3.2 Consider the conjecture: All numbers of the form
2
n
1
(where n is an integer) are prime. Express the conjecture as

an implication: n; n ZZ Z 2
n
1 PP P.
For the conjecture to be a theorem, the implication must be true
for any choice n
0
ZZ Z. So we need to check that irrespective of the
value of n
0
, the implication holds. Now, in fact, the conjecture is
not true, so any attempt to prove it is doomed. Suppose that we
suspect this to be the case we need to nd a
counter-example, in the case of the present example a value for
n
0
for which 2
n0
1 is not prime.
Exercise 3.1 Just try n
0
= 1, 2, 3, until the conjecture fails.
Similarly for Example 3.1, 9 is a counter-example.
If the set of possible values for the free variable(s) happens to be
nite, then we can check case-by-case.
Example 3.3 All odd integers from 17 inclusive are prime.
'
&
$
%
It will often happen that a conjecture can be broken down into a
nite number of special cases; each of which may have innitely
many elements. The advantage of breaking down into special cases
(e.g. n even or n odd) is that very often the implication can be
checked more easily for the special cases.
Example 3.4 (Fermats Last Theorem) The Theorem states:
n 3,
_
x, y, z NN N s.t. x
n
+y
n
= z
n
_
. In other words,
there is no non-trivial integer solution to the equation x
n
+y
n
= z
n
for n > 2. (For n = 2 we have, for example, (3
2
+ 4
2
= 5
2
).) But
in fact, until recently, it was only a conjecture.
'
&
$
%
An interesting discussion on the history of Fermats Theorem and
how it was nally proved may be found in Appendix A.2.
'
&
$
%
3.1 Direct Enumeration
If there are only a nite number of possibilities (cases) check
them all. For example, consider the conjecture: All odd integers
from 1-7 inclusive are prime. Just check the conjecture
n 1, 3, 5, 7, n PP P for each value of n. This approach is only
useful in trivial applications. Non-trivial conjectures are usually
statements about innite sets/classes.
'
&
$
%
3.2 Direct Proof
Given a conjecture : P Q, we assume P true, then based on this
assumption and using any other relevant information available
build a chain of reasoning leading to the conclusion that Q is true.
More generally; given an implication of the form x, p(x) q(x);
we need to show that for an arbitrary but xed choice of x
x
0
say that given p(x
0
) true then based on this assumption and
using any other relevant information available we can build a
chain of reasoning leading to the conclusion that q(x
0
) is true. The
crucial point is that x
0
must be arbitrary, in other words the proof
must not depend on the particular choice of x
0
.
'
&
$
%
We begin with an example conjecture which is clearly true so
that we can concentrate on the logic of the proof method.
Example 3.5 Conjecture that If an integer is divisible by 6, then
it is divisible by 3. Using predicate notation we obtain
x ZZ Z, (6[x) (3[x). Choose an arbitary x
0
ZZ Z. If the result
follows for this x
0
, it must hold for all x. Now regard x
0
as xed.
We can now construct a chain of reasoning starting with the
hypothesis:
Proof:
6[x
0
Hypothesis
x
0
= 6 k, for some k ZZ Z By denition of divides
x
0
= (2 3) k Known fact about 6
x
0
= 3 (2 k) Associativity, Commutativity, Closure for +,
3[x
0
Conclusion 2
'
&
$
%
Example 3.6 Consider the conjecture:
x, y NN N, x < y x
2
< y
2
. Choose x
0
, y
0
arbitary but xed in NN N.
Our chain of reasoning is now:
x
0
< y
0
, x
0
> 0, y
0
> 0 Hypothesis
x
0
x
0
< x
0
y
0
Known property of inequalities
x
2
0
< x
0
y
0
Rewriting
x
0
y
0
< y
0
y
0
x
0
< y
0
x
2
0
< y
2
0
Inequality is transitive Conclusion 2
Comment 3.1 We will often not trouble to explicitly label the
particular arbitrary xed choice of x as (say) x
0
but merely note
that x is now to be regarded as xed. This allows proofs to read
better.
'
&
$
%
Example 3.7 Consider the conjecture:
x, y RR R
+
, x
2
< y
2
x < y. Choose x,y xed and arbitary.
x
2
< y
2
x
y
<
y
x
?...
It is possible to construct a direct proof for this result try it!
However, our next proof technique makes the proof trivial.
'
&
$
%
3.3 Contrapositive Proof
Recall that (A B) (B
) where (B
) is the
contrapositive of (A B). So, to prove P Q just construct a
direct proof for Q
.
Example 3.8 Consider the previous example. Choose x, y
arbitrary and xed as usual. RTP (x
2
< y
2
) (x < y). We simply
take the contrapositive: (x y) (x
2
y
2
). Now construct a
direct proof of the latter implication.
'
&
$
%
3.4 Proof by Contradiction
Given the conjecture (which is to be proved) P Q, we note that
(P Q) (P
Q). So a proof consists in showing that

(P
Q) T. This is equivalent to showing that (P Q
) F.
The technique is thus to assume P T and Q F and try to
deduce a falsehood (e.g. 1 = 0).
Comment 3.2 This approach is particularly useful when neither
P nor Q on their own suce to construct a direct proof.
'
&
$
%
Example 3.9 Conjecture that

2 is irrational. In predicate
notation (rather articially) we can restate this as
x, (x =

2) (x QQ Q)
. (We use the symbol QQ Q to refer to the

rational numbers). A direct proof is certainly not obvious!
We begin our Proof by Contradiction by choosing an arbitrary xed
x such that x =

2 and x is rational. Thus we conclude (as x is
xed) that

2 =
p
q
for some integers p, q ,= 0. We can and do
assume that p, q have no common factors. (This is the key to the
proof ). So 2 = p
2
/q
2
and thus p
2
= 2q
2
. We conclude that p
2
is
even.
Exercise 3.2 Show p
2
even p even.
As p is even, we can write r ZZ Zs.t. p = 2r. Therefore 4r
2
= 2q
2
and q
2
= 2r
2
so q
2
is even and (using the result of Exercise 3.2) so
is q. But we assumed p and q had no common factors. So our
conclusion is a falsehood as required.
'
&
$
%
Comment 3.3 We use the symbol 2 at the end of a line to signify
the end of a proof. Some writers use the letters q.e.d. which
stand for quod erat demonstrandum what was to be proved.
'
&
$
%
3.5 Proof by Induction
We can introduce the idea of induction with the aid of an analogy
(i.e. a comparison with another situation which has similar
features). Consider a ladder being climbed by a person P and
suppose we know that
1. P can reach the rst rung.
2. From any accessible rung, P can reach the next.
Our common sense tells us that we can conclude that P can reach
any rung. The Basis for this conclusion is that the number of rungs
is nite. We are not entitled to arrive at this conclusion if the
ladder is innite.
Comment 3.4 This is unlikely to be a problem in everyday life.
'
&
$
%
Suppose that we are told some predicate p(n) becomes a true
statement for n = 1 (i.e. p(1) T). Suppose that we are also told
that if the predicate is true for any xed integer i, then
p(i + 1) T. It is reasonable to conclude that n NN N, p(n).
However this conclusion is based on the same common-sense
reasoning which led to the conclusion that the ladder can be
climbed. Just as in that case, the reasoning is only valid if the
number of values for the free variable n is nite.
'
&
$
%
Comment 3.5 We can make the ladder analogy exact by letting
p(n) = P can reach the n
th
rung then assumption 1 translates to
p(1) T and assumption 2 translates to: i NN N, p(i) p(i + 1)
To allow us to use this plausible but unsupported line of reasoning
for arbitrary predicates p(n) and for the full set NN N, we add an extra
Axiom or property of the positive integers NN N called the
Principle of Induction.
'
&
$
%
Denition 3.5 (Induction (Weak)) Given a predicate p(n)
(where n is restricted to the positive integers NN N) then if
p(1) T (3.1)
and
i NN N, p(i) p(i + 1) T (3.2)
then
n NN N, p(n) T (3.3)
Comment 3.6 We often shorten p(k) T to p(k).
'
&
$
%
Example 3.10 Conjecture: 1 + 2 + +n =
n(n+1)
2
; n NN N.
Proof:
[Basis step] Check p(1) : 1 =
1(1+1)
2
.
[Inductive step] Assume p(i) : 1 + 2 + +i =
i(i+1)
2
. Use the
following strategy: try to transform/change LHS
i
into LHS
i+1
.
Use the same process on RHS
i
. Then rearrange. Applying the
strategy: 1 + 2 + +i + (i + 1) =
i(i+1)
2
+ (i + 1). Now
rearrange the RHS. We nd that:
1 + 2 + +i + (i + 1) =
(i + 1)(i + 2)
2
as required.
Therefore by the Principle of Induction; n NN N, p(n); i.e.
1 + 2 + +n =
n(n+1)
2
.
'
&
$
%
Comment 3.7 It is often possible to devise an alternative
constructive proof where we derive the result from (for example)
the left hand side. Where this can be done, the resulting proof is
usually clearer than an inductive proof and should be used where
possible.
Comment 3.8 We will usually use sigma notation for sums and
pi notation for products in the following examples as dened in
the following denitions.
Denition 3.6
n
i=1
f
i
f
1
+f
2
+ +f
n
.
Denition 3.7
n
i=1
f
i
f
1
f
2
f
n
.
'
&
$
%
Example 3.11 Conjecture:
n NN N, 1
2
+ 2
2
+ 3
2
+ +n
2
=
n(n+1)(2n+1)
6
.
Proof:
[Basis Step] 1
2
=
1(1+1)(21+1)
2
. The equation is satised so the
Basis Step is complete.
'
&
$
%
[Inductive Step] Assume 1
2
+ 2
2
+ +i
2
=
i(i+1)(2i+1)
6
. RTP
that 1
2
+ 2
2
+ +i
2
+ (i + 1)
2
=
(i+1)(i+2)(2i+3)
6
. We now
change (to reduce the amount of writing) to sigma notation:
the inductive assumption now reads:
i
k=1
k
2
=
i(i + 1)(2i + 1)
6
. (3.4)
Now RTP that

i+1
k=1
k
2
= (i + 1)(i + 2)(2i + 3)/6. Add
term
i+1
= (i + 1)
2
to both sides of Eq. 3.4 to obtain:
i+1
k=1
k
2
= (i + 1)(i + 2)(2i + 3)/6 + (i + 1)
2
. (3.5)
Simplifying the RHS of the latter equation yields the required
result. (Check.)
'
&
$
%
So by the Principle of Induction,
n NN N;

n
k=1
k
2
= n(n + 1)(2n + 1)/6 as required.
'
&
$
%
Denition 3.8 (Factorial) Dene n factorial by
n! = n(n 1).(n 2).....3.2.1. So 3! = 6, 4! = 24 etc. We dene
0! = 1.
'
&
$
%
Example 3.12 Conjecture:

n
i=1
i(i!) = (n + 1)! 1.
Proof:
[B.S] . p(1) : 1.(1!) = 2! 1.
[I.S.] Assume p(k) for some xed but arbitrary k. So we assume
that:
k
i=1
i(i!) = (k + 1)! 1. (3.6)
Now RTP that

k+1
i=1
i(i!) = (k + 2)! 1. Add
t
k+1
= (k + 1)(k + 1)! to both sides of Eq. 3.6. It follows that
k+1
i=1
i(i!) = (k +1)! 1 +(k +1)(k +1)! When we simplify the
RHS, it reduces to the RHS of p(k + 1) as required.
Exercise 3.3 Check.
By the Principle of Induction, we conclude that
n
i=1
i(i!) = (n + 1)! 1.
'
&
$
%
Example 3.13 Conjecture that: Any 2 given positive integers are
equal. Dene p(n): If the maximum of any 2 given integers a, b
is n, a = b. Suppose that we are given that n, p(n). Then, given
any 2 integers a, b, the larger of the two equals some integer n. So
a = b. It follows that our conjecture can be restated as n, p(n).
Proof:
[B.S.] p(1): If the max of any 2 given positive integers a, b is 1,
then a = b. True.
'
&
$
%
[I.S. ] Assume p(k): If the maximum of any 2 given positive
integers a, b is k, then a = b. RTP p(k + 1): If the maximum
of any 2 given positive integers a, b is k + 1, then a = b . So
suppose that the maximum of two given arbitrary positive
integers a, b is k + 1. RTP that a = b. Suppose that b is the
larger (wlog). It follows that b = k + 1. Now consider
a 1, b 1. The larger of these two numbers (b 1) equals k.
So by the inductive hypothesis a 1 = b 1 and trivially a = b.
So by the Principle of Induction, all positive integers are equal.
Something wrong here surely???
Exercise 3.4 Figure out what is wrong!
'
&
$
%
3.5.1 A Variation on the Principle of Induction
Recall the Principle of Induction:
_
p(1)
_
k NN N, p(k) p(k + 1)
_
_
n, p(n). This version is
usually called the Weak Principle of Induction. We can now
dene the Strong Principle of Induction:
Denition 3.9 (Strong Principle of Induction) Given an
arbitrary predicate p, then
_
p(1)[k NN N, (p(1) p(2) ..... p(k)) p(k + 1)]
_
n, p(n).
(3.7)
Comment 3.9 We say that an axiom or theorem is strong if it
allows results to be deduced from it that cannot readily be deduced
from a weaker version.
'
&
$
%
Equivalence of Strong & Weak Induction We do not need to
add the Strong Principle of Induction to our list of axioms for
the positive integers if we can show that it is equivalent to the
simpler weak version. Begin by dening the Well Ordering
Principle. We are not primarily interested in the W.O.P. for itself,
but rather as a means to the end our proving the equivalence of
Strong & Weak Induction.
Denition 3.10 (Well Ordering principle) If X is a
non-empty set of positive integers; then X has a least element
i.e. there is an element in X, (call it x
0
) s.t. x
0
is less than or
equal to all other elements of X. In predicate notation,
X NN N, X ,= ; x
0
Xs.t.x X, x
0
x.
Comment 3.10 This result is obviously true for nite sets.
Exercise 3.5 Check.
'
&
$
%
Just as we were not able to prove that the original (Weak)
Principle of Induction was valid, we have to either state the Well
Ordering Principle (W.O.P.) as an axiom or prove that it is
equivalent to an existing axiom. In fact we will show (using a
so-called Circular Chain of Deduction that the Well Ordering
Principle (W.O.P.) P.S.I. P.W.I.. We begin by proving three
so-called Lemmas (subsidiary theorems).
'
&
$
%
Lemma 3.1 The Weak Principle of Induction (W.P.I.) implies
the Well Ordering Principle (W.O.P.) .
Proof:
RTP that for any arbitrary xed non-empty set X NN N, X has a
least element. We use a trick where we dene p(n): If n X,
then X contains a least element. If n, p(n), then our result
follows. (Check.) We can assume the Weak Principle of Induction
(W.P.I.) so the proof is a standard proof by induction.
[B.S.] p(1): True as X is a set of positive integers and contains 1.
'
&
$
%
[I.S.] Assume p(k): i.e. If k X, then X contains a least
element. In predicate notation, we have for any set X N
that k X x
0
Xs.t.x X; x
0
x. RTP: p(k + 1). So
choose a xed but arbitrary set X N and suppose that
k + 1 X. RTP that X contains a least element. Consider the
new set X
= X k. As X
contains k, X
has a least
element; called x
0
(say). Is x
0
in X or not?
[Case 1] If x
0
X, then it is the least element of X (as it is
the least element of X
which contains X).

[Case 2] Suppose x
0
is not in X. Then we must have x
0
= k.
Conclude (as k + 1 X by assumption) that k + 1 is the
least element of X.
So X contains a least element and therefore we have p(k + 1) .
Thus by the Weak Principle of Induction (W.P.I.) ,
n NN N; p(n).
'
&
$
%
Lemma 3.2 The Well Ordering Principle (W.O.P.) implies the
Strong Principle of Induction (S.P.I.) .
Proof:
RTP that for any predicate p(n), (B.S.) (I.S.) n, p(n). (The
I.S. referred to here is the strong version; see Def. 3.9.)
'
&
$
%
So, let p(n) be an arbitrary xed predicate. Assume the (B.S.) and
the (I.S.) hold. RTP that n, p(n). The only relevant information
at our disposal is that we can assume the Well Ordering Principle
(W.O.P.) . We use a Proof by Contradiction, i.e. we assume
(B.S.) (I.S.)
_
n NN N; p(n)
_
in eect we assume that

at least one n st p(n)
. Let X be the set of positive integers n for

which p(n)
, i.e. X = n NN N[p(n)
. We know that X is not the

empty set (why?) so we can apply the Well Ordering Principle
(W.O.P.) . Therefore x
0
Xs.t.x x
0
, x X. In words, x
0
is
the rst integer for which p(n) is false. So for all
x < x
0
, p(x) T. (Remember we assumed p(1) T the basis
step.) So we have p(1) T, , p(x
0
1) T. But the Inductive
step (I.S.) implies that p(x
0
) T which contradicts our earlier
conclusion that p(x
0
) F. Contradiction. Therefore
n, p(n).
'
&
$
%
Lemma 3.3 The Strong Principle of Induction (S.P.I.) implies
the Weak Principle of Induction (W.P.I.)
Proof:
The result is trivial, precisely because the Strong Principle of
Induction (S.P.I.) is stronger than the Weak Principle of
Induction (W.P.I.) . In other words, the Strong Principle of
Induction (S.P.I.) asserts that (B.S.) (I.S.)
S
n, p(n). But
the Weak Principle of Induction (W.P.I.) asserts that (B.S.)
(I.S.)
W
n, p(n). The key observation is that if (I.S.)
S
T then
certainly (I.S.)
W
T.
Exercise 3.6 Why?
'
&
$
%
We are now in a position to state & prove our Theorem:
Theorem 3.4 The Strong Principle of Induction (S.P.I.) is
equivalent to the Weak Principle of Induction (W.P.I.) .
Proof:
We have established that (Lemma 3.1) Strong Principle of
Induction (S.P.I.) Well Ordering Principle (W.O.P.) , that
(Lemma 3.2) Well Ordering Principle (W.O.P.) Strong
Principle of Induction (S.P.I.) and that (Lemma 3.3) Strong
Principle of Induction (S.P.I.) Weak Principle of Induction
(W.P.I.) . It follows that the three properties of the positive
integers are equivalent and that in particular Weak Principle of
Induction (W.P.I.) Strong Principle of Induction (S.P.I.)
.
'
&
$
%
1. Provide counter-examples to the following statements:
(a) Every geometric gure with four right angles is a square.
(b) If a real number is not positive, then it must be negative.
(c) All people with red hair have green eyes or are tall.
(d) All people with red hair have green eyes and are tall.
2. Give a direct proof that the product of odd integers is odd.
3. Prove by contradiction that the product of odd integers is odd.
4. Prove by contraposition that if a number x is positive then so
is x + 1.
5. Let x and y be positive numbers and prove that x < y if and
only if x
2
< y
2
.
'
&
$
%
6. Prove that for any positive integer n,
2 + 6 + 10 +. . . + (4n 2) = 2n
2
7. Prove that for any positive integer n, the number 2
2n
1 is
divisible by 3.
8. Prove that 2
n
< n! for any positive integer n 4.
9. Prove each of the following identities by mathematical
induction:
n
i=1
i(2
i
) = 2 + (n 1)2
n+1
n
i=1
2(3
i1
) = 3
n
1
n
i=1
(i)(i!) = (n + 1)! 1
'
&
$
%
10. Prove by mathematical induction ( De Moivres Theorem) that
n NN N, (cos +i sin )
n
= cos n +i sin n.
11. Prove by mathematical induction that
(cos )(cos 2)(cos 4)(cos 8) . . . (cos 2
n1
) =
sin 2
n
2
n
sin
.
12. What is wrong with the following proof by mathematical
induction? Show that n NN N, P(n), where
p(n) : n = n + 1.
Assume p(k) for some xed but arbitrary k. Then
k = k + 1.
Adding 1 to both sides yields k + 1 = k + 2 as required!
'
&
$
%
13. What is wrong with the following proof by mathematical
induction? Show that all students in the University are taking
the same degree course. Let p(n) be the statement that any
group of exactly n students in the University are taking the
same degree course. First check p(1); this is trivial as a single
student can only take a single course! Now assume p(k), i.e.
given any group of exactly k students, all are taking the same
course. To prove p(k + 1), we must consider an arbitrary group
of k + 1 students. Exclude one student (e.g. the one with the
highest Q.C.A.) from the group. By the inductive hypothesis,
all the remainder must be studying for the same degree, degree
course X (say). Now remove any other person from the original
group (e.g. the one with the lowest Q.C.A.). Again the
remaining group must all be studying for the same degree and,
as the two groups of k students have k 1 students in common,
all must be studying for degree course X. The result follows.
'
&
$
%
4 Set Theory
This Chapter is largely revision material. Set Theory ideas should
already be familiar it is dicult to progress far in Mathematics
without them & we have used set notation in Chapters 1 & 2.
Denition 4.1 (Set) A set is any well-dened collection of
objects or elements
Denition 4.2 Write x is an element of X as x X. (We have
been using this notation informally up to this point.)
'
&
$
%
We dene a specic set either by listing its elements: eg.
A = 1, 7, 3 or by dening it using a predicate eg.
B = x ZZ Z[(x 5) (x > 3) or in general C = x[p(x). The
range of variation of the free variable x may be restricted (as we
have already seen); using an expression of the form
D = x Y [p(x); e.g. E = x[(x ZZ Z) (x 5) (x > 3) is
the same set as B above.
Denition 4.3 (Cardinality) The cardinality of a nite set X is
the number of elements in X. We write the cardinality of X as [X[.
Example 4.1 [1, 3, 7[ = 3.
Denition 4.4 (Null Set) The null set (written as or ) is
the set with no elements.
Example 4.2 The null set = x[p(x) p
(x) where p(x) is any

predicate.
'
&
$
%
4.1 Equality of Sets
Denition 4.5 (Set Equality) We say that two sets are equal if
they have the same elements.
We can use the idea of a subset to test for equality.
Denition 4.6 (Subsets) We say a set X is a subset of a set Y
(written X Y ) if all elements of X are elements of Y .
Comment 4.1 Now we can observe that two sets X, Y are equal if
and only if X Y and Y X.
'
&
$
%
Testing for Equality This observation leads us to a practical
technique for testing for set equality when the sets are dened (as
they usually are) using predicates. The key step is how to prove
X Y . RTP x(x X) (x Y ). We simply choose x an
arbitrary xed element of X. Now RTP x Y . More specically;
suppose we are given X = x[p(x) and Y = x[q(x). To show
X Y using the above technique choose x xed, arbitrary in X.
It follows that p(x) T. Now construct a proof that p(x) q(x).
If we can do this we will have established that all elements of X are
elements of Y .
Example 4.3 Given X = x ZZ Z[(4[x) and Y = x ZZ Z[(2[x); to
show that X Y, choose x arbitrary and xed in X. Therefore 4[x
and so x = 4 n for some integer n. We therefore have
x = 2 (2n) and so 2[x as required. It follows that q(x) T and so
x Y . But x was an arbitrary element of X; therefore all elements
of X are elements of Y . Therefore X Y .
'
&
$
%
4.2 Set Operators
Denition 4.7 (Union) Dene union of 2 sets X, Y as the
smallest set containing all the elements of both X and Y ; written
X Y .
Denition 4.8 (Intersection) Dene the intersection of 2 sets
X, Y as the set containing all elements common to both; written
X Y .
Comment 4.2 Suppose X = x[p(x); Y = x[q(x). Then
X Y = x[p(x) q(x) (4.1)
X Y = x[p(x) q(x). (4.2)
Example 4.4 Consider the identity (equation)
X(Y Z) = (XY ) (XZ). We can use our general technique
for proving set equalities; show LHS RHS & RHS LHS.
'
&
$
%
[Case I: LHS RHS] Let x be a xed arbitrary element of
LHS. RTP x RHS. We have that x X (Y Z). There are
two sub-cases:
[x X] Therefore x is an element of both X Y and X Z
and thus x (X Y ) (X Z) = RHS as required.
Therefore LHS RHS.
[x (Y Z)] Exercise: check this case.
[Case II: RHS LHS] Let x be a xed arbitrary element of
LHS. RTP x LHS. We have x X Y and x X Z.
Again there are two sub-cases:
[x X] Trivially; we must have x X (Y Z) = RHS as
required.
[x , X] In this case x Y and x Z so certainly x (Y Z)
and therefore x X (Y Z) = RHS as required.
'
&
$
%
Denition 4.9 (Complement) If a set X is dened by a
predicate p(x), i.e. X = x[p(x) then we can dene the
complement of X; X
c
= x[p(x)
.
Proving Equality Again A much neater way of proving set
identities is to note the equivalence between between set union and
logical OR (Eq. 4.1) and between set intersection and logical AND
(Eq. 4.2):
Union () OR ()
Intersection () AND ()
It follows that the set
X (Y Z) is precisely the set
_
a
p(a)
_
q(a) r(a)
_
_
.
'
&
$
%
But it follows from the Distributive Law for Statement Calculus
Eq. 2.7 that this is equal to
_
a
_
p(a) q(a)
_
_
p(a) r(a)
_
_
which is just
_
X Y
_
_
X Z
_
the required result.
Denition 4.10 (Universal Set) The universal set U is the set
containing all elements of interest or equivalently the set of
which all sets under consideration are subsets. For example if we
are working with the positive integers NN N then U = NN N.
Comment 4.3 For all sets X, X X
c
= U and X X
c
=
'
&
$
%
4.3 Paradoxes in Naive Set Theory
A paradox is simply a contradictory result (real or apparent) which
arises from a theory. Paradoxes often motivate new work which
tidies up and claries a branch of mathematics. One famous
paradox is due to Bertrand Russell and is known as Russells
Paradox.
4.3.1 Russells Paradox
Dene a set / = The set of all sets which contain themselves as
elements. (Using symbolic notation: A = X[X X.) Now
consider the set I = The set of all innite sets. The set I is
certainly non-empty as (for example) RR R I; NN N I; ZZ Z I.
Moreover I is itself an innite set as it has innitely many subsets.
'
&
$
%
For example 0, 1, 2.... ; 1, 2.... ; 2.... ; are all innite sets
and are therefore in I. There are innitely many such subsets, so
I I. Therefore A ,= .
Now dene B = The set of all sets which do not contain
themselves as elements. It is easy to nd examples of sets in B.
Exercise 4.1 Give some examples of sets in B.
So B , = . We now pose the question: Is B B ? The answer
must surely be either yes or no!
[Case 1: B B] Therefore B contains itself as an element. So
B , B. Therefore B does not contain itself as an element.
Contradiction!
[Case 2: B , B] Therefore B has the property that it contains
itself as an element. So B B. Again a contradiction!
'
&
$
%
So the denitions of the sets /, B are paradoxical. The resolution
of the paradox is a more careful denition of the term set which
excludes phrases like the set of all sets which
'
&
$
%
4.4 Power Sets
We begin with a denition.
Denition 4.11 Given a non-empty set A, dene the power set of
A, written T(A), to be the set of all subsets of A.
Example 4.5 Given A = a, b, c, then
T(A) =
_
, a, b, c, a, b, b, c, c, a, a, b, c
_
. Note that
[T(A)[ = 2
3
= 8.
This suggests the following result, which is left as an exercise:
Exercise 4.2 Show that for any nite set A of cardinality n,
[T(A)[ = 2
n
'
&
$
%
1. If X and Y are nonempty sets and XY = YX, what can
we conclude about X and Y?
2. In the following problems, determine whether the statement is
true or false. If the statement is false, give a counterexample.
Take A, B, C as arbitrary subsets of a given universal set U.
(a) A(B C) = (AB) (AC)
(b) (AB) C = A C B C
(c) A(B C) = (AB) (AC)
(d) A (B C) = (A B) (A C)
(e) (A B)
C
= A
C
B
C
(f) A(B C) = (AB) (AC)
(g) A (B C) = (A B) (A C)
(h) A =
'
&
$
%
(i) A (B C) = (A B) (AC)
(j) (A B)
C
= A
C
B
C
'
&
$
%
5 Functions
We saw in Ch. 3 that a set is an unordered collection e.g.
a, b = b, a. We begin with a denition:
Denition 5.1 (Ordered Pair) An ordered pair (a, b) is a set
a, b with the additional property that (a, b) = (c, d) i a = c and
b = d .
Denition 5.2 Given 2 non-empty sets X, Y , dene the
Cartesian Product of X, Y ; written X Y to be the set of all
ordered pairs, (x, y) s.t. x X, y Y = (x, y)[x X, y Y .
Example 5.1 Suppose that X = a, b, c and Y = 1, 2. Then
X Y = (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2).
Exercise 5.1 Check that if X, Y are nite sets, then
[X Y [ = [X[.[Y [ .
'
&
$
%
Denition 5.3 We can consider subsets of X Y . Any such
subset is called a relation. Formally: a relation is a set of ordered
pairs.
Example 5.2 Suppose that X = Tom,Mary,Anne,Eoin and
Y = Computer Science, Mathematics, Ethnomusicology, French.
Use the Table to show which subjects each student studies.
Student Course
Tom Computer Science
Mary Mathematics
Anne French
Eoin Ethnomusicology
Anne Mathematics
Mary Computer Science
'
&
$
%
Now we can represent the relationship studies by the relation
R =
_
(Tom, Computer Science), (Mary, Mathematics),
(Anne, French), (Eoin, Ethnomusicology),
(Anne, Mathematics), (Mary, Computer Science)
_
In particular sets of ordered pairs (relations) where no two
ordered pairs have the same rst element are of interest.
Denition 5.4 (Function) If a relation R X Y has this
property then we say that R is a function from X to Y and write
R : X Y.
'
&
$
%
We can rewrite this denition of a function in a formal notation:
Denition 5.5 A relation R X Y is a function R : X Y if
(x, y
1
) R and (x, y
2
) R y
1
= y
2
Example 5.3 Take X = Y = NN N. Consider the relation
f = (n, 2n + 1)[n X. Clearly f X Y as all elements of f
are ordered pairs of positive integers. Is f a function? Let
(n, y
1
), (n, y
2
) f. We need to show that y
1
= y
2
. We must have
y
1
= 2n + 1; y
2
= 2n + 1 so of course y
1
= y
2
and so f is a
function.
Comment 5.1 (Notation ) If f : X Y is a function, then
write
_
(x, y) f
_
_
y = f(x)
_
. The second form is of course the
one familiar from calculus courses. We will use both notations
interchangeably.
Example 5.4 Consider the previous Example; we can write
y = f(n) = 2n + 1.
'
&
$
%
Example 5.5 Consider X = 1, 2, 3, 4, 5 , Y = 0, 1, 2,
f = (x, x mod 3)[x X (a mod b is the remainder when a is
divided by b). We can list the elements of f:
f = (1, 1), (2, 2), (3, 0), (4, 1), (5, 2). We can conclude that f is a
function as (by inspection) no 2 distinct ordered pairs have same
rst element.
Exercise 5.2 Suppose f = (1, 2), (2, 0), 1, 1), (3, 1). Is f a
function?
'
&
$
%
5.1 Domain, Co-domain & Range
Denition 5.6 (Domain Informal ) If f X Y , (
f : X Y ) , say X is the domain of f.
Example 5.6 Suppose that X = 1, 2, 3, 4, 5 and
f : X Y : x x mod 2. We can write
f = (x, x mod 2)[x X and we can write it more explicitly as
f = (1, 1), (2, 0), (3, 1), (4, 0), (5, 1). Clearly the domain of the
function is just X.
Example 5.7 Given X = 1, 2, 3, 4, 5 , Y = a, b, c and
f = (1, a), (4, c), then the above denition implies that the
domain is X. In fact, a more sensible conclusion is that the
domain is 1, 4 as f 1, 4 a, b, c.
'
&
$
%
This example motivates the following improved denition:
Denition 5.7 (Domain Formal) Given a function
f : X Y , the domain of f is the smallest set containing all the
rst elements of the ordered pairs in f.
Example 5.8 In this example we consider three familiar functions
from our new perspective:
1. sin(x) Formally sin = (x, sin(x))[x RR R. The domain of sin
is clearly RR R.
2. ln(x) Formally log = (x, log(x))[x RR R
+
. The domain of
log is RR R
+
.
3.

x Formally

= (x,
x)[x RR R
+
0. The domain of
is RR R
+
0.
Comment 5.2 Using our two notations we can refer to ln by
ln : RR R
+
RR R or ln RR R
+
RR R.
'
&
$
%
Denition 5.8 (Codomain) If f : X Y (f X Y ), we say
that Y is the co-domain of f.
Example 5.9 Consider our three example functions again:
1. sin(x) The co-domain is RR R but could equally well be dened
to be [1, 1].
2. ln(x) The co-domain is RR R. In fact no smaller set would do.
3.

x The co-domain is RR R but could be RR R
+
0. Note that
the usual problem of resolving the ambiguity in the sign of

x
arises here. Until we do,

x is not a function. We usually
take the positive root as here.
Denition 5.9 Given a function f : X Y (f X Y , dene
R(f) (the range of f) to be the set y Y [(x, y) f, for some
x X or equivalently y Y/y = f(x), for some x X.
'
&
$
%
Comment 5.3 The denition implies that R(f) is always a subset
of the co-domain of f.
Example 5.10 Suppose that X = 1, 2, 3, 4, 5 , Y = a, b, c and
f = (1, a), (4, c). The co-domain is just Y while the range is
a, c which is a subset of Y .
Example 5.11 Consider again our three example functions
(sin / ln /
x):
1. sin(x) The range is [1, 1]
2. ln(x) The range is RR R.
3.

x The range is RR R
+
0.
'
&
$
%
5.2 Properties of Functions
Recall that R(f) the co-domain of f. This motivates the
following denition:
Denition 5.10 Say that a function f : X Y is onto or
surjective if R(f) = the co-domain of f.
Example 5.12 Again we examine our three example functions
(sin / ln /
x).
1. sin(x) Not onto.
2. ln(x) Onto.
3.

x Not onto.
Comment 5.4 By restricting the co-domain Y to the range R(f)
we can always make a function onto.
'
&
$
%
Comment 5.5 (Terminology) If f is onto, we say f is a
function from X onto Y otherwise we say f is a function from X
to Y .
Denition 5.11 (11) A function f : X Y is 11 or
injective if
x
1
, x
2
X, (x
1
, y) f and (x
2
, y) f x
1
= x
2
or equivalently
x
1
, x
2
X, (y = f(x
1
)) and (y = f(x
2
)) x
1
= x
2
Exercise 5.3 Consider our three example functions: (sin / ln /
x).
Are they 11?
'
&
$
%
Comment 5.6 (Alternative denition of 11) A more
user-friendly denition of the 11 property is that a function
f : X Y is 11 if no two ordered pairs have the same second
element. Can you see that this is equivalent to Def. 5.11?
Example 5.13 Consider f : RR R RR R : x x
2
. Is f 11? Assume
x
1
, x
2
RR R s.t.f(x
1
) = f(x
2
). Therefore x
2
1
= x
2
2
. Can we
conclude that x
1
= x
2
? No. (Why?) Therefore f is not 11.
Denition 5.12 (Bijection) If a function f : X Y is 11 and
onto, we say that it is a bijection or that f is bijective.
Bijections have the following nice property (which you should
check).
Comment 5.7 If f is a bijection f : X Y then x X, a
unique y Y such that (x, y) f and also that y Y, a unique
x X, such that (x, y) f.
Exercise 5.4 Prove that the above comment holds.
'
&
$
%
We can now dene the inverse of a function, provided that it is a
bijection.
Denition 5.13 (Inverse) If f : X Y is a bijection then dene
f inverse (written f
1
: Y X) by f
1
= (y, x)[(x, y) f.
We need to establish that this denition gives us a function; in fact
we can do better.
Theorem 5.1 The set of ordered pairs f
1
Y X as dened
above is a function and is a bijection.
'
&
$
%
Proof:
1. RTP f
1
is a function. Assume false so f
1
is not a function.
(We seek to establish a contradiction.) Therefore at least two
ordered pairs must have the same rst element. So we have for
some x
1
,= x
2
X that (y, x
1
) f
1
and(y, x
2
) f
1
. But we
can rewrite these equations (using the denition of f
1
) as
(x
1
, y) fand(x
2
, y) f. But we assumed that f is 11, so
x
1
= x
2
. Contradiction. Therefore f
1
is a function.
2. RTP f
1
is 11. Assume not. Therefore y
1
,= y
2
Y s.t.
(y
1
, x) f
1
and(y
2
, x) f
1
Again, we can translate this into
a statement about f; namely (x, y
1
) fand(x, y
2
) f. But f
is a function, so y
1
= y
2
. Contradiction. Sof
1
is 1-1.
'
&
$
%
3. RTP f
1
is onto. Assume not. Therefore
x
0
Xsty Y, (y, x
0
) , f
1
. This is equivalent to saying
that x
0
Xsty Y, (x
0
, y) , f. But x
0
is in the domain of
f. Contradiction, so f is onto.
We conclude that f
1
is a bijection.
'
&
$
%
5.3 Operations on Functions
Just as we can perform arithmetic on numbers using the familiar
arithmetic operators, we can dene corresponding operations on
functions. The denitions are simple:
Denition 5.14 (Function Sum) Given two functions f, g
dened on a set X, we dene the sum of f, g (written f +g) by
f +g = (x, y
1
+y
2
)[x X; (x, y
1
) f&(x, y
2
) g. Using the
more familiar notation: (f +g)(x) = f(x) +g(x).
Example 5.14 The function sin +3 cos is just the function whose
value for any x RR R is sin(x) + 3 cos(x).
'
&
$
%
Similarly, we can dene the dierence and product of two
functions:
Denition 5.15 (Function Dierence) Given two functions
f, g dened on a set X, we dene the dierence of f, g (written
f g) by f g = (x, y
1
y
2
)[x X; (x, y
1
) f&(x, y
2
) g.
Using the more familiar notation: (f g)(x) = f(x) g(x).
Example 5.15 The function sin cos is just the function whose
value for any x RR R is sin(x) cos(x).
Denition 5.16 (Function product) Given two functions f, g
dened on a set X, we dene the product of f, g (written fg) by
fg = (x, y
1
y
2
)[x X; (x, y
1
) f&(x, y
2
) g. Using the more
familiar notation: (fg)(x) = f(x)g(x).
Example 5.16 The function sin cos is just the function whose
value for any x RR R is sin(x) cos(x).
'
&
$
%
Another useful operation which we can dene on functions is
composition.
Denition 5.17 (Function Composition) Given a function
f : X Y and a function g : Y Z, we can dene a new function
g f : X Z by
g f = (x, z)[(x X) (y Y s.t.(x, y) g & (y, z) g). In
the more familiar notation: (g f)(x) = g(f(x)), x X.
Exercise 5.5 Prove that when g f is dened as above, then it is
indeed a function.
Example 5.17 Let X = 1, 2, 3, 4, Y = a, b, c and Z = p, q, r.
Suppose f = (1, a), (2, a), (3, b), (4, c) and
g = (a, p), (b, q), (c, r). Then g f = (1, p), (2, p), (3, q), (4, r).
Exercise 5.6 Which of the functions f, g, g f are 11, onto?
'
&
$
%
1. Determine whether each of the following sets of ordered pairs is
a function from X = 1, 2, 3, 4 to Y = a, b, c, d. If it is a
function, nd its domain and range and determine whether it is
one-to-one (injective) or onto (surjective). If it is one-to-one
and onto, describe the inverse function as a set of ordered pairs
and give the domain and range of the inverse function.
(1, a), (2, a), (3, c), (4, b) (1, c), (2, a), (3, b), (4, c), (2, d)
(1, c), (2, d), (2, a), (4, b) (1, d), (2, d), (4, a)
(1, b), (2, b), (3, b), (4, b).
2. Give an example of a function that is one-to-one, but not onto.
3. Give an example of a function that is onto, but not one-to-one.
4. Give an example of a function that is neither onto nor
one-to-one.
'
&
$
%
5. Given g : X Y and f : Y Z, verify or nd a
counter-example for each of the following propositions:
(a) If f and g are one-to-one, then f g is one-to-one.
(b) If f and g are onto, then f g is onto.
(c) If f g is one-to-one, then g is one-to-one.
(d) If f g is onto, then f is onto.
(e) If f g is onto, then g is onto.
(f) If f g is one-to-one, then f is one-to-one.
(g) If f and g are one-to-one and onto, then f g is one-to-one
and onto.
6. Let f : X Y . Prove that f is one-to-one if and only if
f(A B) = f(A) f(B), A, B X.
7. Let f : X Y. Show that f is one-to-one if and only if
whenever g is a one-to-one function from any set A to X, f g
is one-to-one.
'
&
$
%
8. Let f : X Y. Show that f is onto Y if and only if
whenever g is a function from Y onto any set Z, g f is onto Z.
9. If X and Y are sets, dene X to be equivalent to Y if there is
a one-to-one and onto function from X to Y. Show that for
any set X, X is not equivalent to T(X) (the power set of X).
10. (Dicult!) Given that f : NN N NN N satises the inequality:
n NN N, f(n + 1) > f(f(n)), show that f is given by
n NN N, f(n) = n.
'
&
$
%
6 Recurrence Relations
In this Chapter, we consider lists (sequences) of numbers a
1
, a
2
,
and formulas like a
n
= a
n1
+a
n2
. We will learn in this Chapter
how to solve such equations and in Chapter 7 how they arise when
solving important problems in Computer Science.
6.1 Sequences and Recurrence Relations
Denition 6.1 A sequence is a function f : NN N RR R : n a
n
.
Comment 6.1 Alternatively a sequence may be thought of a an
ordered list of real numbers (of arbitrary length). We often refer to
the sequence a
1
, a
2
, as the sequence a
n
for brevity.
'
&
$
%
Recurrence relations are equations which express the general
term a
n
of a sequence a
1
, a
2
, , in terms of one or more of its
predecessors. The recurrence equation can be used to calculate
successive terms in the sequence given (say) the values of a
1
and
a
2
. Often the recurrence relation is the result of the mathematical
analysis of some problem (as we will see below and in the next
Chapter). Simply calculating successive terms in the sequence can
be useful but often we seek to calculate a closed form or explicit
formula for the general term a
n
in terms of n. The most general
form of interest is a
n
= f(a
n1
, a
n2
, , a
1
). However equations
as complex as (for example)
a
n
= log(a
n1
+a
n2
sin
2
(a
n1
a
n3
)) +a
n4
can rarely be solved
in closed form. The best we could do for this example would be to
calculate a
5
given a
1
, a
2
, a
3
, a
4
; then calculate a
6
in terms of
a
2
, a
3
, a
4
, a
5
; etc.
'
&
$
%
Exercise 6.1 Find a
5
, a
6
, a
7
given a
1
= 2, a
2
= 3, a
3
= 4, a
4
= 5.
Can you see any pattern to the numbers?
To have any hope of nding systematic solution techniques, we rst
need to restrict ourselves to simple special cases which are still of
interest.
Denition 6.2 A recurrence relation is linear if the unknowns
a
n
, a
n1
appear only as linear combinations ie as terms of
the form a
n1
+a
n2
+a
n3
. A recurrence relation which
is not linear is called non-linear.
Example 6.1 The recurrence relation a
n
= 3a
2
n1
+ 4a
n3
is
non-linear. The recurrence relation a
n
= 3a
n1
+ 4a
n3
+ 7 is
linear.
'
&
$
%
Denition 6.3 A recurrence relation is second-order if a
n
can
be expressed in terms of its immediate presecessors a
n1
, a
n2
only.
In general the order of a recurrence relation is the number of
steps back in the sequence you need to go in order to calculate a
n
.
Example 6.2 The recurrence relation a
n
= 4a
3
n3
+ 5a
n7
is
seventh-order. The recurrence relation a
n
= 2a
n1
+ 5a
2
n2
is
second-order.
Denition 6.4 A recurrence relation has constant coecients
if each term on the RHS only involves terms in the sequence and
constant numeric values.
Example 6.3 The recurrence relation
a
n
= 3a
4
n2
/ ln(a
n3
) + 4a
n6
has constant coecients. The
recurrence relation a
n
= 2
n
a
n1
+ 4na
n2
does not.
'
&
$
%
Denition 6.5 A recurrence relation is homogeneous if every
term on the RHS involves one or more terms in the sequence.
Otherwise the recurrence relation is said to be inhomogeneous.
Example 6.4 The recurrence relation
a
n
= a
3
n3
sin
2
(a
n4
) + 7a
3
n2
is homogeneous. The recurrence
relation a
n
= a
3
n3
sin
2
(a
n4
) +7a
3
n2
+7n
2
+4 is inhomogeneous.
Example 6.5 The Fibonacci sequence 1, 1, 2, 3, 5, 8, can be
generated by the recurrence relation a
n
= a
n1
+a
n2
; where
a
1
= a
2
= 1. This is an example of a linear, homogeneous,
second-order recurrence relation with constant
coecients.
'
&
$
%
6.2 Derivation of a Recurrence Relation
Consider the famous Tower of Hanoi problem. It may be posed
as follows. Start with n heavy disks stacked on the left-handmost
of three posts in decreasing order of size (smallest at the top). The
disks are to be moved (one at a time) from Post 1 to Post 3; while
obeying the rule that a larger disk may not be placed on top of a
smaller one.
{
n Disks
Figure 6.1: Tower of Hanoi at Year Zero
'
&
$
%
Many years later the disks have been moved to post number three.
{
n Disks
Figure 6.2: Tower of Hanoi at Year ?
It is not immediately obvious how long it takes to perform this task
for n disks in units of time where one unit is the time required
to carry one disk from one Post to another. The solution to the
problem leads to the idea of an algorithm.
Denition 6.6 An algorithm is an unambiguous sequence of
operations which solve a specied problem in a nite time.
'
&
$
%
We need to specify an algorithm to solve the Tower of Hanoi
problem. This is easily done for small values of n it rapidly
becomes complicated for (say) n > 3. The insight which leads to a
simple algorithm is the idea of recursion.
Denition 6.7 (Recursion) Informally, a recursive algorithm
is one which refers to itself.
Consider the following recursive algorithm for the Tower of Hanoi
problem:
To solve the n-disk problem:
A: Move the top n 1 disks to the middle Post.
B: Move the biggest (base) disk to its nal destination (RH
Post)
C: Move the top n 1 disks from middle Post to RH Post.
'
&
$
%
Comment 6.2 Note that the procedure or algorithm is not explicit
we always describe the solution procedure for a problem in terms
of the procedure for a problem of size n 1.
Exercise 6.2 Persuade yourself that the above algorithm works by
trying it for (say) n = 3, 4.
Let a
n
be the time taken to solve the problem for n disks. Therefore
a
1
= 1 and a
2
= 3. We can now derive a recurrence relation for
this algorithm. Clearly a
n
= T
A
+T
B
+T
C
(where T
A
, T
B
, T
C
are
the times taken to accomplish steps A,B,C of the algorithm
respectively. We must therefore have: a
n
= a
n1
+ 1 +a
n1
(substituting for T
A
, T
B
, T
C
). Therefore the recurrence relation is:
a
n
= 2a
n1
+ 1 (6.1)
which together with the starting value a
1
= 1 concludes our
analysis of the problem.
'
&
$
%
All that remains is to nd a solution to the recurrence relation, i.e.
to nd an expression for a
n
in terms of n (as a function of n).
We will consider two general solution techniques; the Iteration
Technique & the Substitution Technique. The rst has the
advantage of being applicable to any recurrence relation, although
it may not always yield a closed-form solution. The second is only
applicable to linear, homogeneous, second-order recurrence
relations with constant coecients; but will always yield a closed
form solution. (It can be extended to inhomogeneous recurrence
relations as we will see.)
'
&
$
%
6.3 Iteration Technique
The technique consists simply of repeatedly substituting for
a
n1
, a
n2
, in the RHS of the recurrence relation from the
LHS. In other words, given a recurrence relation of the form
a
n
= f(a
n1
, a
n2
, ); substitute for a
n1
= f(a
n2
, a
n3
, ),
a
n2
= f(a
n3
, a
n4
, ), etc. We try to infer the general pattern
(if any) by studying the formulas obtained for a
n
in the rst few
substitutions. (This is an example of inductive reasoning.) After
we guess a formula for a
n
, we check it by substituting into the
original recurrence relation.
'
&
$
%
Example 6.6 Consider the Tower of Hanoi recurrence relation,
Eq. 6.1. We will apply the above technique.
a
n
= 2a
n1
+ 1 n 2
= 2(2a
n2
+ 1) + 1
= 2
2
a
n2
+ 2 + 1
= 2
2
(2a
n3
+ 1) + 2 + 1
= 2
3
a
n3
+ 2
2
+ 2 + 1
= 2
4
a
n4
+ 2
3
+ 2
2
+ 2 + 1
.
.
.
= 2
n1
a
1
+ 1 + 2 + 2
2
+.....2
n2
Finally, simplifying we get
a
n
= 1 +2 +2
2
+......2
n1
=
2
n
1
21
= 2
n
1. Therefore a
n
= 2
n
1
'
&
$
%
Exercise 6.3 Check that this satises the recurrence relation
ie that a
n
= 2a
n1
+ 1.
More examples may be found in the Exercises at the end of the
Chapter.
'
&
$
%
6.4 Substitution Technique Introduction
We begin with an example. The Fibonacci sequence is generated by
the recurrence relation a
n
= a
n1
+a
n2
; a
1
= a
2
= 1. We want
to nd an expression for a
n
in terms of n. Try a simple substitution
for a
n
which contains a parameter for which we can solve. In other
words, we use a trial solution or ansatz which satises the
equation for some choice of a free parameter.
In our work, the trial solution will usually take the form a
n
= t
n
where t is to be determined. So
a
n
= a
n1
+a
n2
(6.2)
t
n
= t
n1
+t
n2
(6.3)
for all n 3.. Dividing across by t
n2
, we nd that t must satisfy
t
2
t 1 = 0. So t =
1
5
2
= t
(say). We therefore have two

solutions a
n
= t
n
+
and t
n
.
'
&
$
%
But we need the solution for a
n
to give the right answer when
n = 1, 2, i.e. a
1
= 1 and a
2
= 1. To sort out the diculty we need
the following theorem.
Theorem 6.1 If the sequences p
n
and q
n
both satisfy the
n
= a
n1
+a
n2
then for any choice of
A, B (constants) so does the new sequence Ap
n
+Bq
n
.
Proof: We have (substituting p
n
, q
n
into the recurrence relation
and cross-multiplying by A, B respectively):
Ap
n
= p
n1
A+p
n2
A (6.4)
Bq
n
= q
n1
B +q
n2
B (6.5)
and adding we obtain
Ap
n
+Bq
n
= (Ap
n1
+Bq
n1
) +(Ap
n2
+Bq
n2
). (6.6)
'
&
$
%
We now introduce the idea of a general solution to a recurrence
relation. This will allow us to nd a solution which has the right
values for a
1
, a
2
.
Denition 6.8 A general solution to a linear, homogeneous,
second-order recurrence relation with constant coecients is a
sequence with two free parameters (A, B say); any choice of which
yields a solution to the recurrence relation.
So from our 2 solutions t
n
+
, t
n
we can create a general solution

At
n
+
+Bt
n
. We can choose the constants A, B so that the correct

values for a
1
, a
2
are obtained.
Denition 6.9 A solution which does not have free parameters is
called a particular solution.
'
&
$
%
Back to the Fibonacci recurrence relation. We now nd the correct
choice of A, B by requiring that
a
1
1 = At
+
+Bt
(n = 1) (6.7)
a
2
1 = At
2
+
+ +Bt
2
(n = 2) (6.8)
Solving, we nd A =
1
5
and B =
1
5
. So the particular solution
which satises a
1
= 1, a
2
= 1 is a
n
=
1
5
_
(1+
5)
n
2
n

(1
5)
n
2
n
_
.
Note that for large n, a
n

1
5
(1+
5)
n
2
n
.
'
&
$
%
6.5 Substitution Technique Details
Our general technique for solving a recurrence relation of the form
a
n
= c
1
a
n1
+c
2
a
n2
(6.9)
is now clear. Begin with a trial solution a
n
= t
n
, where t is to be
determined. Substituting in the recurrence relation yields a
quadratic in t:
t
2
= c
1
t +c
2
(6.10)
When we solve the quadratic, as usual three cases arise:
1. Two real distinct roots.
2. Equal real roots.
3. Two distinct complex roots.
'
&
$
%
We consider each case separately.
6.5.1 Two Distinct Real Roots
This is the most straightforward case. The Fibonacci example
which we have already studied illustrates the procedure in this case.
6.5.2 Equal Real Roots
So the solution to the quadratic is just t = r (say). A general
quadratic takes the form: t
2
+et +f = 0. If there is a double root
at t = r then we can write the quadratic as (t r)
2
= 0. Expanding
this expression and equationg coecients of t, 1, we nd that
e = 2r and f = r
2
. Now, given our recurrence relation Eq. 6.9;
the quadratic being solved is Eq. 6.10.
'
&
$
%
Therefore c
1
= 2r and c
2
= r
2
and so
c
2
c
1
=
1
2
r. (6.11)
We need a second solution to the recurrence relation as we need 2
unknowns in the general solution corresponding to the 2 starting
values for a
1
, a
2
. We set out to show that a second trial solution is
yielded by a
n
= nr
n
.
Lemma 6.2 The sequence a
n
= nr
n
satises the recurrence
relation Eq. 6.9.
'
&
$
%
Proof: Substituting a
n
= nr
n
in the recurrence relation, we
nd that r must satisfy:
nr
n
= c
1
(n 1)r
n1
+c
2
(n 2)r
n2
(6.12)
The term proportional to n and the remainder must separately
vanish as the equation must hold for all n so we obtain the
two equations: r
n
c
1
r
n1
c
2
r
n2
= 0 (holds as r is a root of the
quadratic Eq. 6.10) and c
1
r
n1
+ 2c
2
r
n2
= 0 (as c
1
, c
2
satisfy
Eq. 6.11).
So the general solution for the Double Real Root case is
a
n
= r
n
+nr
n
. (6.13)
'
&
$
%
Example 6.7 Consider the recurrence relation
a
n
= 4a
n1
4a
n2
; a
1
= 1, a
2
= 3. The substitution a
n
= t
n
reduces to the quadratic t
2
4t +4 = 0 whose only solution is r = 2.
The general solution is a
n
= 2
n
+n2
n
. When we incorporate the
starting values for a
1
, a
2
, we get the pair of equations:
1 = 2 + 2 (n = 1) (6.14)
3 = 4 + 8 (n = 2) (6.15)
whose solution is = = 1/4. So the particular solution (the
solution which satises the given values for a
1
, a
2
) is
1
4
2
n
+
1
4
n2
n
= 2
n2
(n + 1).
'
&
$
%
6.5.3 Complex Roots
We have the general solution a
n
= (r
1
)
n
+(r
2
)
n
where r
1
, r
2
are
2 roots of t
2
c
1
t c
2
= 0. In general, given t
2
+et +f = 0, the
solution is of course
e
(e
2
4f)
2
. If (e
2
4f) < 0 (the case where
the roots are complex) then call
_
e
2
4f = iB where B is real
and positive and i =

1. Call
e
2
= A. Then the roots are
r
1
= A+iB and r
2
= AiB. Note that the two roots come in a
mirror image or conjugate pair. We can write any complex
number A+iB in so-called polar form D(cos +i sin ) where
D =

A
2
+B
2
and tan = B/A.
Now De Moivres Theorem states that
(cos +i sin )
n
= cos n +i sin n. So we can write the general
solution to our recurrence relation as
D
n
(cos n +i sin n) +D
n
(cos n i sin n) (6.16)
'
&
$
%
The problem with this form for the solution is that , are (in
general) complex numbers while we know that the solution to a
recurrence relation where the coecients are all real must
themselves be real. (Why?) If we write =
1
+i
2
and
=
1
+i
2
and substitute into Eq. 6.16 we nd that the general
solution is
D
n
_
1
cos n
2
sin n +i(
1
sin n +
2
cos n)
+
1
cos n
2
sin n +i(
1
sin n +
2
cos n)
_
'
&
$
%
However using the fact that the solution is real, we can drop all the
terms prexed by i and write the general solution as:
D
n
[ cos n + sin n] (6.17)
where , are arbitrary constants and D, are computed from the
quadratic as explained above.
a
n
= 2a
n1
5a
n2
[a
1
= 1; a
2
= 3. The usual substutution
a
n
= t
n
yields the quadratic t
2
2t + 5 = 0 whose roots are 1 2i.
So (in terms of our previous analysis), A = 1 and B = 2. First
calculate D =

A
2
+B
2
which gives D =

5. Now we need to
calculate the angle fro the equation tan = B/A. We therefore
have tan = 2 and so = arctan 2. (There is no need to
numerically evaluate at this stage.)
'
&
$
%
Our general solution is therefore: 5
n/2
_
cos n + sin n
_
. We
have the initial conditions a
1
= 1 and a
2
= 3 so we have
1 =

5(cos + sin ) (n = 1)
3 = 5(cos 2 + sin 2)
and, substituting for
1 = + 2
3 = 3 + 4
Exercise 6.4 Solve for , and write the general term a
n
.
'
&
$
%
6.6 Substitution Technique Inhomogeneous
Case
We now know how to solve linear homogeneous order 2 recurrence
relations with constant coecients; i.e. recurrence relations of
form a
n
= c
1
a
n1
+c
2
a
n2
. We will now extend the technique to
inhomogeneous recurrence relations of form
a
n
= c
1
a
n1
+c
2
a
n2
+f(n) where f is an arbitrary given function
of n.
Example 6.9 Consider the recurrence relations
a
n
= 2a
n1
a
n3
+n
2
+ 1 and a
n
= 2a
n1
+ 4a
n2
+ sin(n).
The technique for homogeneous recurrence relations doesnt work
as if we substitute a
n
= t
n
in such a recurrence relation, we get
t
n
= c
1
t
n1
+c
2
t
n2
+f(n), which cannot be solved for t in general
without t depending on n. The extended technique can be stated
as a theorem:
'
&
$
%
Theorem 6.3 Let a
n
be the general solution of the recurrence
relation
a
n
= c
1
a
n1
+c
2
a
n2
+f(n). (6.18)
Then, given a particular solution p
n
(see Def. 6.9), we can write
a
n
= p
n
+h
n
; where h
n
is a general solution of the homogeneous
equation which can be constructed by deleting f(n) from eq. 6.18,
namely a
n
= c
1
a
n1
+c
2
a
n2
.
'
&
$
%
Proof: Given
a
n
= c
1
a
n1
+c
2
a
n2
+f(n) (6.19)
h
n
= c
1
a
n1
+c
2
h
n2
(6.20)
and assuming we have a particular solution p
p
n
= c
1
p
n1
+c
2
p
n2
+f(n) (6.21)
then, subtracting Eq. 6.21 from Eq. 6.19 we have that
(a
n
p
n
) = c
1
(a
n1
p
n1
) +c
2
(a
n2
p
n2
). (6.22)
This equation has the same form as Eq. 6.20; so, as h
n
is the
general solution of the homogeneous equation, we must have
a
n
p
n
= h
n
. Thus
a
n
= h
n
+p
n
, (6.23)
as required.
'
&
$
%
a
n
= 5a
n1
6a
n2
+ 9 with initial values a
1
= 1 and a
2
= 1.
First we solve the homogeneous recurrence relation
a
n
= 5a
n1
6a
n2
. The solution is h
n
= 2
n
+3
n
.(Check.)
Now we need a particular solution of the full equation. We try
the simplest possible choice: p
n
= K a constant. Substituting
the the recurrence relation yields K = 5K 6K + 92K = 9, so
we have K = 4
1
2
and therefore p
n
= 4
1
2
.
So the general solution of the inhomogeneous recurrence
relation is a
n
= h
n
+p
n
= 2
n
+3
n
+ 4
1
2
.
Exercise 6.5 Find the particular solution to the above recurrence
relation which satises the given initial conditions.
'
&
$
%
We need a structured approach to the task of nding a particular
solution to a given inhomogeneous recurrence relation. We adopt
as our guiding principle that we should use the simplest solution
possible. Consider a succession of increasingly complex possible
forms for f(n).
6.6.1 Polynomial Inhomgeneous Term
Suppose that f(n) is a polynomial in n. In particular, suppose that
f(n) = An
2
+Bn +C a quadratic in n. Then our recurrence
relation takes the form a
n
= c
1
a
n1
+c
2
a
n2
+An
2
+Bn +C.
For a trial solution p
n
to satisfy this equation, it must be at least a
quadratic in n i.e. at least p
n
= Kn
2
+Ln +M. In general the
trial solution P
n
must be a polynomial of degree at least equal to
that of f(n).
'
&
$
%
Example 6.11 Consider the example
a
n
= 3a
n1
+ 7a
n2
+ 2n
2
+ 6n + 1. Substituting
p
n
= An
2
+Bn +C for a
n
in the recurrence relation gives us
An
2
+Bn +C = 3(A(n 1)
2
+B(n 1) +C)
+ 7(A(n 2)
2
+B(n 2) +C) + 2n
2
+ 6n + 1. (6.24)
Now gather together on the LHS the n
2
, n and constant terms.
They must each sum to 0. (Why?) We have
A3A7A2 = 0 (6.25)
B + 6A3B + 28A6 = 0 (6.26)
C 3A+ 3B 3C 28A+ 14B 7C 1 = 1. (6.27)
Solving for A, B, C yields a particular solution.
'
&
$
%
Exercise 6.6 Use Maple to solve the above set of equations and
solve the above recurrence relation for the initial values a
1
= 1,
a
2
= 3. Do you really need Maple?
The problem may be degenerate and this rule may not work, e.g.
a
n
= 4a
n1
3a
n2
+ 15. Try p
n
= K. Then K must satisfy
K = 4K 3K + 15. So K = K + 15 and therefore 0 = 15. The
problem is degenerate as h
n
= 3
n
+(1)
n
= 3
n
+. Try p
n
=
Kn. (There is no need for a constant term as h
n
already includes
one.) Then
Kn = 4K(n 1) 3K(n 2) + 15
Exercise 6.7 Try solving for K.
'
&
$
%
6.6.2 Trigonometrical Inhomogeneous Term
Suppose that f(n) is a cos or sin. For example, consider the
n
= 2a
n1
3a
n2
+ 2 cos(n) 7 sin(n). The
most general needed p
n
takes the form Acos n +Bsin n.
Exercise 6.8 Substitute the above trial solution in the given
recurrence relation and solve for A, B.
'
&
$
%
1. Suppose that you have n dollars and that each day you buy
either orange juice ($1), milk ($2) or beer ($2). If c
n
is the
number of ways of spending all the money, show that
c
n
= c
n1
+ 2c
n2
.
2. Let c
n
denote the number of regions into which the plane is
divided by n lines. Assume that each pair of lines meet in a
point, but that no three lines meet in a point. Derive a
recurrence relation for the sequence c
1
, c
2
, . . .. Hint: What is
the eect of adding one extra line?
3. If o is a bit string, let C(o) be the maximum number of
consecutive 0s in o. Let s
n
be the number of n-bit strings o
with C(o) 2. Develop a recurrence relation for s
1
, s
2
, . . ..
'
&
$
%
4. Ackermans function A(m, n) is dened in Johnsonbaugh by
the recurrence relations
A(m, 0) = A(m1, 1), m = 1, 2, . . .
A(m, n) = A(m1, A(m, n 1)), m = 1, 2, . . . n = 1, 2, . . .
and the initial conditions
A(0, n) = n + 1, n = 0, 1, 2, . . .
(a) Use induction to show that
A(1, n) = n + 2, n = 0, 1, . . .
(b) Use induction to show that
A(2, n) = 3 + 2n, n = 0, 1, . . .
(c) Guess a formula for A(3, n) and prove it using induction.
'
&
$
%
5. Solve the following recurrence relations with the given initial
conditions:
a
n
= 3a
n1
; a
0
= 2,
a
n
= 2na
n1
; a
0
= 1,
a
n
= a
n1
+n; a
0
= 0,
2a
n
= 7a
n1
3a
n2
; a
0
= a
1
= 1,
2a
n
= 7a
n1
3a
n2
+n + 1; a
0
= a
1
= 1,
2a
n
= 7a
n1
3a
n2
+ cos n; a
0
= a
1
= 1,
2a
n
= 7a
n1
5a
n2
+ 1; a
0
= a
1
= 1,
a
n
=

a
n1
+ 2
a
n2
; a
0
= a
1
= 1,
a
n
=
a
n1
a
2
n2
; a
0
= 1, a
1
= 2,
a
n
= 2na
n1
+ 3n(n 1)a
n2
; a
0
= 1, a
1
= 2.
'
&
$
%
7 Application: Analysis of Algorithms
We have already dened the term algorithm, the denition is
repeated here for convenience.
Denition 7.1 (Algorithm) An algorithm is an unambiguous
sequence of steps which completes a task in a nite time.
In this Chapter we use recurrence relations to analyse the
execution time needed by algorithms. Given a particular
algorithm, we will nd a recurrence relation (and initial
conditions) that dene a sequence a
1
, a
2
, . . . ,, where a
n
is the time
taken by the algorithm to solve a problem of size n.
'
&
$
%
We usually distinguish between
Best Case: the time taken under the most favourable
assumptions possible.
Worst Case: the time taken under the least favourable
assumptions possible.
Average Case: the time taken when we average over all possible
input types.
In many situations, the average case is the one of interest, though
it can be useful to know the best and worst case execution times as
they bracket the actual time for a particular problem. Often we are
more interested with the approximate rate of growth of the
execution time as n increases than with the exact formula.
'
&
$
%
Example 7.1 Suppose that the worst case time for an algorithm is
t(n) = 60n
2
+ 5n + 1
for an input of size n. For large n, it is reasonable to say that
t(n) 60n
2
.
Note that if time in the latter example was measured in seconds
then
t(n) = n
2
+
5n
60
+
1
60
when time is measured in minutes. This change of units does not
change the rate of growth in t(n); it just changes t(n) by a constant
factor. For this reason, when we want to describe how the
execution time grows as n, we not only look for the dominant
(most important) term (e.g. 60n
2
), but also ignore constant
coecients (factors).
'
&
$
%
For the present example, we would say that t(n) grows like n
2
as n
increases. We say that t(n) is of order at most n
2
and write
t(n) = O(n
2
)
which is spoken as t(n) is big oh of n
2
or just t(n) is of order
n
2
. We now dene these terms formally:
Denition 7.2 Let f and g be functions with domain
_
1, 2, 3, . . .
_
. We write
f(n) = O(g(n))
and say f(n) is of order at most g(n) if there exists a positive
constant C such that
[f(n)[ C[g(n)[
for all n suciently large (greater than some minimum value N).
'
&
$
%
Example 7.2 Since
60n
2
+ 5n + 1 60n
2
+ 5n
2
+n
2
= 66n
2
for n 1,
we may take C = 66 in Def. 7.2 to get
60n
2
+ 5n + 1 = O(n
2
).
Example 7.3 The function 2n + 3 log
2
n < 2n + 3n = 5n (as
log
2
n < n for n 1). So
2n + 3 log
2
n = O(n).
Example 7.4 If k is a positive integer , then
1
k
+ 2
k
+ +n
k
n
k
+n
k
+ +n
k
= n n
k
= n
k+1
for n 1; so
1
k
+ 2
k
+ +n
k
= O(n
k+1
).
'
&
$
%
Example 7.5 Since (by the Triangle Inequality)
[3n
3
+ 6n
2
4n + 2[ 3n
3
+ 6n
2
+ 4n + 2
3n
3
+ 6n
3
+ 4n
3
+ 2n
3
= 15n
3
for n 1,
it follows that
3n
3
+ 6n
2
4n + 2 = O(n
3
).
'
&
$
%
7.1 Selection Sort Algorithm
Consider the following algorithm Selection Sort. It sorts a
sequence s
1
, s
2
, . . . , s
n
into ascending order by rst selecting the
largest item and placing it last and then recursively sorting the
remaining elements.
[Input:] A sequence s
1
, s
2
, . . . , s
n
[Output:] s
1
, s
2
, . . . , s
n
arranged into ascending order.
'
&
$
%
Example 7.6 Algorithm 7.1 (Selection Sort)
1 begin
2 if n = 1
3 then STOP
4
5 MaxIndex := 1
6 for i := 2 to n do
7 if s[i] > s[MaxIndex]
8 then MaxIndex := i
9
10 od
11 SWAP s[n], s[MaxIndex]
12 Selection Sort (s[1], . . . , s[n-1])
13 end
'
&
$
%
Now, to analyse the time-complexity of this algorithm. we count
the number of comparisons t
n
at line 7. (For this algorithm, the
best-case, average-case and worst-case times are all the same.) We
immediately nd the initial condition
t
1
= 0.
To nd a recurrence relation for the sequence t
1
, t
2
, . . . , we
simulate the execution of the algorithm for an arbitrary input of
size n > 1. We count the number of comparisons at each line and
then sum these numbers to nd the total number of comparisons
t
n
. At line 7 there are n 1 comparisons (as the for loop is
executed n times) and at line 12 there are t
n1
comparisons as we
are sorting a list of size n 1.
So we have the required recurrence relation :
t
n
= t
n1
+n 1.
'
&
$
%
We can solve this using the Iteration Method as follows:
t
n
= t
n1
+n 1
= (t
n2
+n 2) +n 1
= (t
n3
+n 3) + (n 2) +n 1
.
.
.
= t
1
+ 1 + 2 + + (n 2) + (n 1)
= 0 + 1 + 2 + + (n 1)
=
n(n 1)
2
= O(n
2
).
'
&
$
%
7.2 Binary Search algorithm
In this subsection, we consider a classic recursive algorithm and
analyse its complexity. First, a technical denition.
Denition 7.3 Dene the oor of a real number x to be the
largest integer x. Write this as x or x|.
Example 7.7 The oor of 3.7 is 3, the oor of 2.0 is 2, the oor
of -3.1 is 4.
Consider the following algorithm Binary Search. It searches
an ordered sequence s
1
, s
2
, . . . , s
n
for a key and returns the
index (position) of the key if it is found and zero if it is not.
i
, s
2
, . . . , s
j
, i 1 sorted into ascending
order, together with a value key which is to be searched for.
[Output:] An index k for which s[k] = key, or if key is not in the
sequence, the output is the value 0.
'
&
$
%
Algorithm 7.2 (Binary Search)
1 begin
2 left := i
3 right := j
4 if left > right
5 then
6 k := 0
7 STOP (Failed)
8
9 k :=
left+right
2

10 if (key = s[k])
11 then STOP (Succeeded)
12
13 if (key < s[k])
14 then j := k 1
15 else i := k + 1
16
17 Binary Search (s[i], . . . , s[j])(Recursive Call)
18 end
'
&
$
%
Dene t
n
for this problem to be the number of times of times the
algorithm is invoked (called) in the worst case for a list of n items.
Suppose that n = 1. Then the sequence consists of one element s
i
and i = j. In the worst case, the item will not be found at line 10
so the algorithm will be invoked a second time at line 17. However,
now i > j and so the algorithm will terminate with failure at
line 7. So the algorithm has been invoked twice and therefore:
t
1
= 2.
Suppose now that n > 1. In this case i > j, so at line 4, the
condition left > right will be false. In the worst case, the item will
not be found at line 10 and so the algorithm will be invoked at
line 17. The invocation at line 17 will require a total of t
m
invocations, where m is the size of the sequence that is input at
line 17.
'
&
$
%
Since the sizes of the left and right sides of the original sequence
are
n1
2
| and
n
2
| respectively and as the worst case occurs when
the sequence is larger; the total number of invocations at line 17
will be t
n
2
. The original invocation together with the invocation

at line 17 gives the total number of invocations. We therefore have
the recurrence relation :
t
n
= 1 +t
n
2
; t
1
= 2. (7.1)
We now need to solve the recurrence relation 7.1. Rather than try
to solve for all n; consider the special case n = 2
k
, which allows the
recurrence relation to be solved exactly. We obtain:
t
2
k = 1 +t
2
k1; k 1. (7.2)
We can greatly simplify this with the substitution u
k
= t
2
k, which
yields:
u
k
= 1 +u
k1
; k 0, u
0
= 2. (7.3)
'
&
$
%
It is easy to see that the solution to this recurrence relation is
u
k
= k + 2, k 0. Reverting to the original sequence t
n
, we have
t
2
k = k + 2 and so, when n is a power of two, we have
t
n
= log
2
(n) + 2. (7.4)
We could conjecture that t
n
= log
2
(n) + 2 for all n; but this cannot
be correct as log
2
(n) is only an integer for n a power of 2. The
simplest change we can make to the solution which might work is
to try t
n
= log
2
(n)| + 2. We could simply substitute into the
recurrence relation Eq. 7.1 but to do this is precisely to prove the
formula by induction; and Strong Induction at that!
Exercise 7.1 Discuss.
'
&
$
%
Theorem 7.1 Given the recurrence relation Eq. 7.1, the solution
is t
n
= log
2
(n)| + 2, n 1.
Proof: Use the Strong Principle of Induction.
[Basis Step] Straightforward.
[Inductive Step] Assume that t
k
= log
2
(k)| + 2, k < n. We
need to show that t
n
= log
2
(n)| + 2. (Note that we need
Strong Induction, as we need to assume the formula holds in
particular for k =
n
2
|, not just for k = n 1.) We need to
consider the cases n even and n odd separately.
'
&
$
%
[n Even] We have t
n
= t
n
2
+ 1. As n is even, we can replace
n
2
| by
n
2
. So;
t
n
= t
n
2
+ 1.
Now use the inductive hypothesis:
t
n
2
= log
2
(
n
2
)| + 2
= log
2
(n) log
2
(2))| + 2
= log
2
(n)| 1 + 2
= log
2
(n)| + 1
and so
t
n
= t
n
2
+ 1
= log
2
(n)| + 1 + 1
= log
2
(n)| + 2
as required.
'
&
$
%
[n Odd] As n is odd, we must replace
n
2
| by
n1
2
. So;
t
n
= t n1
2
+ 1.
Now use the inductive hypothesis:
t n1
2
= log
2
(
n 1
2
)| + 2
= log
2
(n 1) log
2
(2))| + 2
= log
2
(n 1)| 1 + 2
= log
2
(n 1)| + 1.
But, as n is odd, log
2
(n) cannot be a whole number and so
log
2
(n 1)| = log
2
(n)|
The nal steps are as for the Even Case.
'
&
$
%
We can therefore conclude that the execution time for a Binary
Search of an Ordered List is O(log
2
(n)). This is very fast compared
with the times for searching an unordered list.
'
&
$
%
7.3 Insertion Sort
This algorithm sorts the sequence s
1
, . . . , s
n
into increasing order
by recursively sorting the rst n 1 elements and then inserting s
n
in the correct position.
1
, s
2
, . . . , s
n
.
[Output:] The sequence s
1
, s
2
, . . . , s
n
arranged into ascending
order.
'
&
$
%
Algorithm 7.3 (Insertion Sort)
1 begin
2 if n = 1
3 then
4 STOP
5
6 Insertion Sort (s[1], . . . , s[n-1])(Recursive Call)
7 i := n 1
8 temp := s[n]
9 while (i 1) (s[i] > temp) do
10 s[i + 1] := s[i]
11 i := i 1
12 od
13 s[i + 1] := temp
14 end
'
&
$
%
Let t
n
be the number of times the comparison (s[i] > temp) in
line 9 is made in the worst case. We can assume that, if i < 1, the
comparison is not made.
Exercise 7.2 Check that the algorithm correctly sorts the list
5, 2, 7, 3, 1, 4.
Exercise 7.3 Show that the worst case arises when the list to be
sorted in in descending order.
Clearly t
1
= 0 and t
2
= 1.
Exercise 7.4 Check that t
3
= 3.
In general, for n > 1; the recursive call at line 6 yields t
n1
comparisons (as the input to this call is a list of n 1 elements). In
the worst case the while loop at line 9 is executed n 1 times. So
the total number of comparisons for a list of size n is t
n1
+n 1.
'
&
$
%
We can write the recurrence relation :
t
n
= t
n1
+n 1; t
1
= 0.
Exercise 7.5 Show that the solution is
t
n
=
n(n 1)
2
.
Clearly we can conclude that t
n
= O(n
2
). More importantly, we
nd that Insertion Sort and Selection Sort have execution times of
the same order. We end this Chapter by considering a more
complex sorting algorithm with much faster performance.
'
&
$
%
7.4 Merge Sort
The Merge Sort algorithm takes a sequence s
i
, . . . , s
j
and divides it
into two nearly equal sequences s
i
, . . . , s
m
and s
m+1
, . . . , s
j
; where
m =
_
i +j
2
_
. Each of these sequences in then recursively sorted
(by dividing in two & sorting, ...) after which they are combined to
produce a sorted version of the original sequence. The process of
combining two sorted sequences into a new list (also in ascending
order) is called merging.
We begin by describing the Merge algorithm .
[Input:] Two sorted sequences s
i
, . . . , s
m
and s
m+1
, . . . , s
j
.
[Output:] The sequence c
i
, , c
j
consisting of the two input
sequences combined (in ascending order).
'
&
$
%
Algorithm 7.4 (Merge)
1 begin
2 p := i (p is the index in the first input sequence)
3 q := m + 1 (q is the index in the second input sequence)
4 r := i (r is the index in the combined output sequence)
5 while (p m) (q j) do
6 if (s[p] < s[q]) then
7 c[r] := s[p]
8 p := p + 1
9 else
10 c[r] := s[q]
11 q := q + 1
12
13 r := r + 1
14 od
15 while (p m) do (Copy remainder of first sequence)
16 c[r] := s[p]
17 p := p + 1
18 r := r + 1
19 od
20 while (q j) do (Copy remainder of second sequence)
21 c[r] := s[q]
22 q := q + 1
23 r := r + 1
24 od
25 end
'
&
$
%
Exercise 7.6 Try stepping through the algorithm with the two
sequences 1, 3, 4 and 2, 4, 5, 6 as input.
In the Merge algorithm, the comparison of elements in the
sequences occurs at line 6. This loop will execute as long as (p m)
and (q j). So, in the worst case, the algorithm requires j i
comparisons. (This worst case occurs when members of the rst
and second sequences are alternately selected to enter the combined
sequence; e.g. s(1, . . . , 3) = (1, 3, 5) and s(4, . . . , 6) = (2, 4, 6).)
We now describe the main algorithm (which uses the Merge
algorithm as a tool):
'
&
$
%
i
, . . . , s
j
.
[Output:] The sequence s
i
, , s
j
in ascending order.
Algorithm 7.5 (Merge Sort)
1 begin
2 if i = j then STOP
3
4 m :=
_
i+j
2
_
5 Merge Sort (s[i], . . . , s[m])(Recursive Call 1
st
Part)
6 Merge Sort (s[m+1], . . . , s[j])(Recursive Call 2
nd
Part)
7 Merge (s(i, . . . , m) and s(m+ 1, . . . , j))(Merge Sorted Parts)
8 s(i, . . . , j) := c(i, . . . , j)(Copy c onto s.)
9 end
'
&
$
%
Finally, we need to determine the worst case execution time of the
Merge Sort algorithm. Because of the complexity of the
argument, we state it as a Theorem. We want to show that the
algorithm has a worst case execution time of O(nlog
2
n), i.e. that
t
n
Cnlog
2
n for some positive constant n.
Theorem 7.2 The Merge Sort algorithm requires at most
4nlog
2
n comparisons to sort n items in the worst case.
Proof: Let t
n
be the number of comparisons required by
Merge Sort to sort n items in the worst case. Clearly t
1
= 0. If
n > 1, then at line 5 at most t
n+1
2

comparisons are needed.
Similarly at line 6 at most t
n
2
comparisons are needed.

Exercise 7.7 Check; consider the cases n even and n odd.
'
&
$
%
At line 7, at most n 1 comparisons are needed. Therefore:
t
n
t
n+1
2

+t
n
2
+n (7.5)
(We have replaced n 1 by n note the . This simplies the
following discussion. Purists may like to try Exercise 2 below.) The
price we pay is the introduction of the inequality; which means we
do not have a recurrence relation. Now dene the sequence
u
1
, u
2
, . . . by the recurrence relation
u
n
= u
n+1
2

+u
n
2
+n; u
1
= 0. (7.6)
We use the standard trick of considering the special case n = 2
k
,
which yields:
u
2
k = 2u
2
k1 + 2
k
; u
1
= 0.
'
&
$
%
or, dening v
k
= u
2
k;
v
k
= k; v
0
= 0.
We can solve this recurrence relation using the Iteration Method.
v
k
= 2v
k1
+ 2
k
= 2
_
2v
k2
+ 2
k1
+ 2
k
= 2
2
v
k2
+ 2 2
k
= 2
_
2v
k3
+ 2
k2
+ 2 2
k
= 2
3
v
k3
+ 3 2
k
.
.
.
= 2
k
v
0
+k2
k
= k2
k
'
&
$
%
So, when n is a power of 2,
u
n
= nlog
2
n. (7.7)
We want to show that t
n
4nlog
2
n, for n = 1, 2, 3, . . . .
Exercise 7.8 It is easy to check that the result holds for n = 1, 2.
We may assume that n > 2. We assume the results of Lemma 7.3
and Lemma 7.4 below; namely that
u
n
u
n+1
; n = 1, 2, 3, . . . (7.8)
and
t
n
u
n
; n = 1, 2, 3, . . . (7.9)
Let n > 2 be arbitrary but xed. First, choose k such that
2
k
< n < 2
k+1
. Then, by Eq. 7.7 and Eq. 7.8, we have:
u
n
u
2
k+1 = (k + 1)2
k+1
(k +k)2
k+1
= 4k2
k
4nlog
2
n.
'
&
$
%
Finally, by Eq. 7.9, we have
t
n
4nlog
2
n,
as required.
Finally, we tidy up the loose ends by proving the two Lemmas
quoted in the above proof.
'
&
$
%
Lemma 7.3 Given the denitions used in Theorem 7.2, then
u
n
u
n+1
; n = 1, 2, 3, . . . , i.e. Eq. 7.8 above.
Proof: Use the Strong Principle of Induction.
[Basis Step] u
1
= 0 < 2 = 2u
1
+ 2 = u
2
.
[Inductive Step] Assume that the inequality holds for k < n.
Now,
u
n+1
= u
n+2
2

+u
n+1
2

+n + 1
u
n+1
2

+u
n
2
+n = u
n
,
as required.
'
&
$
%
Lemma 7.4 Given the denitions used in Theorem 7.2, then
t
n
u
n
; n = 1, 2, 3, . . . , i.e. Eq. 7.9 above.
Proof: Again, use the Strong Principle of Induction.
[Basis Step] By denition of u
1
, we have u
1
1 t
1
= 1.
[Inductive Step] We assume that the inequality holds for k < n.
Now, by Eq. 7.5 we have
t
n
t
n+1
2

+t
n
2
+n
u
n+1
2

+u
n
2
+n
= u
n
as required.
'
&
$
%
In conclusion, we have found that Merge Sort is O(nlog
2
n) in
the worst case and is therefore much more ecient than either
Insertion Sort or Selection Sort. The analysis of the average
case execution time is of great importance but is too involved for
the present course.
'
&
$
%
1. Consider the following algorithm: ListSearch
Find the largest and smallest elements in an array
s[1], . . . , s[n]. The largest element is returned in large and the
least element in small.
'
&
$
%
Algorithm 7.6 (ListSearch)
1 begin
2 if (n = 1)
3 then large := s[1]
4 small := s[1]
5
6 return
7 m := (
n+1
2
)
8 call LISTSEARCH(s[1], .., s[m])
9 large left := large
10 small left := small
11 call LISTSEARCH(s[m + 1], .., s[n])
12 large right := large
13 small right := small
14 if (large left > large right)
15 then large := large left
16 else large := large right
17
18 if (small left > small right)
19 then small := small right
20 else small := small left
21
22 return
23 end
Let tn be the number of comparison steps required for an input of size n. Establish the
recurrence relation
tn = t
n
2
+ t
n+1
2

+ 2.
Solve the recurrence relation.
'
&
$
%
2. Show that when the recurrence relation
t
n
= t
n+1
2

+t
n
2
+n 1; t
1
= 0
is solved for n = 2
k
, the result is t
2
k = k2
k
2
k+1
+ 1.
3. Use a plotting package (e.g. Maple) to plot the functions n
2
and nlog
2
n. How big does n have to be for the two functions
to dier by a factor of 10?
'
&
$
%
4. Consider the following algorithm , Exponential1.
[Input:] A real number a and a positive integer n.
[Output:] exp = a
n
.
Algorithm 7.7 (Exponential1)
1 begin
2 if n = 1 then
3 exp := a
4 STOP
5
6 m := n/2|
7 exp1 := Exponential1 (a, m)(Recursive Call 1
8 exp2 := Exponential1 (a, n m)(Recursive Call 2)
9 exp := exp1 exp2
10 end
'
&
$
%
(a) Let t
n
be the number of multiplications (line 9) required
to compute a
n
. Find a recurrence relation and initial
conditions for this algorithm .
(b) Solve the recurrence relation found in the previous
question your answer should be
t
n
= n 1, n = 1, 2, . . . . (First solve the recurrence
relation for n = 2
k
then use induction to show the formula
holds for n = 1, 2, 3, . . . .)
(c) What is the order of Exponential1?
'
&
$
%
5. Consider the following algorithm , Exponential2.
[Input:] A real number a and a positive integer n.
[Output:] exp = a
n
.
Algorithm 7.8 (Exponential2)
1 begin
2 if n = 1 then
3 exp := a
4 STOP
5
6 m := n/2
7 exp := Exponential2 (a, m)(Recursive Call)
8 exp := exp exp
9 if n is odd then
10 exp := exp a
11
12 end
Again, let t
n
be the number of multiplications (lines 8 and 10).
'
&
$
%
(a) Show that
t
n
=
_
_
_
t
(n1)/2
+ 2 if n is odd
t
n/2
+ 1 if n is even
(b) Find t
1
, t
2
, t
3
, t
4
.
(c) Solve the above recurrence relation for the case where n is
a power of 2. You should nd t
n
= log
2
n.
(d) Prove that t
n
2 log
2
n for n = 1, 2, 3, . . . .
(e) What is the order of Exponential2?
6. Which of the two exponential algorithms would you
recommend and why?
'
&
$
%
A Supplementary Material
The following material is included in the hope that the reader will
nd it interesting perhaps even entertaining!
A.1 In Praise of Lectures
The following is quoted verbatim from a short lecture published on
the Internet by T. W. Korner of the Dept. of Pure Mathematics
and Mathematical Statistics, University of Cambridge. It may be
found at:
http://www.dpmms.cam.ac.uk/site2000/Sta/korner01.html
'
&
$
%
The Ibis was a sacred bird to the Egyptians and worshippers
acquired merit by burying them with due ceremony. Unfortunately
the number of worshippers greatly exceeded the number of birds
dying of natural causes so the temples bred Ibises in order that
they might be killed and and then properly buried.
So far as many mathematics students are concerned university
mathematics lectures follow the same pattern. For these students
attendance at lectures has a magical rather than a real signicance.
They attend lectures regularly (religiously, as one might say) taking
care to sit as far from the lecturer as possible (it is not good to
attract the attention of little understood but powerful forces) and
take complete notes. Some lecturers give out the notes at such
speed (often aided by the technological equivalent of the Tibetan
prayer wheel an overhead projector) that the congregation is
fully occupied but most fail in this task.
'
&
$
%
The gaps left empty are lled by the more antisocial elements with
surreptitious (or not so surreptitious) conversation
a
, reading of
newspapers and so on whilst the remainder doodle or daydream.
The notes of the lecture are then kept untouched until the holidays
or, more usually, the week before the exams when they are carefully
highlighted with day-glow yellow pens (a process known as
revision). When more than 50% of the notes have been highlighted,
revision is said to be complete, the magical power of the notes is
exhausted and they are carefully placed in a le never to be
consulted again.
a
A lecture is a public performance like a concert or a theatrical event. Televi-
sion allows channel hopping and conversation. At public performances, private
conversation, however interesting to the participants, distracts the rest of the
audience from the matter in hand. It must be added that just as good eaters
make good cooks so good audiences make for good lectures. A lecturer will give
a better lecture to a quiet and attentive audience than to a noisy and inattentive
one.
'
&
$
%
(Sometimes the notes are ceremonially burnt at the end of the
students university career thereby giving a vivid demonstration of
the value placed on the academic side of fteen years of education.)
Many students would say that there is an element of caricature in
my description. They would agree that the lectures they attend are
incomprehensible and boring but claim that they have to come to
nd out what is going to be examined. However, even if this was
the case, they would still be behaving irrationally. The invention of
the Xerox machine means that only one student need attend each
lecture the remainder being freed for organised games, social events
and so on
a
.
a
In the past some universities made lectures compulsory. In Cambridge during
the early 19th century attendance at lectures was not compulsory but attendance
at Chapel was. The choice thundered supporters of compulsory chapel is be-
tween compulsory religion and no religion at all. The dierence replied one
opponent . . . is too subtle for my grasp.
'
&
$
%
Nor would this student need to take very extensive notes since
everything done in the lecture is better done in the textbooks.
Even the least experienced observer can see that the average
lecturer makes lots of little mistakes. Usually these are just
mis-speakings or misprints sometimes spotted by the lecturer,
sometimes vocally corrected by a wide awake member of the
audience, sometimes silently corrected by the note taker but often
passing unnoticed into students notes to puzzle or confuse them
later. The experienced observer will note that, though the general
outlines of proofs are reasonably well done, the ne detail is often
tackled ineciently or vaguely with, for example, a four line proof
where one line will do. A lecture takes place in real time, so to
speak, with 50 minutes of mathematics occupying 50 minutes of
exposition whereas a chapter of a book that takes ten minutes to
read may have taken as many days to compose.
'
&
$
%
When the author of a book encounters a problem she can stop and
think about it; the lecturer must press on regardless. If the
notation becomes too complex or it becomes clear that some
variation in an early denition would be helpful the author can go
back and change it; the lecturer is committed to her earlier choices.
When her book is nished the lecturer can reread it and revise at
leisure. She will get her friends to read the manuscript and they,
viewing it with fresh eyes, will be able to suggest corrections and
improvements. Finally, if she is wise, she will oer a graduate
student a suitable monetary reward for each error found.
'
&
$
%
Even with all these precautions, errors will still slip through, but it
is almost certain that the book will provide a clearer, simpler and
more accurate exposition than any lecture notes
a
.
Students may feel under some obligation to go to lectures; their
teachers are under no such compulsion. Yet mathematicians go to
seminars, colloquium talks, graduate courses all of which are
lectures under another name. Why, if lectures have all the
disadvantages that I have shown, do they persist in going to them?
The surprising answer is that many mathematicians nd it easier to
learn from lectures than from books. In my opinion there are
several interlinked reasons for this.
a
At one time it was the custom for beginning lecturers to spend their rst
couple of years producing a perfect set of lecture notes, in eect a book. For the
rest of their professional lives their lectures consisted of reading these notes out
at dictation speed. Their exposition was then clear, simple and accurate but, in
view the invention of printing some centuries earlier, the same result could have
been obtained more eciently.
'
&
$
%
(1) A lecture presents the mathematics as a growing thing and not
as a timeless snapshot. We learn more by watching a house being
built than by inspecting it afterwards.
(2) As I said above, the mathematics of lecture is composed in real
time. If the mathematics is hard the lecturer and, therefore, her
audience are compelled to go slowly but they can speed past the
easy parts. In a book the mathematics, whether hard or easy, slips
by at the the same steady pace.
(3) Some lecturers are too shy, some too panic stricken and a few
(but very few) too vain or too lazy to respond to the mood of the
audience. Most lecturers can sense when an audience is puzzled
and respond by giving a new explanation or illustration. When a
lecture is going well they can seize the moment to push the
audience just a little further than they could normally expect to go.
A book can not respond to our moods.
'
&
$
%
(4) The author of a book can seldom resist the temptation to add
just one extra point. (Why should she, when purchasers and
publishers prefer to deal in proper books rather than slim
pamphlets?) The lecturer is forced by the lecture format to
concentrate on the essentials.
(5) In a book the author is on her best behaviour; remarks which
go down well in lectures look at on the printed page. A lecturer
can say This is boring but necessary or It took me three days to
work this out in a way an author cannot.
There is another advantage of lectures which is of particular
importance to beginners. There is a slogan We learn mathematics
by doing mathematics which like many slogans conceals one truth
behind another. We do not learn to play the violin by playing the
violin or rock climbing by climbing rocks. We learn by watching
experts doing these things and then imitating them.
'
&
$
%
Practice is an essential part of learning but unguided practice is
generally useless and often worse than useless. People who teach
themselves to program acquire a mass of bad programming habits
which (unless they wish to remain hackers all their lives) they then
have to painfully unlearn. Mathematics textbooks show us how
mathematicians write mathematics (admittedly an important skill
to acquire) but lectures show us how mathematicians do
mathematics.
'
&
$
%
In his book Science Awakening Van Der Waerden makes the
following suggestive remarks about the decline of the ancient Greek
mathematical tradition.
Reading a proof in Apollonius requires extended and
concentrated study. Instead of a concise algebraic formula,
one nds a long sentence, in which each line segment is
indicated by two letters which have to be located in the
gure. To understand the line of thought one is compelled
to transcribe these sentences in modern concise formulas.
The ancients did not have this tool; instead they had the
oral tradition.
An oral tradition makes it possible to indicate the line
segments with the ngers; one can emphasise essentials and
point out how the proof was found. All of this disappears
in the written formulation of the strictly classical style.
The proofs are logically sound, but they are not suggestive.
'
&
$
%
One feels caught in a logical mousetrap, but one fails to
see the guiding line of thought.
As long as there was no interruption, as long as each
generation could hand over its method to the next,
everything went well and the science ourished. But as
soon as some external cause brought about an interruption
in the oral tradition, and only books remained it became
extremely dicult to assimilate the work of the great
precursors and next to impossible to pass beyond it.
'
&
$
%
In my view students should treat lectures not as a note taking
exercise but as a dialogue between themselves and the lecturer.
They should try to follow the argument as it emerges and not just
take it down blindly. But the reader will exclaim this is an
impossible and futile council of perfection and, after having thrown
these notes into the nearest available wastepaper basket, she may
well resolve her indignation into a series of questions.
'
&
$
%
What about note taking? If you look at experienced
mathematicians in a lecture you will see that their note taking is an
automatic process which leaves them free to concentrate on the
lecture. Most mathematics lecturers follow two conventions which
make automatic, or at least semi-automatic, note taking possible
(a) Everything that is written on the blackboard is to be copied
down and nothing that is spoken need be taken down.
(b) It is the responsibility of the lecturer to ensure that what
appears on the board forms a decent set of notes without further
editing.
Semi-automatic note taking is a skill that has to be learnt, but it
seems to be an easy one to acquire.
Would it better not to take notes? Some mathematicians
never take notes but most nd that note taking helps them
concentrate on the job in hand.
'
&
$
%
(When the audience at a seminar stop taking notes the experienced
seminar speaker knows that they have lost interest and are now
using her as a gently babbling source of white noise whilst they
think their own thoughts.) Further even the largest blackboard will
eventually be erased and notes allow you to glance back to earlier
parts of the lecture.
What should you do if you get lost? The rst and most
important thing is to remember that most mathematicians are lost
most of the time during lectures. (If you do not believe me, ask
around.) Attending a mathematics lecture is like walking through a
thunderstorm at night. Most of the time you are lost, wet and
miserable but at rare intervals there is a ash of lightening and the
whole countryside is lit up. Once you realise that your plight is
neither an infallible sign of your incurable stupidity nor a clear
indication of the lecturers total incompetence but simply a normal
occurrence, it is clear how you should act.
'
&
$
%
You should continue taking notes watching all the time for a point
where the lecturer changes the subject (or nishes a proof or
whatever) and you can rejoin her exposition as an active partner.
It is obvious that if you study your lecture notes after the lecture
with the object of understanding the point where the
lecturer has got to you will have a better chance of
understanding the next lecture. If you are one of the majority of
the students who nd this a counsel of perfection then you could at
least use the ve minutes before the next lecture rereading the last
part of your notes. (If you do not do even do this, at least ask
yourself why you do not do this.)
What should you do if you understand nothing at all of
what is going on? At an advanced level it is possible for an entire
course of 24 lectures to be devoted to the proof of a single theorem.
'
&
$
%
If you get really lost in such a course (and probably by the end
everybody except, perhaps, the lecturer will be really lost) you stay
lost. However rst and second year undergraduate lectures consist
of a set of short topics chained together in some reasonable order.
Even if you completely fail to understand one topic there is no
reason why you should not understand the next (even if you do not
understand the proof of Cauchys theorem you can still use it). On
the other hand if incomprehensible topic succeeds incomprehensible
topic then taking notes in the hope that all will become clear when
you revise is not an adequate response. You should swallow your
pride and consult your director of studies.
What about questions? There are three types of questions that
an audience can ask.
(a) Questions of Correction If you think the lecturer has
missed out a minus sign or written when she meant then you
should always ask.
'
&
$
%
No lecturer likes to spend a blackboard of calculations sinking
further into the mire because her audience has failed to point out
an error on line one. Sometimes very polite students wait until
after a lecture to point out errors with the result that the lecturer
knows that she has made an error but that she cannot correct it.
So the rule is ask and ask at once.
(b) Questions of Incomprehension It takes considerable
courage to admit that you do not understand something in front of
other people. However if you do not understand something it is
likely that many others in the audience will be in the same boat
and you will have their silent thanks.
'
&
$
%
You will usually also have the audible and honest thanks of the
lecturer since, as I have indicated above, most lecturers prefer to
keep in touch with the audience
a
. (There is a small and
unfortunate minority who would prefer to lecture to an empty
room, but give your lecturer the benet of the doubt and ask.)
(c) Questions of Extension If you are in the happy position of
understanding everything the lecturer says then you may wish her
to go further into a topic. Your modest request to hear more about
the general case is unlikely to go down well with the rest of the
audience who are still struggling with the particular case.
a
I have often thought that the technology of the TV game-show should be
adapted to the lecture theatre. Each seat would have a concealed button which
the auditors could press when they wanted the lecturer to slow down. The votes
could be added and the result shown on a dial visible only to the lecturer who
would then be in the position of a motorist trying to keep to the speed limit.
'
&
$
%
Such questions should be left until after the lecture when the
lecturer will be happy to oblige (few mathematicians can resist an
invitation to talk more about their subject).
'
&
$
%
If you nd yourself asking more than one question per lecture,
examine your motives.
It is noticeable that at seminars it is often the most distinguished
mathematicians who ask the simplest (if they were not so
distinguished, one might say naive) questions. It is, I suppose,
possible that they only began to ask such questions after they
became distinguished, but I believe that a willingness to ask when
they do not know is a characteristic of many great minds
a
.
a
Though there is no unique recipe for greatness. When the very great physicist
Bohr was visiting the great physicist Landau in Moscow he was invited to give
a talk to the graduate students with Landau translating. Bohr concluded his
talk with the assertion I attribute my success to the fact that I have never been
afraid to let my students tell me what a fool I am. The Russian translation
ended I attribute my success to the fact that I have never been afraid to tell my
students what fools they are.
'
&
$
%
Mathematical sayings tend to have multiple attributions (perhaps
because mathematicians remember processes rather than isolated
facts like names). The ancient Greeks attributed the following
saying to Euclid among others. Ptolomey, King of Egypt, asked
Euclid to teach him geometry. O King replied Euclid in Egypt
there are royal roads and roads for the common people, but there
are no royal roads in geometry. Mathematics is hard, there are no
easy ways to understanding but the lecture, properly used, is the
easiest way that I know.
'
&
$
%
A.2 Wiles Proof
The following is an excerpt from an extensive discussion of the
history of the Theorem and attempts to prove it; it can be found
on http://www.vertigo.co.uk/fermat/book10.htm
Figure A.1: Pierre de Fermat
'
&
$
%
I have discovered a truly marvellous proof, which this
margin is too narrow to contain . . . With these words the
seventeenth-century French mathematician Pierre de
Fermat threw down the gauntlet to future generations.
Fermats Last Theorem looked simple enough for a child to
solve, yet the nest mathematical minds would be baed
by the search for the proof.
Over three hundred and fty years were to pass before
a mild-mannered Englishman nally cracked the mystery
in 1995. Fermat by then was far more than a theorem.
Whole lives had been devoted to the quest for a solution.
There was the nineteenth century mathematician
Sophie Germain, who had to take on the identity of a man
to conduct her research in a eld forbidden to females.
'
&
$
%
The dashing Evariste Galois scribbled down the results
of his research deep into the night before sauntering out to
die in a duel. The Japanese genius Yutaka Taniyama killed
himself in despair, while the German industrialist Paul
Wolfskehl claimed Fermat had saved him from suicide.
'
&
$
%
Figure A.2: Andrew Wiles
Andrew Wiles had dreamed of proving Fermat ever
since he rst read about the theorem as a boy of ten in his
local library. Whilst the hopes of others had been dashed,
his dream was destined to come true but only after
years of toil and frustration, of exhilarating breakthrough
'
&
$
%
and crashing disappointment. The true story of how
mathematics most challenging problem was made to yield
up its secrets is a thrilling tale of endurance, ingenuity and
inspiration.
To succeed Wiles required enormous determination to
overcome the periods of self-doubt. He describes his
experience of doing mathematics in terms of a journey
through a dark unexplored mansion: You enter the rst
room of the mansion and its completely dark. You stumble
around bumping into the furniture but gradually you learn
where each piece of furniture is. Finally, after six months or
so, you nd the light switch, you turn it on, and suddenly
its all illuminated. You can see exactly where you were.
Then you move into the next room and spend another six
months in the dark. So each of these breakthroughs, while
sometimes theyre momentary, sometimes over a period of
'
&
$
%
a day or two, they are the culmination of , and couldnt
exist without, the many months of stumbling around in the
dark that proceed them.
In 1993, Wiles returned to Cambridge to announce his
proof. Headlines around the world declared that the Last
Theorem had been solved, but at this point the proof had
not been checked. It turned out that there was a aw in
Wiles argument, and the proof crashed to the ground.
Wiles immediately locked himself away again, trying to
x the error. The mistake seemed to become harder and
harder to overcome as the months passed. Eventually he
invited a former student, Richard Taylor, to work with
him, but still there seemed to be no progress.
On September 19th 1994, Wiles made the crucial
breakthrough: I was sitting at my desk one Monday
morning, when suddenly, totally unexpectedly, I had this
'
&
$
%
incredible revelation. It was so indescribably beautiful, it
was so simple and so elegant. I couldnt understand how
Id missed it and I just stared at it in disbelief for twenty
minutes. Then during the day I walked around the
department, and Id keep coming back to my desk looking
to see if it was still there. It was still there. I couldnt
contain myself, I was so excited. It was the most important
moment of my working life. Nothing I ever do again will
mean as much.

Slides

Uploaded by

Copyright:

Available Formats

Slides

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Slides

Uploaded by

Copyright:

Available Formats

Course Notes

) and simplify them where

B). Can we draw any conclusions?

(x) is true, as required.

(where n is an integer) are prime. Express the conjecture as

Q). So a proof consists in showing that

Q) T. This is equivalent to showing that (P Q

. (We use the symbol QQ Q to refer to the

which contains X).

in eect we assume that

. Let X be the set of positive integers n for

. We know that X is not the

(x) where p(x) is any

(say). We therefore have two

we can create a general solution

. We can choose the constants A, B so that the correct

. The original invocation together with the invocation

+ 1. As n is even, we can replace

comparisons are needed.

You might also like