Chapter 1

Mathematical Language and Proof

We begin this chapter looking at some sequences and an example showing why proofs are so
necessary, and follow up with an example of a proof – of one of the most famous theorems of
all time. We move on to a discussion of how to make our statements more precise, looking at
mathematical notation for and, or, not and implies. You will learn what is meant by the
contrapositive, converse and negation of a statement, and how to write these down. We
also define the symbols ∀ (for all) and ∃ (there exists). Equipped with these new concepts,
we then begin to look at how proofs can be constructed, and introduce some methods of proof.

1.1 1,2,3 . . .
Sequences of numbers can arise in all sorts of ways – sometimes the same sequence crops up in
many different areas of mathematics. In each of the following questions, you are asked to work
out the first few terms of a sequence and then make a conjecture about what you think the nth
term is. (Here n will always be a positive integer.)

Exercise 1.1 Look at the grid below. Imagine you have to travel from point O to one of the
points P1 , P2 , . . . on the top line. You are only allowed to travel along grid lines and you are
only interested in ‘shortest paths’.
�
���
P2 P3 P4 P5
P1
�� ��
�� � � �
����
��
O
For example, in the diagram below the left-hand shows a correct shortest path to P4 , and the
right hand picture shows a path that is not as short as possible, so we do not allow it.
�
���
��
P4 �� �
�� P4
�� ����
��
O
�
O
yes no
Let an be the number of different shortest paths to Pn . Then for example a1 = 1 and a2 = 2.
Find a3 and a4 . What do you think an is, in general?

Exercise 1.2 Imagine you are in charge of painting a block of flats. Town planning regulations
(bizarrely!) state that each level must be painted either black or white, and you can only paint
a level white if it has a black level immediately below it.
4 Proof & Structure Chapter 1: Mathematical Language and Proof

Below are two legal ways and one illegal way of painting a 4-storey block.

legal legal illegal

Let bn be the number of legal ways of painting an n-storey block of flats. Find b1 , b2 and b3 .
How would you find bn in general?

Exercise 1.3 You have a chocolate bar with n + 1 cubes. You wish to break it into individual
cubes. You may only break along the lines, and one ‘move’ consists of breaking one piece along
one straight line. The example below shows one way of breaking up a four-cube bar.

move 1 move 2 move 3

Let cn be the smallest number of moves required to break up an (n + 1)-cube chocolate bar.
(So the illustration above shows that c3 ≤ 3.) Make a conjecture for cn .

Exercise 1.4 This question is about partitions. A partition of a positive integer is a way of
splitting it up into a sum of positive integers. So one partition of 7 is just 7, but you could also
have 4 + 3 or 5 + 2. Note that we count, say, 4 + 3 and 3 + 4 as the same partition, it is only
the numbers that matter, not the order. Let pn be the number of partitions of n. Go forth and
conjecture!

Exercise 1.5 Finally in this section, coins. Imagine it’s the old days and we have such things
as threepenny bits. You have a stock of 1p, 2p and 3p coins. Let qn be the number of ways
you can make n pence. So for example 4p could be made using a 3p and a 1p coin, or two 2p
coins, and there are other ways. Investigate.

1.2 Why bother with proof ?

Example 1.2.1 Let n be an integer (with n ≥ 1). Draw n points on the circumference of a
circle and join every pair of points with a straight line. What is the greatest number of regions
into which the circle can be divided? The answer isn’t obvious, so let’s try some examples.

n 1 2 3 4 5
Regions 1 2 4 8 16

What do you think the answer is for n = 6? What do you think the answer is in general? Make
a conjecture before you read on!
1.2 Why bother with proof? Proof & Structure 5

In fact, however you place 6 points on the circle, you can never create more than 31 regions.
(For 7 and 8 the answers are 57 and 99.) So your conjecture was (probably) wrong. The actual
answer, and a proof of it, are in Appendix 1 (available to download from the module website).
The moral of the story is that you should never believe something until it has been proved.

A word of warning/comfort: this question and Exercises 1.1 – 1.5 are more open ended than
the typical exam question. Do play around with these questions though; I’ll discuss them in
the worked solutions. But don’t worry if you can’t completely solve all of them – for one of
these sequences there is no known formula!

So what is a proof? It is a sequence of deductions in which each statement follows logically from
the last. The first statement is what we assume to be true; it is called the hypothesis. The
final statement is what we want to deduce, and is called the conclusion. The steps in-between
should be detailed enough to convince a reader that the argument is valid. As an illustration
of this, let’s consider the following well known result.

Theorem 1.2.2 (Pythagoras) In a right-angled triangle, the square of the hypotenuse is the
sum of the squares of the other two sides.

Alternatively: If ABC is a triangle with ∠ABC = 90◦ , then AC 2 = AB 2 + BC 2 . Here the

hypothesis is ABC is a triangle with ∠ABC = 90◦ and the conclusion is AC 2 = AB 2 + BC 2 .

In general, when a theorem is given in the form ‘if p, then q’, then p is the hypothesis and q is
the conclusion.

Proof Let a = AB, b = BC and c = AC. We have to show that c2 = a2 + b2 .

Consider a square with sides of length a + b. We can fit four copies of the triangle ABC into
the square, one at each corner, as in the diagram:

b a

x
a c c b
C

b c
b c c a

B a A a b

The quadrilateral inside has all its sides of length c. In addition, its angles are all right-angles.
To see this, remember that angles in a triangle add up to 180◦ and angles on a straight line
add up to 180◦ . Therefore

x + ∠BCA + ∠BAC = 180◦ = 90◦ + ∠BCA + ∠BAC

giving x = 90◦ .
6 Proof & Structure Chapter 1: Mathematical Language and Proof

Hence the inner quadrilateral is a square of side c. We can now work out the area S of the
outer square in two different ways. Firstly the area is just the square of the length of its sides.
Thus
S = (a + b)2 = a2 + 2ab + b2 .
Alternatively, the area of the square is the area of the inner square (with side c) plus four times
the area of ABC. Thus
S = c2 + 4 × ( 12 ab) = c2 + 2ab.
Combining the two expressions for S gives c2 + 2ab = a2 + 2ab + b2 or, equivalently, c2 = a2 + b2 .
This is what we wanted to prove, and so we are finished. We write the symbol □ to denote the
end of a proof. □

Commentary That all seems very neat! But how did anyone come up with it? It seems to
come from nowhere. That is because we are presented with a fait accompli – we don’t see the
various attempts at proof, the ones that don’t work, the ones that work but are untidy, and so
on. However, when the final proof is presented most of this work ends up being thrown out.
In this module we will present many proofs; often we will also discuss where the idea for the
proof came from. That is, we will spend some time looking through the mathematician’s waste
paper bin.

1.3 Statements and Theorems

In the mathematical sense, a “statement” (or “proposition”) is a sentence which makes an as-
sertion: a given statement is true or false, but not both. Here are ten examples of statements.

S1 2 + 2 = 4;
S2 51 is prime;
S3 The square of an even integer is divisible by 4;
S4 The sum of two odd integers is even;
S5 x2 − 3x > 0;
S6 If x > 1, then x2 − 12x + 35 > 0;
S7 If 2n − 1 is prime, then n is prime;
S8 Any even integer greater than 2 can be expressed as the sum of two primes;
√
S9 2 is irrational;
S10 The number of shortest paths to Pn (see Exercise 1.1) is n.
Something like ‘3 + 7’ is not a statement – no assertion is made, so it can’t be said to be true
or false.
Note that the truth or falsity of S5 depends on the value of x. As soon as we give a value to x
the statement becomes true or false. Statements for which the truth depends on the value of a
variable or variables are called predicates. Of the above only S5 is a predicate. Of the others
S1, S3, S4, S7, S9 and S10 are true, the truth of S8 is not known (but it is certainly either
true or false) and S2 and S6 are false.
1.4 Definitions Proof & Structure 7

Statements which are always true are called theorems 1 (of course we can’t know they are always
true until we’ve proved it). Mathematicians also use other words for certain types of theorems:
a proposition is a result which is not considered significant enough to be called a theorem;
a lemma is usually a rather technical result often required in the proof of a more important
theorem; and a corollary is a result that follows as a consequence of another theorem. A
related issue is that of a conjecture. This is a statement that is thought to be true but
for which there is no known proof. For example, statement S8 is a conjecture and is called
Goldbach’s conjecture.

1.4 Definitions
Consider statements S1 – S10 given in Section 1.3. Before we can decide whether any of
them is true we need to know the meanings of certain terms. In particular, for S3 we need
to know what it means for an integer to be even. There are various ways to give the meaning
of ‘even’. We might say that an integer is even if there is no remainder when we divide by 2.
Alternatively we could say that an integer is even if it is a multiple of 2. These are both valid
definitions. However, when defining a term it is worthwhile taking a little care to make sure
that the definition is easy to work with. In this case the two definitions given for ‘even’ do not
lend themselves to easy algebraic manipulation. The following definition is easier to work with.

Definition 1.4.1 Let m be an integer. Then m is even if there is an integer n such that
m = 2n.

Technical note: There is a problem with this definition. To see this observe that the definition
can be rephrased as: if m is an integer and there is an integer n such that m = 2n, then m is
even. From this it is clear that 0, ±2, ±4, . . . are all even, but it does not tell us anything about
the other integers like 3, -7, 21 and so on. The problem can be resolved if we use the phrase
‘if and only if’ instead of ‘if’ in the original definition. In practice mathematicians do not do
this – instead we have the convention that we always treat the if in a definition as an if
and only if. With this in mind we now conclude this section with some further definitions
required in the rest of this chapter.

Definition 1.4.2 Let m be an integer. Then m is odd if there is an integer n such that
m = 2n + 1.

Definition 1.4.3 Let m and n be integers. Then m divides n if there is an integer q such that
n = mq. If m divides n then we say m is a factor or a divisor of n and that n is divisible
by, or a multiple of, m.

Definition 1.4.4 A positive integer p is prime if p ̸= 1 and the only positive divisors of p are
1 and p. A positive integer greater than 1 which is not prime is called composite.

Example 1.4.5 The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.
1
Actually, the concepts of “truth” and theorems are not synonymous. The two concepts have had a rocky
relationship, which is further explained in the biography of Gödel at the end of the chapter. For this module,
however, true statements and theorems will be thought of as the same concept.
8 Proof & Structure Chapter 1: Mathematical Language and Proof

Exercise 1.6 Show that if p is a prime number with p ≥ 5, then either there exists an integer
n such that p = 6n + 1, or there exists an integer n such that p = 6n + 5. [Hint: you may
assume that any integer is of the form 6n, 6n+1, 6n+2, 6n+3, 6n+4, or 6n+5 for some n. The
fact, however, is a consequence of Theorem 2.1.3. But some of these forms can be factorised.]

Definition 1.4.6 A real number x is rational if there are integers m and n with n ̸= 0 such
that x = m
n
.

Note that all integers are rational since for any integer n we have n = n1 .

The previous definition relies on the notion of a real number. Although we have not defined
such numbers, we can think of a real number as an infinite decimal r0 .r1 r2 r3 . . . where each
ri is an integer and 0 ≤ ri ≤ 9 for i ≥ 1. A real number which is not rational is called irrational.

We have now introduced several sets of numbers, each of which has a mathematical symbol.
These symbols are listed below.

N: the natural numbers 0, 1, 2, 3, . . .;

Z: the integers . . . , −2, −1, 0, 1, 2, 3, . . .;
Z+ : the positive integers 1, 2, 3, 4, . . .;
Q: the rational numbers;
R: the real numbers.

1.5 Some Grammar

In spoken and written English the meaning of particular words can vary depending on context.
In mathematics we have to be more precise about what certain words mean. In this section we
consider some such words.

In what follows, we denote statements by letters p, q and so forth.

not If p is a statement, then not p, denoted ¬p, is a statement which is false when p is true
and true when p is false. So if p is the statement ‘2+2=5’, then ¬p is the statement ‘2 + 2 ̸= 5’.
If we represent true with a T and false with an F then we can express this information in a
so-called truth table, as follows:

p ¬p
T F
F T

The statement ¬p is also called the negation of p. Sometimes

√ the negation of statements√is
easy to spot. For example, the negation
√ of statement S9 ( 2 is irrational) given earlier is ‘ 2
is not irrational’ or more simply ‘ 2 is rational’. However, the negation of other statements
can be difficult and we require more grammar before we can do this with confidence.

Exercise 1.7 Write out the negation of each of the statements S1–S10 given earlier (don’t
worry if you find some of them difficult – we’ll acquire tools to make this easier in coming
sections).
1.5 Some Grammar Proof & Structure 9

Note that the statement ¬(¬p) (‘not not p’) has the same truth values as p. We say that
¬(¬p) is equivalent to p. In this sense mathematical grammar is much stricter than linguistic
grammar. For example compare ‘I am happy’ with ‘I am not unhappy’, and ‘they are friendly’
with ‘they are not unfriendly’. They do not have quite the same meanings.

and If p and q are statements, then the statement p and q, denoted by p ∧ q, is true if both
p and q are true, and false otherwise. The truth table for p ∧ q is:

p q p∧q
T T T
T F F
F T F
F F F

or The word ‘or’ in English can have two uses. Consider the following two situations:

• You have just won first prize in a TV game show. The host of the show says that you
can take the car or £20,000. Given this choice he would not expect you to take both!

• The manager of a company says that the ideal candidate for a job would be either a
mathematician or a Birkbeck student. Presumably she would not object to a candidate
who was a Birkbeck mathematics student.

In the first instance the word or is being used exclusively (you cannot take both prizes) and in
the second instance the word is being used inclusively (having both of the required attributes
does not stop you being a candidate for the job). When used linguistically it is usually clear
from the context whether the word or is inclusive or exclusive. In mathematics such ambiguity
is not desirable, so we have the convention that the word or is always used inclusively.

Therefore, if p and q are statements, then the statement p or q, denoted by p ∨ q, is true

whenever p is true or q is true (or both), and is false only when both p and q are false. The
truth table for p ∨ q is as follows.

p q p∨q
T T T
T F T
F T T
F F F

if . . ., then Consider the following statements of the form if p, then q.

• (At the local supermarket) ‘If you’re trying to eat healthily, then we’ve hundreds of low-fat
products.’

• ’If you leave your umbrella at home, then it will rain.’

• ‘If it’s raining, then it’s cloudy.’

10 Proof & Structure Chapter 1: Mathematical Language and Proof

In the first statement, the shop has hundreds of low-fat products whether or not you’re trying
to eat healthily. So, assuming the second part is true, the truth value of the first part ‘you’re
trying to eat healthily’ is irrelevant – the whole if/then statement is still true. The only time
the if/then statement is false is if you are trying to eat healthily, and you discover that the
shop doesn’t have hundreds of low-fat products. That is, when the first part is true and the
second part is false.

Let’s look at the second statement, ‘if you leave your umbrella at home, then it will rain’. When
is this false? In other words, when have I lied? There are four possibilities to consider. First
suppose that you leave your umbrella at home, and it rains. Then there’s no reason to call me
a liar; what I said would happen, happened. What if you leave your umbrella at home and it
doesn’t rain? Then my statement would definitely be false.

Now suppose you take your umbrella with you. Whether it rains or not, my statement makes no
predictions about this event, so you cannot say that the statement is false in this case. Again,
the only time the statement is false is when the first part is true and the second part is false.

In the third statement, again we see the statement says nothing about what happens if it is
not raining. If it is not raining, then it may or may not be cloudy, and the statement will be
true in either case. The statement only makes a claim about what happens if it is raining. The
only way the statement is false is if it is raining outside, but it is not cloudy.

In a mathematical context, if p and q are statements, then the statement if p, then q, denoted
by p ⇒ q, is false when p is true and q is false, and true otherwise. The truth table is given
below.
p q p⇒q
T T T
T F F
F T T
F F T

There are other ways of expressing ‘if p, then q’. The ones you are most likely to come across
are: p implies q; p only if q; p is sufficient for q; q is necessary for p; q ⇐ p.

Given the mathematical definition of ‘if . . ., then’, try the following exercise:

Exercise 1.8 Which, if any, of the following statements (a) – (d) are true?
(a) If 17 is prime, then 5 does not divide 17.
(b) If 17 is prime, then 5 does not divide 15.
(c) If 15 is prime, then 5 does not divide 17.
(d) If 15 is prime, then 5 does not divide 15.

The symbols ¬, ∧, ∨ and ⇒ are called connectives. We can use them to combine statements
to make more complicated statements. The truth values of these new statements can be worked
out using truth tables.

Example 1.5.1 The truth table for (p ∨ q) ∧ p is:

1.6 Tautologies and Equivalent Statements Proof & Structure 11

p q p∨q (p ∨ q) ∧ p
T T T T
T F T T
F T T F
F F F F

Exercise 1.9 Let p and q be statements. Consider the statement (p ∧ q) ⇒ p. When would
you expect this statement to be true? Construct the truth table for (p ∧ q) ⇒ p. Do the
resulting truth values agree with your expectation.

if and only if If p and q are statements, then p if and only if q, denoted by p ⇐⇒ q, is

true when p and q have the same truth values and false otherwise. The truth table for p ⇐⇒ q
is given below. Note that often ‘if and only if’ is abbreviated to iff. It may not be surprising
that ’p if and only if q’ is actually the same as ’p implies q and q implies p’ (see previous page
on ’if p, then q’).

p q p ⇐⇒ q
T T T
T F F
F T F
F F T

1.6 Tautologies and Equivalent Statements

A tautology is a statement which is always true. For example, for any statement p the
statement p ∨ ¬p is a tautology. For more involved statements we can check whether they are
tautologies using truth tables.

Example 1.6.1 The statement (p ∧ q) ⇒ (p ∨ q) is a tautology. We can verify this from the
following truth table.

p q p∧q p∨q (p ∧ q) ⇒ (p ∨ q)
T T T T T
T F F T T
F T F T T
F F F F T

Since the truth value in the last column is always T , it follows that (p ∧ q) ⇒ (p ∨ q) is a
tautology.

Exercise 1.10 Let p and q be statements. Use truth tables to show that the statements
p ⇒ (p ∨ q) and ((p ⇒ q) ∧ ¬q) ⇒ ¬p are tautologies.

Two statements p and q are equivalent if they always have the same truth values. As we
noted earlier p and ¬(¬p) are equivalent for any statement p. If p and q are equivalent, then
p ⇐⇒ q is a tautology and vice versa.

Again we can use truth tables to verify that two statements are equivalent, as the following
two examples illustrate.
12 Proof & Structure Chapter 1: Mathematical Language and Proof

Example 1.6.2 Let p and q be statements. We will show that p ⇒ q is equivalent to ¬p ∨ q.

To do this we construct the following truth table.

p q p⇒q ¬p ¬p ∨ q
T T T F T
T F F F F
F T T T T
F F T T T

Since the truth values in the third and fifth columns are the same, the two statements are
equivalent.

Example 1.6.3 Let p and q be statements. We will show that ¬(p∧q) is equivalent to ¬p∨¬q.
To do this we construct the following truth table.

p q p∧q ¬(p ∧ q) ¬p ¬q ¬p ∨ ¬q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

Since the truth values in the fourth and seventh columns are the same, the two statements are
equivalent.

Exercise 1.11 Let p and q be statements. Use a truth table to show that ¬(p ∨ q) and
¬p ∧ ¬q are equivalent. (The equivalence of the statements given here and the equivalence of
the statements given in Example 1.6.3 are collectively known as de Morgan’s Laws).

Exercise 1.12 Let p and q be statements. Use a truth table to show that p ⇒ q is equivalent
to ¬q ⇒ ¬p.

The statement ¬q ⇒ ¬p is called the contrapositive of the statement p ⇒ q. Their equivalence

provides us with a useful method of proof. Suppose we want to prove if p, then q. One possible
approach would be to prove if ¬q, then ¬p. Having completed the proof it follows, since
p ⇒ q and ¬q ⇒ ¬p are equivalent, that if p, then q is true. This type of proof is called a
contrapositive proof.

Exercise 1.13 Let p and q be statements. Use Example 1.6.2 along with de Morgan’s laws
and the equivalence of p and ¬(¬p) to show that ¬(p ⇒ q) is equivalent to p ∧ ¬q. With the
equivalence of these two statements in mind, reconsider your answers to Exercise 1.7.

Exercise 1.14 So far we have only given examples of truth tables for statements constructed
from one or two statements. How many rows would be needed for the truth table of a statement
constructed from (a) three statements? (b) four statements?
Use a truth table to show that, for statements p, q and r, the statements p ∨ (q ∧ r) and
(p ∨ q) ∧ (p ∨ r) are equivalent.

We will now show how we can use the theoretical work we have done so far to restate some
mathematical statements in a different, but equivalent form. This sometimes helps as it can be
easier to see whether a particular statement is true when it is in one of these restated forms.
1.7 Some Proofs Proof & Structure 13

Example 1.6.4 Consider the statement S7: ‘if 2n − 1 is prime, then n is prime’. This is
difficult to get a handle on when trying to prove, because we really don’t know much about
prime numbers, except that they don’t have many factors. Composite numbers (non-primes)
are easier; we can straight away say ‘OK, if n is composite, then it has some factorisation
n = ab with neither of a or b equal to 1’. So we’d ideally like to prove an equivalent statement
in terms of numbers not being prime. Now, the statement is in the form p ⇒ q, where p is the
statement ‘2n − 1 is prime’ and q is the statement ‘n is prime’. By Example 1.6.2, p ⇒ q is
equivalent to ¬p ∨ q. Here ¬p is the statement ‘2n − 1 is not prime’, or ‘2n − 1 is composite or
equal to 1’. Thus statement S7 is equivalent to: ‘either 2n − 1 is not prime or n is prime’.

Alternatively, by Exercise 1.12, p ⇒ q is also equivalent to its contrapositive, ¬q ⇒ ¬p. Here

¬q is the statement ‘n is not prime’. Thus statement S7 is equivalent to: ‘if n is not prime, then
2n − 1 is not prime’. In this form we at least have some hope that we could use a factorisation
of n to produce a factorisation of 2n − 1. We’ll do this in the next section.

Example 1.6.5 Consider the statement ‘if x > 0 and x < 1 then x2 < x’. This statement
is of the form p ⇒ q where p is the statement ‘x > 0 and x < 1’ and q is the statement
‘x2 < x’. The statement is equivalent to two other statements, the either/or form ¬p ∨ q and
the contrapositive form ¬q ⇒ ¬p. To work with these we need to know ¬p and ¬q. Here
the statement p is of the form p1 ∧ p2 where p1 is ‘x > 0’ and p2 is x < 1. By de Morgan’s
Laws, ¬p is equivalent to ¬p1 ∨ ¬p2 . Hence ¬p is the statement ‘either x ≤ 0 or x ≥ 1’. So the
given statement is equivalent to ¬p∨q, which is the statement: ‘either x ≤ 0 or x ≥ 1, or x2 < x’.

Alternatively, the given statement is equivalent to its contrapositive ¬q ⇒ ¬p, which is the
statement: ‘if x2 ≥ x, then either x ≤ 0 or x ≥ 1’.

Exercise 1.15 For each of the following statements (a) – (d), find equivalent statements in

• the either/or form;

• the contrapositive form.

(a) If n2 is odd, then n is odd.

(b) If x2 = 2, then x is irrational.
(c) If x > y and y > z, then y 2 > xz.
(d) If x + y is irrational, then either x is irrational or y is irrational.

Which, if any, of the statements do you think are true?

1.7 Some Proofs

Example 1.7.1 The square of an even integer is even.

Commentary This is the same as saying: if n is even, then n2 is even. So we have to show
that n2 = 2m for some integer m. All we know is that n is even, which means that n = 2k for
some integer k. So n2 = (2k)2 = 4k 2 = 2(2k 2 ), and this provides our m. This is the basis for
the following proof.
14 Proof & Structure Chapter 1: Mathematical Language and Proof

Proof Let n be an even integer. Then there exists an integer k such that n = 2k. Thus

n2 = (2k)2 = 4k 2 = 2(2k 2 ).

Now, since k is an integer, clearly 2k 2 is an integer. Thus n2 = 2m for some integer m. That
is, n2 is even. □

Remember, if in doubt, write down all the appropriate definitions and see if you can work from
there.

Exercise 1.16 Prove that the square of an odd integer is odd.

Example 1.7.2 The sum of two odd integers is even.

Proof Let m and n be odd integers. Then there are integers k and l such that m = 2k + 1
and n = 2l + 1. Thus

m + n = 2k + 1 + 2l + 1 = 2k + 2l + 2 = 2(k + l + 1).

Now, since k and l are integers, it follows that k + l + 1 is an integer. That is, m + n is even. □

Note Do not make the mistake of using the same letter for k and l.

Exercise 1.17 Prove that if m and n are multiples of r then m + n is a multiple of r and mn
is a multiple of r2 .

Example 1.7.3 Let n be a positive integer. If 2n − 1 is prime, then n is prime.

Commentary As we said in the last section, our attack on this proof will be to try and prove
the contrapositive statement, that if n is not prime, then 2n − 1 is not prime. If n is not prime,
then either n = 1 or n is composite. If n = 1, then 2n − 1 = 1 is not prime, so the statement is
true for n = 1. So assume n is composite. We first write down the definition: n is composite
means that n = ab for some integers a, b with neither a nor b equal to 1. Thus 2n − 1 = 2ab − 1.
We have to show somehow that 2ab − 1 is composite. In other words we have to factorize 2ab − 1.
It is time to list three very useful factorisations which it is worth remembering.
For any real numbers x, y and any positive integer k we have

1. x2 − y 2 = (x + y)(x − y);

2. xk − 1 = (x − 1)(xk−1 + xk−2 + · · · x2 + x + 1); and in general

3. xk − y k = (x − y)(xk−1 + xk−2 y + xk−3 y 2 + · · · xy k−2 + y k−1 ).

We will be using the second of these in our proof.

1.7 Some Proofs Proof & Structure 15

Proof (Contrapositive) Suppose n is not prime. If n = 1, then 2n − 1 = 1 is not prime. So

suppose n > 1 is not prime. Then n is composite. So n = ab for some integers a, b with neither
a nor b equal to 1. Let x = 2a . Then

2n − 1 = 2ab − 1
= xb − 1
= (x − 1)(xb−1 + · · · + x + 1).

Now, since a, b > 1, both 2a − 1 = x − 1 > 1 and (xb−1 + · · · + x + 1) > 1. Thus 2n − 1 is the
product of two integers both of which are greater than 1. Thus 2n − 1 is composite, hence not
prime. □
n
If a number of the form 2 −1 is prime, it is called a Mersenne prime, after the French mathemati-
cian Marin Mersenne, who found many primes of this form, and claimed that, for primes less
than or equal to 257, the integer 2n − 1 is prime if and only if n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127
or 257. And this was in the 17th century! Incredibly this is very nearly true, and it wasn’t
until 1903 that the claim was refuted. It turns out that 267 − 1 is composite, but it’s hardly
surprising that poor old Mersenne didn’t spot the factors 193 707 721 and 761 838 257 287.

Exercise 1.18 Following on from Example 1.7.3, you might be wondering when expressions
like 3n − 1 and 8n − 1 are prime. We can deal with all of these cases in one go. Let n and r be
positive integers. Show that if n > 1 and r > 2, then rn − 1 is composite.

Example 1.7.4 75 311 357 is not a perfect square.

Commentary The first thing to do is put down your calculator! There are better ways to
do this, and it would be no help at all to you if the number was
75 311 222 333 444 555 666 777 888 999 357
which is also not a perfect square. It would be nice to find a proof that covered as general a
case as possible.

If we investigate the squares of a few smallish integers such as 172 = 289 and 252 = 625 we
note that the units digit of the square is just the units digit of the square of the units digit of
the original number. For example, the units digit of 172 is just the units digit of 72 . How do
we show this in general?

An integer in base 10 is of the form ar ar−1 . . . a1 a0 where, for each i, 0 ≤ ai ≤ 9 and ar ̸= 0.

This representation is just shorthand for

ar 10r + ar−1 10r−1 + · · · + a1 10 + a0 .

For example 289 = 2 · 100 + 8 · 10 + 9, so r = 2, a2 = 2, a1 = 8 and a0 = 9.

Now, since 10 is a factor of every term of this sum except for a0 we can write any positive
integer as 10n + u where n and u are non-negative integers and u is the units digit when the
integer is expressed in base 10. Thus

(10n + u)2 = 100n2 + 20nu + u2 = 10(10n2 + 2nu) + u2

16 Proof & Structure Chapter 1: Mathematical Language and Proof

and so, in base 10, the units digit of (10n + u)2 is just the units digit of u2 .

We now have enough to write out a proof of the following result.

Proposition 1.7.5 The units digit of a perfect square when expressed in base 10 is either 0,
1, 4, 5, 6 or 9.

Proof Any positive integer can be expressed in the form 10n + u where n and u are non-
negative integers and u is the units digit when the integer is expressed in base 10. Now

(10n + u)2 = 100n2 + 20nu + u2 = 10(10n2 + 2nu) + u2

and so, in base 10, the units digit of (10n + u)2 is just the units digit of u2 . Since we know
u = 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9, clearly u2 = 0, 1, 4, 9, 16, 25, 36, 49, 64 or 81. Thus the units digit
of u2 , and hence the units digit of a perfect square, is one of 0, 1, 4, 5, 6 or 9. □

Corollary 1.7.6 75 311 357 is not a perfect square.

Proof The units digit of 75 311 357 is 7. Thus by Proposition 1.7.5, 75 311 357 is not a
perfect square. □

Exercise 1.19 Prove that for any integer n, n2 + 4 is not divisible by 7. Hint: every integer
can be expressed in the form 7q + r where r is one of 0, 1, 2, 3, 4, 5 or 6. Note, in general,
for any positive integers k and n, there are unique positive integers q and r with 0 ≤ r < n
such that k = nq + r. This is proved Theorem 2.1.3 in Chapter 2 and is one of the central
theorems of the module. Notice that in the proof of Proposition 1.7.5, we also use this fact
(i.e. every integer is uniquely expressable as 10n + u), though we more readily accept this in
the case of Proposition 1.7.5 because we count in base 10. In all cases, however, these facts are
consequences of Theorem 2.1.3.

Definition 1.7.7 For a real number x the modulus of x, written |x|, is equal to x if x ≥ 0
and −x if x < 0. So |x| is giving us the size of x.

Theorem 1.7.8 The triangle inequality Let x and y be real numbers. Then |x + y| ≤
|x| + |y|.

Proof We have to consider the possibilities for |x|, |y| and |x + y|, and in each case show that
|x| + |y| − |x + y| ≥ 0. Some of these are filled in in the table below; as an exercise you should
fill in the rest.
x y x+y |x| + |y| − |x + y| ≥ 0?
≥0 ≥0 ≥0 x + y − (x + y) = 0 ✓
≥0 <0 ≥0 x + (−y) − (x + y) = −2y = 2|y| ✓
≥0 <0 <0 x + (−y) − [−(x + y)] = 2x ✓
<0 ≥0 ≥0
<0 ≥0 <0
<0 <0 <0
The completed table will show that in every case, |x + y| ≤ |x| + |y|, and so the triangle
inequality always holds. □
1.8 Converses and Counterexamples Proof & Structure 17

1.8 Converses and Counterexamples

The converse of the statement p ⇒ q is the statement q ⇒ p. It is important to note that the
truth of p ⇒ q tells us nothing about the truth of q ⇒ p. To see this consider the following
examples.
Example 1.8.1 The statement: ‘if x = 3 and y = 5, then x + y = 8’ is true. The converse of
this statement is: ‘if x + y = 8, then x = 3 and y = 5’, which is false (for example x = 2, y = 6
is another possibility).
Example 1.8.2 The converse of the true statement ‘if n is even, then n2 is even’ is ‘if n2 is
even, then n is even’. In this case the converse is true. You can prove it using a contrapositive
proof. (See Exercise 1.16.)
Note that in the previous example we have assumed that n is an integer. We could (possibly
should!) have written the statement as ‘if n is an integer and n is even, then n2 is even’. If
we did this, then it is important to note that the ‘n is an integer’ part carries through to the
conclusion. In other words, the converse would be ‘if n is an integer and n2 is even, then n is
even’; it would not be ‘if n2 is even, then n is an integer and n is even’. To avoid this possible
confusion it is often better to define first any symbols used in the statement. So we could write:
‘Let n be an integer. If n is even, then n2 is even’. This approach makes it clear that the ‘n is
an integer’ part belongs to both the hypothesis and the conclusion.
Exercise 1.20 Write out the converse of each of the statements (a) – (d) given in Exercise
1.15.
Exercise 1.21 Criticise the following piece of deduction. Geniuses always behave oddly. I
behave oddly, so I must be a genius!
Example 1.8.3 Knowing the word converse helps to describe what is wrong with the following
‘proof’ that 1 = −1:
‘1 = −1 implies (1)2 = (−1)2 implies 1 = 1. Since the last statement is true, the first statement
must have been true. Therefore 1 = −1.’
It is true that 1 = −1 does imply 1 = 1. The error comes when the ‘proof’ goes on to claim
that this means the converse statement (1 = 1 implies 1 = −1) is true. As we know, the truth
or otherwise of a statement tells us nothing about the truth of the converse. In this case the
converse is false. We can spot the error if we try to work the equations backwards. x2 = y 2
only tells us that x = ±1. So we can’t deduce that 1 = −1 (thankfully!). Of course none of
you would write a ‘proof’ like this. But do take care to avoid ‘proofs’ that start with equating
two objects you are trying to show are equal. More subtle errors than 1 = −1 can creep in if
you risk this!
Exercise 1.22 Find the errors in the following ‘proofs’.
(a) A ‘proof ’ that all numbers are equal to zero. Let x ∈ R. Suppose for a contradiction that
x = y for some y ̸= 0. Then y = x
y 2 = xy
y 2 − x2 = xy − x2
(y + x)(y − x) = x(y − x)
y+x = x
y = 0
18 Proof & Structure Chapter 1: Mathematical Language and Proof

This contradicts our earlier assertion that y ̸= 0. Hence x = 0.

(b) A ‘proof ’ that the smallest positive number is 1. Let x be the smallest positive number.
Clearly x ≤ 1. Now x2 is also positive, so by minimality of x, x2 ≥ x. Divide both sides by
(the positive number) x to get x ≥ 1. Hence x = 1. [Nice to know we never have to worry
about fractions again, isn’t it?]

The truth, or otherwise, of the converse of a statement raises the question of how we can show
that a statement is false. Now, if p ⇒ q is false, then ¬(p ⇒ q) must be true. From Exercise
1.13, ¬(p ⇒ q) is equivalent to p ∧ ¬q. Hence, to show that the statement p ⇒ q is false we just
need to give an example where p is true and q is false; that is, an example where the hypothesis
holds but the conclusion fails. Such an example is called a counterexample to the statement.

Example 1.8.4 The statement: ‘if x + y = 8, then x = 3 and y = 5’ is false since x = 2, y = 6

is a counterexample.

Example 1.8.5 The statement: ‘if n is prime, then 2n − 1 is prime’ is false. To see this put
n = 11. Then n is prime, but 2n − 1 = 211 − 1 = 2047 = 23 × 89 and so is composite.

Exercise 1.23 Find another counterexample to each of the statements in Examples 1.8.4 and
1.8.5. (Hint: 213 − 1, 217 − 1 and 219 − 1 are all prime.)

Example 1.8.6 The statement: ‘if n is prime, then n is odd’ is false. For when n = 2, then n
is prime but n is even.

Note that in Example 1.8.6, n = 2 is the only counterexample. However, one counterexample
is all that is required to show that a given statement is false.

Exercise 1.24 Give counterexamples to each of the following statements.

(a) If x2 = 9, then x = 3.
(b) If xy < 0, then x + y < 0.
(c) If n is a positive integer, then 5n2 + 5n + 1 is prime.
(d) If 6 divides mn, then 6 divides m or 6 divides n.

1.9 Quantifiers
The Existential Quantifier (there exists)

Consider the following four statements.

E1 There exists an integer n such that n2 is even.

E2 There is an integer n such that n2 = 4.
E3 For some integer n, n3 = 27.
E4 There exists an integer n such that n2 = 18.
1.9 Quantifiers Proof & Structure 19

Each of E1 – E4 has the form: There exists some integer satisfying a certain property. In
other words, if the statement is true, we can find an integer satisfying the given property. The
mathematical symbol used to represent ‘there exists’ is ∃. So E1 – E4 can be rewritten using
this symbol as follows.

E1 ∃n ∈ Z such that n2 is even.

E2 ∃n ∈ Z such that n2 = 4.
E3 ∃n ∈ Z such that n3 = 27.
E4 ∃n ∈ Z such that n2 = 18.

To prove an existence statement it is sufficient to find one object (in this case an integer) which
satisfies the given property. So E1 is true since putting n equal to any even number verifies the
statement, E2 is true since n = 2 or n = −2 verifies the statement, and E3 is true since n = 3
verifies the statement. Note that the number of examples available to illustrate an existence
statement is irrelevant; all we need to do is find one such example. Thus E1 and E3 are equally
true even though there are infinitely many integers which verify E1 and only one integer which
verifies E3.
It is not always necessary to give a specific example to prove an existence statement, as the
following example illustrates.

Example 1.9.1 Prove that ∃ a ∈ R such that a3 + 3a2 − 2a + 11 = 0.

Proof Let f (x) = x3 + 3x2 − 2x + 11. Then f (0) = 11 and f (−10) = −669. Thus the graph
y = f (x) must cross the x-axis at some point between −10 and 0. Let a be such a point. Then
f (a) = 0, that is ∃ a ∈ R such that a3 + 3a2 − 2a + 11 = 0. □

2
Note There is a direct proof of the previous example, for if a = − b +6b+60 , where b =
√3
√ 6b
3 2
1620 + 60 669, then a + 3a − 2a + 11 = 0. However, this is more difficult to show than
the above proof!

Exercise 1.25 Write each of the following statements using, where possible, the symbols ∃,
∈, R and Q and verify that they are true. [Note, for (c), that angles are measured in radians
rather than degrees.]

(a) There is a real number x such that x + π is rational.

(b) For some real number y, y 2 − y − 1 = 0.
(c) There exists a real number θ such that cos θ = θ.

The Universal Quantifier (for all)

Consider the following three statements.

A1 For all integers n, n2 ≥ 0.

A2 For every integer n, n2 is even.
A3 Any integer is divisible by 1.
20 Proof & Structure Chapter 1: Mathematical Language and Proof

Each of A1 – A3 has the form: For all integers a certain property is true. In other words, if
the statement is true, then every integer must satisfy the given property. The mathematical
symbol used to represent ‘for all’ is ∀. So A1 – A3 can be rewritten using this symbol as
follows.

A1 ∀n ∈ Z, n2 ≥ 0.
A2 ∀n ∈ Z, n2 is even.
A3 ∀n ∈ Z, n is divisible by 1.

To show that a ‘for all’ statement is true we need to give a general argument; to show it is false
we need only give a single counterexample. Of the statements given here A1 and A3 are true
and A2 is false.

Exercise 1.26 Write each of the following statements using, where possible, the symbols ∀,
∈, R and Q.

(a) For all rational numbers a, a2 is rational.

b 2
(b) For each rational number b, 3
+ 5
is rational.
(c) The cube of any real number is positive.

Which, if any, of the statements are true? Can you justify your answers?

Statements involving more than one quantifier

Many mathematical statements involve more than one quantifier. For example, the following
statements involve more than one quantifier.

M1 For all integers m there exists an integer n such that m + n = 0. (Using symbols: ∀m ∈
Z, ∃n ∈ Z such that m + n = 0.)
M2 Given integers l and m, there is an integer n such that l2 + m2 = n2 . (Using symbols,
∀l ∈ Z, ∀m ∈ Z, ∃n ∈ Z such that l2 + m2 = n2 .

Exercise 1.27 Verify that M1 is true and that M2 is false.

Exercise 1.28 The order of quantifiers is important. The statement

∃n ∈ Z such that ∀m ∈ Z, m + n = 0

looks similar to M1. Verify, however, that this statement is false. Explain the difference
between M1 and the statement given here.

Negating statements involving quantifiers

Consider the statement E2, ‘∃n ∈ Z such that n2 = 4’, once more. Suppose we want to negate
this statement, that is we want to write the statement ¬E2. One possibility is: ‘there does not
exist an integer n such that n2 = 4’. However, if this is true then if we take any integer its
square cannot be 4. Thus, a more succinct way of writing ¬E2 is: ’for all integers n, n2 ̸= 4’
or, using symbols: ∀n ∈ Z, n2 ̸= 4.
1.10 Proof by Contradiction Proof & Structure 21

Now consider the statement A2, ‘∀n ∈ Z, n2 is even’, once more. One possibility for ¬A2 is:
‘not all integers have an even square’. However, if this is true, then there must be some integer
whose square is not even. Thus, if we use the term ‘odd’ for ‘not even’, a more succinct way of
writing ¬A2 is: ‘there exists an integer n such that n2 is odd, or, using symbols: ∃n ∈ Z such
that n2 is odd.

In summary, when negating a statement involving quantifiers, we change there exists (∃) to for
all (∀), we change for all (∀) to there exists (∃) and negate the conclusion.
Example 1.9.2 Consider the statement M2, ‘∀l ∈ Z, ∀m ∈ Z, ∃n ∈ Z such that l2 + m2 = n2 ’.
Using the above observation we get that ¬M2 is
∃l ∈ Z, ∃m ∈ Z such that ∀n ∈ Z, l2 + m2 ̸= n2 .
That is: There are integers l and m such that for all integers n, l2 + m2 ̸= n2 .
Exercise 1.29 Negate the statement M1.
Quantifiers often occur in definitions. As an example we give the following important definitions
for certain types of mappings.
Definition 1.9.3 Let f : X → Y be a function from X to Y . Then f is injective (or one-
to-one) if for all x, y ∈ X with x ̸= y, f (x) ̸= f (y); f is surjective (or onto) if for all y ∈ Y ,
there exists x ∈ X such that f (x) = y; f is bijective if it is both injective and surjective.
Exercise 1.30 Write out the definition for a mapping to be (a) injective (b) surjective, using
the symbols ∀ and ∃.
Exercise 1.31 Write out the definition for a mapping not to be (a) injective (b) surjective,
using the symbols ∀ and ∃.
Exercise 1.32 For i = 1, 2, 3, 4, 5 let fi : R → R be defined as follows: f1 (x) = 3x + 2,
f2 (x) = x2 , f3 (x) = x3 , f4 (x) = 2 and f5 (x) = 2x . Which, if any, of these mappings is (a)
injective? (b) surjective? (c) bijective?
An injective function f : X → Y in some sense preserves the set X, because every x ∈ X has
a unique image f (x) – so in particular the set {f (x) : x ∈ X} is a subset of Y which has the
same size as X. We’ll talk more about this in Chapter 2.

1.10 Proof by Contradiction

Suppose you want to prove a statement s. One approach is assume that the negation ¬s is
true. The aim is to produce a mathematical argument from this starting point which leads to
a statement r that is clearly false, something like 1 = 0. Thus we have shown that (¬s) ⇒ r
is true. But r is false. By the truth table for ⇒, this forces ¬s to be false too (we can’t have
a true statement implying a false one). Therefore s was true all along. This is called a proof
by contradiction, because we are aiming to produce a false statement (r), which is known as
a contradiction. This can be a very powerful technique. In the case where s is an if. . ., then
statement p ⇒ q, the negation of s is p ∧ ¬q. So the starting point is to assume that p is true
and q is false.
Example 1.10.1 Prove that if 10 001 is composite, then it has a prime factor less than 98.
22 Proof & Structure Chapter 1: Mathematical Language and Proof

Commentary As in Example 1.7.4, there is an obvious proof, namely that 10 001 = 73 × 137
and, since 73 < 98, then 10 001 has a prime factor less than 98. However, it is worth looking
for an alternative, not least since finding the given factorisation of 10 001 is not that easy.

Note If m > 1 is a factor of any positive integer a, then there is a prime factor p of a with
p ≤ m. This is because either m is prime (so m = p), or m is composite and can be written
m = m1 m2 where both 1 < m1 < m and 1 < m2 < m. Either m1 is prime (so m1 = p) or m1
is composite and we can factorise m1 . We just continue like this until we get a prime number.
This process will terminate since at each step our factors are less than our original number and
greater than 1. That is, this process will terminate after at most a steps.

We will try a contradiction proof for Example 1.10.1. The statement is of the form p ⇒ q,
so we will suppose that 10, 001 is composite (p is true), and all of the prime factors of 10 001
are greater than 97 (q is false). Now if 10 001 is composite, then there exist positive integers
m, n both greater than 1 such that 10 001 = mn. Now m and n are factors of 10 001 which are
greater than 1, and so (by the Note) must be at least as large as the smallest prime factor of
10 001. Thus m, n > 97 and 10 001 = mn > 97 × 97 = 9409.

Bother. We haven’t got the required contradiction. A little more care is needed. Note that
none of 98, 99 or 100 is prime. Thus if all the prime factors of 10 001 are greater than 97,
then the smallest prime factor of 10 001 must be at least 101. If we try this, then we get the
following proof.

Proof Suppose that all of the prime factors of 10 001 are greater than 97. Then the smallest
prime factor of 10 001 is at least 101. Since 10 001 is composite, there are positive integers m
and n both greater than 1 such that 10 001 = mn. Now m and n are factors of 10 001 which
are greater than 1, and so (by the Note) must be at least as large as the smallest prime factor
of 10 001. Thus m, n ≥ 101 and

10 001 = mn ≥ 101 × 101 = 10 201.

Hence we have a contradiction. Therefore our assumption that all the prime factors of 10 001
are greater than 97 was false. Hence 10 001 has a prime factor no greater than 97. □

Exercise 1.33 Let n be√ a positive integer. Prove that if n is composite, then it has a prime
factor no greater than n.

We conclude this section by giving contradiction proofs of two important results.

√
Theorem 1.10.2 2 is irrational.
√
Proof
√ Suppose that 2 is rational. Then there are integers p and q, with q ̸= 0, such that
2 = pq . Furthermore, we may suppose (cancelling if necessary) that p and q have no common
√ 2
factors. Squaring both sides of 2 = pq gives 2 = pq2 , and hence p2 = 2q 2 . Thus, using Exercise
1.16, p is even, and so there is an integer k such that p = 2k. Putting p = 2k in p2 = 2q 2 gives
4k 2 = 2q 2 , and so q 2 = 2k 2 . Thus q is also even. That is, both
√ p and q have 2 as a factor,
contradicting the fact that they have no common factors. Thus 2 is irrational. □
1.11 The Principle of Induction Proof & Structure 23

√
Exercise 1.34 Try to adapt the proof of Theorem 1.10.2 to show that 3 is irrational. Where,
if at all, are the potential difficulties?
√ √
Exercise 1.35 Follow the proof of Theorem 1.10.2, but replace 2 with 4. At what point
does the proof break down?
The following proof is perhaps the earliest contradiction proof. It was discovered by Euclid. We
use a result in the next section to help prove this result, as that result is proved by induction.
Theorem 1.10.3 There are infinitely many prime numbers.

Proof Suppose that there are only finitely many primes, p1 , p2 , . . . , pr , say. Let n = p1 p2 · · · pr +
1. By Example 1.12.2 below, there is a prime p that is a factor of n. Now n is one more than a
multiple of p1 , so clearly p1 does not divide n, hence p ̸= p1 . Similarly p ̸= p2 , p ̸= p3 , . . . , p ̸= pr .
Thus p is a prime not on the list, which is a contradiction. Thus there are infinitely many primes.
□

1.11 The Principle of Induction

Let P (n) be a statement concerning the positive integers Z+ . Suppose we can prove:
I1 P (1) is true;
I2 for each positive integer k, P (k) ⇒ P (k + 1).
Then P (n) is true for all positive integers n.
Example 1.11.1 Prove that, for all positive integers n,
∑n
1
r2 = n(n + 1)(2n + 1).
r=1
6

∑
Proof Let P (n) be the statement: nr=1 r2 = 16 n(n + 1)(2n + 1).
∑ ∑
For n = 1, nr=1 r2 = 1r=1 r2 = 12 = 1 and 16 n(n + 1)(2n + 1) = 16 × 1 × 2 × 3 = 1. Thus P (1)
is true. ∑
Now, suppose P (k) is true. That is, kr=1 r2 = 16 k(k + 1)(2k + 1). Then

∑k+1
r=1 r2 = 12 + 22 + · · · + k 2 + (k + 1)2
(∑ )
k
= r=1 r 2
+ (k + 1)2
1
= 6
k(k + 1)(2k + 1) + (k + 1)2 (since P (k) is true)
1
= 6
(k + 1)(k(2k + 1) + 6(k + 1))
1
= 6
(k + 1)(2k 2 + 7k + 6)
1
= 6
(k + 1)(k + 2)(2k + 3)
1
= 6
(k + 1)([k + 1] + 1)(2[k + 1] + 1).
Thus P (k + 1) is true.

Since we have shown that P (1) is true∑and that P (k) implies P (k + 1), it follows that P (n) is
true for all positive integers n. Thus nr=1 r2 = 16 n(n + 1)(2n + 1). □
Example 1.11.2 Show that for all positive integers n, 7n − 6n + 3 is divisible by 4.
24 Proof & Structure Chapter 1: Mathematical Language and Proof

Commentary It is important here that you do not confuse the statement you are trying to
prove (for all positive integers n, 7n − 6n + 3 is divisible by 4) with the expression involving n,
which is 7n − 6n + 3. In fact, it is worth giving the expression a name; we denote it by f (n)
here, but any name will do.

In the actual induction proof that follows you would expect f (k + 1) = 7k+1 − 6(k + 1) + 3 to be
expressed in terms of f (k) = 7k − 6k + 3. We do this indirectly by considering f (k + 1) − f (k).
This is a useful device which makes it easier to deal with the algebra.

Proof Let f (n) = 7n − 6n + 3 and let P (n) be the statement: f (n) is divisible by 4.

For n = 1, f (1) = 71 − 6 × 1 + 3 = 7 − 6 + 3 = 4. Thus f (1) is divisible by 4 and so P (1) is

true.

Suppose P (k) is true. That is, f (k) is divisible by 4. Now

f (k + 1) − f (k) = 7k+1 − 6(k + 1) + 3 − (7k − 6k + 3)
= 7k+1 − 6k − 6 + 3 − 7k + 6k − 3
= 7k+1 − 7k − 6
= 7k (7 − 1) − 6
= 6(7k − 1)
Since 7k is odd, 7k − 1 is even and so is divisible by 2. Thus 6(7k − 1) is divisible by 4. Now
f (k + 1) = f (k) + 6(7k − 1)
and so is the sum (by the inductive hypothesis) of two integers which are both divisible by 4.
Hence f (k + 1) is divisible by 4 and so P (k + 1) is true.

Since we have shown that P (1) is true and that P (k) implies P (k + 1), it follows that P (n) is
true for all positive integers n. Thus for all positive integers n, 7n − 6n + 3 is divisible by 4.□
Exercise 1.36 Can you modify this proof to show that f (n) is divisible by 6 for all n? If not,
where does it fall down?
∑ ∑
Exercise 1.37 Use the principle of induction to show that nr=1 r = 12 n(n + 1) and nr=1 r3 =
1 2
4
n (n + 1)2 .
Exercise 1.38 Prove that, for all positive integers n, 7n − 4n is divisible by 3.

1.12 Variations on the Principle of Induction

There are several different variations on the method of proof using the principle of induction.
Here we consider just two variations on the main method.
Variation 1: A different starting point
There is no reason why an induction proof should start at n = 1. In fact there are certain
statements which are not true for the first few positive integers. And sometimes we prefer to
start at n = 0, in other words to consider the set of natural numbers. In this case the following
method can sometimes be used.
Let P (n) be a statement concerning the integers Z. Suppose that we can prove:
1.12 Variations on the Principle of Induction Proof & Structure 25

I1′ for some integer N , P (N ) is true;

I2′ for every integer k ≥ N , P (k) ⇒ P (k + 1).

Then P (n) is true for all integers n ≥ N .

Example 1.12.1 For all integers n ≥ 5, 2n > n2 .

Proof Let P (n) be the statement 2n > n2 . For n = 5, 25 = 32 and 52 = 25. Thus 25 > 52
and so P (5) is true.
Suppose P (k) is true. That is 2k > k 2 . Then

2k+1 = 2 × 2k
> 2k 2 (since P (k) is true)
= k 2 + [(k + 1)2 − 2k − 1]
= (k + 1)2 + k 2 − 2k − 1.

Now if k ≥ 3, then k 2 − 2k − 1 = (k − 1)2 − 2 > 0 and so 2k+1 > (k + 1)2 . Thus, if k ≥ 3, P (k)
implies P (k + 1).
Since we have shown that P (5) is true and that, for k ≥ 3, P (k) implies P (k + 1), it follows
that P (n) is true for all integers n ≥ 5. Thus for all integers n ≥ 5, 2n > n2 . □

Exercise 1.39 Prove that, for all integers n ≥ 4, n! ≥ 2n .

Variation 2: Strong Induction

Let P (n) be a statement concerning the positive integers. Suppose that we can prove:

S1 P (1) is true;
S2 for each positive integer k, P (1), P (2), . . . , P (k) together imply P (k + 1).

Then P (n) is true for all positive integers n.

Remarks Note that as in the first variation, we have a version of strong induction which starts:
for some integer N , P (N ) is true.
At first sight, strong induction looks significantly different from the basic induction, because we
are allowed to assume all of P (1), P (2), . . . , P (k) to prove P (k + 1). However, strong induction
is actually equivalent to basic induction. To see this let Q(n) be the statement: for all m ∈ Z+
with m ≤ n, P (m). Then S1 and S2 become

S1′ Q(1) is true;

S2′ for each positive integer k, Q(k) implies Q(k + 1);

which are just the requirements of basic induction. It is usually clear which type of induction
is required once you try to deduce that P (k + 1) is true.

For the purpose of the next example we define a product of primes to be either a single
prime or an expression of the form p1 p2 · · · pr where each of p1 , p2 , . . . , pr is a prime number.

Example 1.12.2 Every integer greater than one can be expressed as a product of primes.
26 Proof & Structure Chapter 1: Mathematical Language and Proof

Proof Let P (n) be the statement that n can be expressed as a product of primes.

Since 2 is prime, P (2) is true.

Suppose P (2), P (3), . . . , P (k) are true. That is, 2, 3, . . . , k can all be expressed as a product
of primes.

Consider k + 1. Either k + 1 is prime or it is composite. If k + 1 is prime, then k + 1 is obviously

a product of primes. If k + 1 is composite, then there exist integers l and m with 1 < l < k + 1
and 1 < m < k + 1 such that k + 1 = lm. Since 1 < l < k + 1 and 1 < m < k + 1, both P (l)
and P (m) are true by the induction hypothesis. That is, there are primes p1 , p2 , . . . , pr and
q1 , q2 , . . . , qs such that l = p1 p2 · · · pr and m = q1 q2 · · · qs . Thus

k + 1 = lm = p1 · · · pr q1 · · · qs

can be expressed as a product of primes. Hence P (k + 1) is true.

Since we have shown that P (2) is true and that P (2), . . . , P (k) together imply P (k + 1), it
follows by induction that P (n) is true for all integers greater than 1. Thus every integer greater
than 1 can be expressed as a product of primes. □

Exercise 1.40 Look back at Exercise 1.3, in which cn is defined to be the smallest number of
moves required to break up an (n + 1)-cube chocolate bar into individual cubes. Use strong
induction to prove that cn = n for all positive integers n. [Hint: Your first move is always to
break the bar into two pieces along a line. Those pieces have, say l and m cubes respectively.
Use the inductive hypothesis on both pieces.]
 1.12 Variations on the Principle of Induction Proof & Structure 27

Exam-Style Questions
Section A
Exercise 1.41 The following is a statement about a triangle ABC.
If ABC is isosceles, then AB = BC.

(a) Write out the contrapositive of the statement. [2]

(b) Write out the converse of the statement. [1]
(c) Write out the negation of the statement. [2]

Exercise 1.42 Let n be an integer with n > 1.

(a) Prove that if n is odd, then n2 + 2n − 3 is composite. [3]
(b) Give a counterexample to the following statement:
‘If n is even, then n2 + 2n + 5 is prime.’ [2]

Exercise 1.43 Let p and q be statements. Construct a truth table to show the truth values
of ¬p ∧ q and (p ∨ q) ⇒ ¬p. Are ¬p ∧ q and (p ∨ q) ⇒ ¬p equivalent? Explain your answer. [5]

Exercise 1.44 Consider the following statement.

For each real number x there is an integer n such that n > x.

(a) Write out the statement using the symbols ∃, ∀, R, Z and ∈. [3]
(b) Write out the negation of the statement. [2]

Section B
n
∑
Exercise 1.45(a) Let f (n) = (2r − 1).
r=1

(i) Evaluate f (n) for n = 1, 2, 3, 4, 5 and 6. [3]

(ii) Conjecture a formula for f (n) in terms of n. [2]
(iii) Use induction to prove that your conjecture in (ii) is valid for all positive
integers n. [5]
(b) Let n be a positive integer. Use a contrapositive proof to show that if 2n − 1 is prime, then
n is prime. [5]
(c)(i) Suppose that a, b, c and d are positive integers such that
a2 − 3b2 = 1
c2 − 3d2 = 1.
Let x = ac + 3bd and y = ad + bc. Show that x2 − 3y 2 = 1. [3]
(ii) Noting that 22 − 3(12 ) = 1 and 72 − 3(42 ) = 1, use part (i) to find positive integers m and
n, with m > 7, such that m2 − 3n2 = 1. [2]

Note: Exam questions, particularly Section B questions, often combine elements from different
chapters.
28 Proof & Structure Chapter 1: Mathematical Language and Proof

Historical Notes
At the end of each chapter of these notes you will find some historical titbits relevant to the
topics that have been covered. Since we would certainly call the study of proof pure mathe-
matics, you might wonder where this term first arose. Francis Bacon wrote about mathematics
in Book II of ‘The Advancement of Learning’, published in 1605. He split mathematics (then
used in the plural, hence the s) into ‘pure’ and ‘mixed’ – what we would now call applied.
In the Mathematics I can report no deficience, except it be that men do not sufficiently
understand the excellent use of the Pure Mathematics, in that they do remedy and cure many
defects in the wit and faculties intellectual. [. . . ...] And as for the Mixed Mathematics, I may
only make this prediction, that there cannot fail to be more kinds of them, as nature grows
further disclosed.
We’ll mention Bacon again later in the context of the mathematician Cantor.
In the first edition of the Encyclopaedia Britannica (1768-1771), the advantage of proof is
discussed:
Pure mathematics have one peculiar advantage, that they occasion no disputes among
wrangling disputants, as in other branches of knowledge; and the reason is, because the
definitions of the terms are premised, and every body that reads a proposition has the same
idea of every part of it.

Pythagoras (circa 569 – 475 BC)

Not a great deal is known about Pythagoras. He was probably not the first to prove ‘Pythago-
ras’ Theorem’, if indeed he proved it at all (the first surviving written proof from the Greek
mathematical tradition is in Euclid, Proposition 47, Book 1). Lists of Pythagorean triples, that
is sets of three integers which form the sides of a right angled triangle (3,4,5; 5,12,13; and so
on) have been found on Babylonian tablets and it is even speculated that three of the six triples
with numbers smaller than 40 were known to megalithic man. This of course isn’t the same
as proving the theorem. However there were proofs by Chinese and Indian mathematicians,
possibly predating Pythagoras. The Indian Mathematician Baudhayana, in roughly 800BC,
includes a special case of the theorem in his Sulbasutra: ‘The rope which is stretched across
the diagonal of a square produces an area double the size of the original square.’ In China
Pythagoras’ Theorem is known as the Gougu rule. Since Pythagoras hundreds of proofs have
been devised, one even due to a U.S. President!
Pythagoras’ Theorem and the elegant approach of Euclid have impressed many over the cen-
turies. The following is from a biography of the philosopher Thomas Hobbes.
He was 40 years old before he looked on Geometry; which happened accidentally. Being in a
Gentlemen’s Library, Euclid’s Elements lay open, and ’twas the 47 El. libri I. He read the
Proposition. By G–, sayd he (he would now and then sweare an emphaticall Oath by way of
emphasis) this is impossible! So he reads the Demonstration of it, which referred him back to
such a Proposition; which proposition he read. That referred him back to another, which he
also read. Et sic deinceps [and so on] that at last he was demonstratively convinced of that
trueth. This made him in love with Geometry.
1.12 Variations on the Principle of Induction Proof & Structure 29

Kurt Gödel (28 April 1906 – 14 January 1978)

Led by world famous mathematician David Hilbert, mathematicians before and during the time
of Gödel were looking for a way to put mathematics on a solid logical foundation. At the time,
attempts to clarify the foundations of mathematics by basing them on a consistent set of axioms
were failing. Hilbert’s program was to find set of axioms powerful enough to describe the results
of arithmetic, whilst being internally consistent. However, it was Gödel’s ground breaking work
in mathematical logic that put serious doubt into the possibility of Hilbert’s program. Gödel’s
incompleteness theorems essentially state that any sufficiently powerful consistent logical sys-
tem is incomplete; that is, any such system can be shown to contain true statements which
cannot be proved by logical deductions from the axioms (i.e. they are not theorems).

Gödel’s results have shown that Hilbert’s program is unattainable in the full generality en-
visioned by Hilbert. However, some of the current research in mathematical logic essentially
continues with Hilbert’s program by weakening its goals.
30 Proof & Structure Chapter 1: Mathematical Language and Proof

Learning Outcomes
After studying this chapter, and the related exercises, you should be able to

• appreciate why there is a need for proof in mathematics;

• realise that there is no guaranteed method for constructing proofs of a given mathematical
statement;

• feel more confident using mathematical notation and terminology;

• understand and define the terms even, odd, prime, composite, multiple and divides with
respect to the integers;

• be aware that a real number is either rational or irrational;

• write out the truth tables of ¬p, p ∧ q, p ∨ q, p ⇒ q and p ⇐⇒ q, and use them to
construct the truth tables of statements involving at most three simple statements;

• explain what it means for a statement to be a tautology and what it means for two
statements to be equivalent;

• state and verify de Morgan’s laws;

• rewrite a statement of the form if p, then q as an equivalent either/or statement;

• write out the contrapositive, converse and negation of a statement of the form if p, then
q, and know that this statement is equivalent to its contrapositive;

• construct proofs for elementary statements, particularly ones about even and odd integers,
primes and perfect squares;

• show elementary statements are false by means of a suitable counter-example;

• rewrite statements involving quantifiers using the symbols ∀ and ∃;

• negate statements and definitions involving quantifiers;

• determine whether a simple statement involving quantifiers is true or false;

• understand the ideas involved in a contrapositive proof and in a proof by contradiction,

and use them to verify elementary results;
√
• prove that 2 is irrational and that there are infinitely many primes;

• understand the principle of induction, and use it to prove statements about the natural
numbers.