Unit

7
MATHEMATICAL PROOFS
T
T
F
F
p q
T
F
T
F
p⇒q
T
F
T
T
(p ⇒ q) ∧ ¬ q
F
F
F
T
[(p ⇒ q) ∧ ¬q] ⇒ ¬p
T
T
T
T

Unit Outcomes:
After completing this unit, you should be able to:



develop the knowledge of logic and logical statements.



understand the use of quantifiers and use them properly.



determine the validity of arguments.



apply the principle of mathematical induction for a problem that needs to be
proved inductively.



realize the rule of inference.

Main Contents
7.1 REVISION ON LOGIC
7.2 DIFFERENT TYPES OF PROOFS
7.3 PRINCIPLE AND APPLICATION OF MATHEMATICAL INDUCTION
Key Terms
Summary
Review Exercises
 Unit 7 Mathematical Proofs

INTRODUCTION
In order to fully understand Mathematics, it is important to understand what makes up a
correct mathematical argument, or proof. In this unit, you will be introduced to different
methods of mathematical proof and you will also see the role of mathematical logic in
proving mathematical statements. We will begin the unit by briefly revising
mathematical logic.

 O PPEEN
NIIN
NGG P
PRRO
OBBLLE
EMM
After completing this unit, you should be able to answer the following:
Consider the following arrangements of dots.

etc

Number of dots 1 3 6 10
Sum of dots in row 1 1+2 1+2+3 1+2+3+4

Numbers like 1, 3, 6, 10, etc. are called triangular numbers.

a Can you list the next 5 triangular numbers?
b Can you give a formula for the ith triangular number?
c Let Ti denote the ith triangular number. Can you show that
n
n ( n + 1)( n + 2)
∑
i =1
Ti =
6
?
40
d Can you find ∑T ?
i =1
i

7.1 REVISION ON LOGIC

Revision of Statements and Logical Connectives

In Unit 4 of your Grade 11 mathematics, you have studied statements and logical
connectives (or operators):
negation (¬), or (∨), and (∧), implication (⇒) and bi-implication (⇔).
The following activities are designed to help you to revise these concepts.

297
Mathematics Grade 12

ACTIVITY 7.1
1 What is meant by a statement (proposition)?
2 List the propositional connectives.
3 What is meant by a compound (complex) statement?
4 Review the rules of assigning truth values to complex propositions by completing
the table below, where p and q are any two propositions.
p q ¬p p∧q p∨q p⇒q p⇔q
T T
T F
F T
F F
5 Given statements p and q, each with truth value T, find the truth value of each of
the following compound statements.

a ¬p ∨ q b ¬(p ∨ q) c ¬q ⇒ ¬p
d ¬q ⇔ p e ¬(p ∧ q)
6 Construct a truth table for
a ¬p ∨ q b (p ⇒q) ⇔ ¬p
c (p ∧ q) ⇒r d ¬ (p ⇒ q) ∨¬ r

Open statements and quantifiers

ACTIVITY 7.2
Decide whether or not each of the following is a statement.
If it is a statement, determine its truth value.
1 x is a composite number.
2 If 3 + 2 = 7, then 4 × 9 = 32.
3 x + 2 = 15, where x is an integer.
4 All prime numbers are odd.
5 There exists a prime number between 15 and 30.
6 All birds can fly.
As you may recall from your Grade 11 lessons, the words all and there exists in
questions 4, 5 and 6 of Activity 7.2 are quantifiers.

298
 Unit 7 Mathematical Proofs

Some of the sentences involve variables or unknowns and become statements when the
variables or the unknowns are replaced by specific numbers or individuals; such
sentences are called open statements.
Recall that open statements are denoted by P (x) where x stands for the unknown and P
stands for some property that is to be satisfied by x. For example, if we denote the open
statement 1) above by P(x), then P stands for the property of being a composite number
while x is the variable or the unknown in the open statement.
Quantifiers
There is a way of changing an open statement into a statement without substituting
individual(s) for the variable(s) involved by using what we call quantifiers. There are
two types of quantifiers which are used to change an open statement into a statement,
without any substitution. They are:
The universal quantifier denoted by ∀ and
The existential quantifier denoted by ∃.
The notation ∀x may be read in any one of the following ways:
for all x for every x
for each x for any x
The notation ∃x may be read in any one of the following ways:
there exists x, for at least one x, for some x
Example 1 Let P(x) ≡ x > 5 and Q(x) ≡ x is an even number. Then determine the
truth value of each of the following statements.
a (∀x) P(x) b (∃x) P(x)
c (∃x) [P(x) ∧ Q(x)] d (∀x) [P(x) ⇒ Q(x)]
Solution
a (∀x) P(x) is false, because if you take x = 1, then 1 > 5 is false.
b (∃x) P(x) is true, because you can find an x, say x = 7 such that 7 > 5 is true.
c (∃x) [P(x) ∧ Q(x)] is true, if you take x = 6, then 6 > 5 and 6 is even.
d (∀x) [P(x) ⇒ Q(x)] is false, for x = 7, P(7) is true but Q(7) is false.
Example 2 Change the following open statement into a statement using quantifiers
and determine the truth value.
P(x): x2 < 0, where x is a complex number.
Solution Using the universal quantifier, (∀x) P(x) is false, because when x is a
real number such as x = 1, x2 < 0 is false.
Using the existential quantifier, (∃x) P(x) is true because when x is an imaginary
number such as x = i, 2i, etc, x2 = –1, –4, etc.

299
Mathematics Grade 12

Exercise 7.1
1 Let P(x) = x is a student who studied geometry.
Then, (∀x) P(x) is read as:
while (∃x) P(x) is read as:
2 Given the open statements:
P(x) ≡ x is a prime number. Q(x) ≡ x is an odd number.
Determine the truth value of each of the following statements.
a (∀x) P (x) b (∃x) P (x) c (∃x) (¬P (x))
d (∀x) [P(x) ⇒ Q(x)] e (∃x) [P (x) ∧ ¬ Q(x)]
3 If x and y are integers, determine the truth value of each of the following.
a (∃x) (∀y) ( x ≤ y) b (∃x) (∀y) (x2 ≤ y)
c (∀x) (∃y) (x ≤ y) d (∀x) (∀y) (x + y = y + x)
e (∀x) (∃y) (x + y = 0)
4 Express each of the following using quantifiers.
a Some students in this class have visited Gondar.
b Every student in this class has visited either Gondar or Hawassa.

Arguments and validity of arguments

ACTIVITY 7.3
1 Discuss whether or not the following conclusion is meaningful.
a If the day is cloudy, then it rains.
Does this mean that if it rains, there are clouds?
b If x is a prime number and y is a composite number, then x + y is a
composite number.
2 Construct a single truth table for the following statements.
p ⇒ q, ¬ q ⇒ r, and p.
Find out the rows in which the statements p ⇒ q and ¬ q ⇒ r are both true but p
is false.
An argument is an assertion that a given set of statements called the premise
(hypothesis), yields another statement, called the conclusion (consequent).
An argument is said to be valid, if and only if the conjunction of all the premises always
implies the conclusion. In other words, if we assume that the statements in the premises
are all true, then (for a valid argument), the conclusion must be true. An argument
which is not valid is called a fallacy.

300
 Unit 7 Mathematical Proofs

The validity of an argument can easily be checked by constructing a truth table. All you
must show is that the premises altogether always imply the conclusion. In other words,
you show that "conjunction of the premises ⇒ conclusion" is always true (or a
tautology).
To show the validity of an argument, you have to show that the conclusion is true
whenever all the premises are true.
Example 3 Is the following argument valid?
If I am rich, then I am healthy.
I am healthy.
Therefore, I am rich.
Solution
Note that the first two statements are the premises while the last statement is the
conclusion. This argument is not a valid argument. To see why, we shall first
symbolize it.
Let p stand for the statement "I am rich" and let q stand for the statement "I am
healthy".
Then, the symbolic form of the above argument becomes:
p ⇒ q
q
or p ⇒ q, q p
p
This argument would be valid, if the implication [(p ⇒ q) ∧ q] ⇒ p were always true.
When you construct the truth table for this conditional statement as shown below, you
see that the conclusion could be F while both the premises are true. (See the third line in
the 5th column). In other words, [(p ⇒ q) ∧ q] ⇒ p is not a tautology. Thus, the
argument is invalid.
p q p⇒q (p ⇒ q ) ∧ q [(p ⇒ q) ∧ q] ⇒ p
T T T T T
T F F F T
F T T T F
F F T F T
Example 4 Is the following argument valid?
If I am healthy, then I will be happy.
I am not happy.
Therefore, I am not healthy.

301
Mathematics Grade 12

Solution Once again, to check the validity of this argument, symbolize it. Let p
represent "I am healthy" and let q represent "I am happy". The symbolic
form of the argument is:
p⇒q p ⇒ q, ¬ q ¬ p.
¬q
¬p
This argument will be valid, if the implication [(p ⇒ q) ∧ ¬ q] ⇒ ¬p is always
true (a tautology). Constructing a truth table as shown below, you notice that the
argument is valid.
p q ¬p ¬q p⇒q (p ⇒ q ) ∧ ¬ q [(p ⇒ q) ∧ ¬q] ⇒ ¬p
T T F F T F T
T F F T F F T
F T T F T F T
F F T T T T T
Example 5 Show that the following argument is valid.
If you send me an email, then I will finish writing my project.
If I finish writing my project, then I will get relaxed.
Therefore, if you send me an email, then I will get relaxed.
Solution
Let: p ≡ you send me an email
q ≡ I finish writing my project
r ≡ I get relaxed. Then the symbolic form of this argument will be as follows.
p⇒q
q⇒r
p⇒r
Now, the implication [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r) is always true as shown in
the truth table below.
p q r p⇒q q⇒r p⇒ r (p ⇒q)∧(q ⇒ r) [(p ⇒ q)∧(q ⇒ r)]⇒(p ⇒r)
T T T T T T T T
T T F T F F F T
T F T F T T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Therefore, the argument p ⇒ q, q ⇒ r p ⇒ r is valid.

302
 Unit 7 Mathematical Proofs

The construction of such a big truth table may be avoided by studying and correctly
applying the following rules by which we check whether a given argument is valid or
not. They are called rules of inference and are listed as follows.
p
1 Principle of adjunction addition. It states that "If p is true, then p∨q is
p∨q
also true for any proposition q "
p ∧ q
2 Principle of detachment simplification. It states that "If p ∧ q is true,
p
then p is true".
p
q
3 Principle of conjunction. It states that whenever p and q are true the
p∧q
statement p ∧ q is also true.
p ⇒ q
p
4 Modus ponens. It states that whenever the implication p ⇒ q is true
q
and the hypothesis p is true, then the consequent q is also true. Recall
the rule of implication.
p ⇒ q
¬q
5 Modus Tollens. It states that whenever, p ⇒ q is true and q is false,
¬p
then p is also false.
p ⇒ q
q ⇒ r
6 Principle of syllogism (Law of syllogism). It may be remembered as
p ⇒ r
the transitive property of implication. This law was one of Aristotle’s
(384 – 322 B.C.) main contributions to logic.
p ∨ q
¬p
7 Modus Tollends Ponens. This rule is also called the Disjunctive
q
syllogism.
Let us now consider examples that show how the above rules of inference are applied.
Example 6 Identify the rule of inference applied for each of the following
arguments.
a It is raining.
Therefore, it is raining or it is cold.
The rule that applies to this argument is rule 1 (adjunction).

303
Mathematics Grade 12

b Abdissa is rich and happy.

Therefore, he is rich.
The rule applied here is rule 2 (Detachment).
c It is cold today.
It is raining today.
Therefore, it is raining and it is cold today.
This argument uses rule 3 (conjunction).
d If Hanna works hard, then she will score good grades. Hanna works hard.
Therefore Hanna scores good grades.
This argument uses rule 4 (Modus ponens).
e If it is raining, then I get wet when I go outside. I do not get wet when I go
outside.
Therefore, it is not raining.
In this argument, the appropriate rule is rule 5 (Modus Tollens).
f If I get a job, then I will earn money.
If I earn money, then I will buy a computer.
Therefore, if I get a job, then I will buy a computer.
The inference rule 6 (Principle of syllogism) is applied here.
g Either wages are low or prices are high .Wages are not low.
Therefore, prices are high.
The inference rule applied here is rule 7. (Modus Tollends Ponens)
Example 7 Using rules of inference, check the validity of the following argument.
p
p⇒q
q⇒r
r
Solution
1 p is true (premise)
2 p ⇒ q is true (premise)
3 q is true (Modus ponens from 1, 2)
4 q ⇒ r is true (premise)
5 r is true (Modus ponens from 3, 4)
Therefore, the argument is valid. i.e., p, p ⇒ q , q ⇒ r r is valid.

304
 Unit 7 Mathematical Proofs

Note:
This is not the only way you can show this. Here is another set of steps.
1 p is true (premise).
2 p ⇒ q is true (premise).
3 q ⇒ r is true (premise).
4 p ⇒ r is true (syllogism from 2,3).
5 r is true (Modus ponens from 1, 4).
Therefore, the argument is valid.

All the examples considered above are examples of valid arguments. It is now time to
see an example of an invalid argument (or a fallacy).
q
Example 8 ¬p ⇒ ¬q
¬p
Solution
1 q is true (premise)
2 ¬q is false from (1)
3 ¬p ⇒ ¬q is true (premise)
4 ¬p is false (from 2 and 3)
Therefore, the argument form is not valid.

Exercise 7.2
1 Which of the following are statements? Which of them are open statements?
a Plato was a philosopher. b 3 is rational
c x2 + 1 = 5 d (∃x )( x 2 + 1 = 5)
e What is today’s date?
2 Let p: 5 + 3 = 9 and q: Today is sunny
a Write each of the following in symbolic form
i 5 + 3 = 9 or today is not sunny
ii 5 + 3 = 9 only if today is sunny
iii 5 + 3 ≠ 9 if and only if today is sunny
iv It is sufficient that today is sunny in order that 5 + 3 ≠ 9.
b Write each of the following in words.
i p ∧ ¬q ii ¬p ⇒ q iii ( p ∨ q ) ⇒ ¬q
305
Mathematics Grade 12

3 Using truth tables, show that each pair of the following are equivalent.
a ¬p ∨ q ; ¬q ⇒ ¬p b ¬p ⇔ ¬q ; p ⇔ q
c ¬p ⇔ q ; ( p ∨ q ) ∧ ¬ ( p ∧ q )
4 Using truth tables, check whether each of the following arguments given
symbolically is valid or invalid (a fallacy).
p p p ∧ q
q ¬q p ⇒ q
a b c
p ⇒ q q ⇒ p p ∨ q
5 For each of the following arguments written in words determine whether the
argument is valid or not.
a Your troubles start when you get married.
You have no troubles.
Therefore, you are not married.
b If Legesse drinks beer, he is at least 18 years old.
Legesse does not drink beer.
Therefore, Legesse is not yet 18 years old.
6 Using rules of inference check the validity of each of the following arguments.
p ⇒ (q ∨ r )
a ¬q ∧ ¬r
¬p
b If I study, then I will not fail in mathematics.
If I do not watch TV frequently, then I will study. But, I failed in mathematics.
Therefore, I must have watched TV frequently.
7 Using truth tables, check the validity of each of the following arguments.
p ∧ ¬q p ∧ ¬q p ∨ ¬r
a r ∨ ¬p b ¬q c p ∨q
q⇒r p q∨r
8 Using rules of inference check the validity of each of the following.
a p ⇒ ¬q , r ⇒ q , r ¬p
b Hailu’s books are on the desk or on the shelf.
The books are not on the shelf.
Therefore, they are on the desk.
c If 5 is even, then 2 is prime. 2 is prime if and only if 4 is positive.
4 is not positive.
Therefore, 5 is not even.
306
 Unit 7 Mathematical Proofs

7.2 DIFFERENT TYPES OF PROOFS

In Mathematics, a proof of a given statement is a sequence of statements that form an
argument. When a valid argument is constructed, you say that the given statement is
proved. There are different methods by which proofs are constructed. The rules of
inference discussed above, are instruments to construct proofs. In this section, you shall
consider different types of proofs of mathematical statements.
Since many mathematical statements are implications, the techniques for proving
implications are important. Recall that the implication p ⇒ q is true unless p is true and
q is false. Therefore, you notice that when the statement p ⇒ q is proved, the only thing
to be shown is that q is true if p is true; it is not usually the case that q is proved to be
true, in isolation. The following discussion will give you the most common techniques
for proving implications.
Direct proof
The implication p ⇒ q can be proved by showing that if p is true, then q must also be
true. A proof of this kind is called a direct proof. To construct such a proof, you
assume that p is true and use rules of inference and facts already known or proved, to
show that q must also be true.

ACTIVITY 7.4
1 Complete the proof of the following statement.
If x and y are odd integers, then x + y is an even integer.
Proof:
If x and y are odd integers, then there exist integers m and n such that
x = 2n + 1 and y = 2m + 1.
⇒ x + y = _________
⋮
Therefore, x + y is an even integer.
2 Given below is a proof of the following statement. Give reasons why each of the
statements in the proof is true.
m+5 m
∀n, m ∈ ℝ, if n > m > 0, then > .
n+5 n
Proof:
n > m ⇒ 5n > 5m ⇒ 5n + mn > 5m + mn ⇒ n (m + 5) > m (n + 5)
m+5 m
⇒ >
n+5 n

307
Mathematics Grade 12

Example 1 Give a direct proof of the statement " If n is odd, then n 2 is odd".
Proof:
Assume that the hypothesis of the statement (implication) is true; i.e. suppose that
n is odd. Then n = 2k+1 for some integer k.
Then, it follows that n2 = (2 k + 1)2 = 4k2 + 4k + 1 = 2 (2k2 + 2k) + 1 = 2 m + 1
(where m = 2k2 + 2k which is an integer).
Therefore, n 2 is odd (as it is 1 more than an even integer).
The method of cases or exhaustion
In this method, each and every possible case is considered.
Example 2 Show that n2 + 3n + 7 is odd for all n ∈ ℤ
Proof:
Case 1 n is even
n is even ⇒ n = 2k, for k ∈ℤ , by definition.
⇒ n 2 + 3n + 7 = (2k)2 + 3 (2k) + 7 = 4k2 + 6k + 7 = 2 (2k2 + 3k + 3) + 1
Hence, n2 + 3n + 7 is odd.
Case 2 n is odd
n is odd ⇒ n = 2k + 1, for some k ∈ℤ
Accordingly n 2 + 3n + 7 = (2k + 1)2 + 3(2k + 1) + 7 = 4k2 + 4k + 1 + 6k + 3 + 7
= 2 (2k2 + 5k + 5) + 1
Thus, n 2 + 3n + 7 is odd
∴ From cases 1 and 2, n2 + 3n + 7 is odd ∀n ∈ ℤ .
Example 3 Show that for any x, y ∈ R , the maximum of x and y is given by
x +y + x − y
.
2
Proof:
Two cases arise: Either x ≥ y or x < y
Case 1 x≥ y
x ≥ y⇒ x− y ≥0
Then the maximum of x and y is x and x − y = x − y by definition of absolute value.
x +y + x− y x + y + ( x − y) 2x
Now, = = =x
2 2 2
x +y + x− y
Hence the maximum of x and y is =x
2
308
 Unit 7 Mathematical Proofs

Case 2 x<y
x < y ⇒ x – y < 0 ⇒ maximum of x and y is y and x − y = − ( x − y ) = − x + y .
x + y+ x− y x + y − (x − y ) 2y
Here, = = =y
2 2 2
x +y + x− y
So the maximum of x and y is =y
2
x+y + x −y
∴ The maximum of x and y is x or y given by .
2
Indirect proof
Since the implication p ⇒ q is equivalent to its contrapositive ¬q ⇒ ¬p, the implication
p ⇒ q can be proved by proving its contrapositive, ¬q ⇒ ¬ p, is a true statement. A
proof that uses this technique is called an indirect proof.
Example 4 Prove the statement "If 5n + 2 is odd, then n is odd".
Proof:
Assume that the conclusion of the implication is false; i.e. suppose n is even.
Then, n = 2k for some integer k. It follows that
5n + 2 = 5 (2k) + 2 = 10k + 2 = 2 (5k + 1).
So 5n + 2 is even (as it is a multiple of 2).
Thus, you have shown that if n is even, then 5n + 2 is even. You showed that the
negation of the conclusion implies the negation of the hypothesis. Therefore, its
contrapositive, which says "if 5n + 2 is odd, then n is odd" is true.
This ends the proof.

Remark:
In Example 1, the statement that "if n is odd, then n2 is odd" is proved. Using the
method of Example 5, we have equally proved that the statement "If n 2 is even, then n is
even" is also true, because this statement is the contrapositive of the above one.
Example 5 Show that ∀x, y ∈ R, with x and y positive,
if xy > 25 then x > 5 or y > 5.
Proof:
You can use indirect proof.
Suppose, 0 < x ≤ 5 and 0 < y ≤ 5. Then, 0(0) < x y ≤ 5(5). i.e., 0 < xy ≤ 25.
Thus, the product xy is not larger than 25.
∴If xy > 25, then x >5 or y >5 by a contra positive.

309
Mathematics Grade 12

Proof by contradiction
In the previous methods of proof, you used the method of proof that assumes p is true and
finally concludes that q is also true. Now what will happen if you start by assuming the
implication p ⇒ q is false? That means, if p is true and q is false? If this assumption leads to
a conclusion which contradicts either one of the assumptions or conclusions or any
previously known fact, then the assumption p ⇒ q is false was not correct. This will tell you
that p ⇒ q is always true. This method of argument is known as proof by contradiction.
Example 6 Prove the following statement by using the method of proof by
contradiction. " 2 is an irrational number".
Proof:
Let p be the statement " 2 is an irrational number”. Suppose that ¬p is true.
Then, 2 is a rational number. We shall now show that this leads to a
contradiction. The assumption that 2 is rational implies that there exist integers
a
a and b such that 2 = , where a and b have no common factor other than ± 1
b
a a
(so that is in its lowest terms). Since 2 = , by squaring both sides you get
b b
2
a
2 = 2 ⇒ a2 = 2b2.
b
This means that a2 is even implying that a is even. Now, since a is even, it follows
that a = 2c for some integer c.
Thus, 2b2 = a2 = 4c2 ⇒ b2 = 2c2.
This again means that b2 is even, hence b is even as well. Hence 2 is a common
factor of a and b.
Notice that it has been shown that ¬p implies that (r ∧ ¬r ) is true. Note that as shown
a
above, from ¬p, 2 = is rational, a and b have no common factor other than ± 1,
b
and at the same time 2 divides both a and b, i.e 2 is a common factor of a and b.
This is a contradiction, since you have shown that ¬p implies both r and ¬r where
r is the statement " a and b are integers with no common factor other than ± 1".
Hence ¬ p is false, as a result, p : " 2 is an irrational number" is true.
Example 7 Show that the sum of a rational and an irrational number is an irrational
number.
Proof:
Let a be a rational and b be an irrational number.
Suppose that on the contrary a + b is rational.

310
 Unit 7 Mathematical Proofs

p r
Then, a = and a + b = for some p, q, r , s ∈ ℤ , q, s ≠ 0.
q s
p r r p qr − ps
Now, a + b = +b= ⇒b= − =
q s s q sq
⇒ b is rational (qr − ps ∈ ℤ and sq ∈ ℤ sq ≠ 0)
This contradicts the assumption that b is irrational.
Thus, if a is rational and b is irrational, then a + b is irrational.
Disproving by counter-example

ACTIVITY 7.5
Give the negation of each of the following statements in symbolic form.
1 (∀x) (x2 > 0, where x is a real number)
2 (∃x) (2x is a prime number, where x is a natural number)
3 ((∀x) (∃y) (x = y2 + 1, where x and y are real numbers)
Note:
From Activity 7.5, you have the following results:
1 ¬(∀x) (P(x)) = (∃x) (¬P(x))
2 ¬(∃x) (Q(x)) = (∀x) (¬Q(x))
Suppose that you want to show that a statement of the form (∀x) P(x) is not true. This is
done by producing an element x0 from the universal set that makes P(x) false when
substituted in place of x. Such an element x0 is called a counterexample.
Note that only one counterexample needs to be found to show that (∀x) P (x) is false.
Example 8 Disprove the statement:
"For every natural number n, n2 – 11n + 121 is prime"
Proof:
It is sufficient to find one natural number that does not satisfy this condition.
Thus, if you take n = 5, you see that 52 – 11(5) + 121 = 91. But 91 is not a prime
number as 7 divides 91 i.e. 91 ÷ 7 = 13.
Therefore, the statement "∀n∈ ℕ , n2 – 11n + 121 is prime" is now disproved
using the counter example n = 5.
The different methods of proofs discussed above are not an exhaustive list of methods
of proof. They are just the most common methods and it is hoped that they will help you
see how the ideas of mathematical logic can be applied in stating and proving theorems.

311
Mathematics Grade 12

Exercise 7.3
1 Prove that the sum of two consecutive odd integers is a multiple of 4.
2 Show that, if a and b are rational numbers with a < b, then there exists a rational
number c such that a < c < b.
3 Prove that for any real numbers a and b, a + b ≥ 40, if and only if a ≥ 20 or
b ≥ 20.
4 Prove that the square of any integer is of the form 3k or 3k + 1, for k ∈ Z .
5 If m, n ∈ ℕ and mn is not a perfect square, then m is not a perfect square or n is
not a perfect square. ( x ∈ ℕ is a perfect square, if ∃n ∈ ℕ such that x = n2)

6 Show that 5 is irrational.

7 Show that if x and y are positive, then x2 + y 2 ≠ x + y .

8 Check whether or not each of the following is true.
a For any sets A and B, A ∩ B ⊆ A ∪ B
b For any n ∈ ℕ , n is even implies that 2 n – 1 is not prime.
9 Prove or disprove each of the following statements
a If x and y are even integers, then xy is also even.
b If 3n + 2 is odd, then n is odd.
c ∀n∈ ℕ , n! < n3
d ∀n∈ ℕ , n2 < n3

7.3 PRINCIPLE AND APPLICATION OF

MATHEMATICAL INDUCTION
Before we state the principle of mathematical induction, let us consider some examples.
Example 1 Consider the sum of the first n odd positive integers. That is,
if n = 1, 1=1 = 12
if n = 2, 1+3=4 = 22
if n = 3, 1+3+5=9 = 32
if n = 4, 1 + 3 + 5 + 7 = 16 = 42
if n = 5, 1 + 3 + 5 + 7 + 9 = 25 = 52
if n = 6, 1 + 3 + 5 + 7 + 9 + 11 = 36 = 62

312
 Unit 7 Mathematical Proofs

From the results above, it looks as if the sum of the first n odd natural numbers is
always given by n2. To express this idea symbolically, first observe that the nth odd
natural number is given by 2n – 1, (which you may check yourself). Then what we
have derived above can be expressed as:
1 + 3 + 5 + 7 + 9 + . . . .+ (2n – 1) = n2 (*)
You have seen by direct calculation that the formula (*) is true when n has any one of
the values 1, 2, 3, 4, 5 and 6.
Does this mean that the formula (*) is true for any natural number n? Can we be sure of
this simply by continuing numerical calculations?
Try the case when n = 13. Direct calculation shows that:
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 = 169 = 132.
So, our formula (*) seems to hold. One might also be tempted to say that since the
natural number n = 13 is chosen randomly, this proves that (*) is true for every possible
choice of n. Actually, no matter how many cases you check, you can never prove that
(*) is always true, because there are infinitely many cases and no amount of pure
calculation can check them all.
So, what is needed is some logical argument that will prove that formula (*) is true for
every natural number n.
Before you consider the details of this logical argument, some examples of assertions
which can be checked by direct calculation for small values of n, but which after careful
investigation, turn out to be false for some other values of n.
Example 2 Consider the number P which is expressed in the form
n
P = 22 + 1 ..............................................i
Where n is a non-negative integer, then by direct calculation, we observe that
when n = 0, P = 21 + 1 = 3
when n = 1, P = 22 + 1 = 5
when n = 2, P = 24 + 1 = 17
when n = 3, P = 28 + 1 = 257
when n = 4, P = 216 + 1 = 65,537
Each of these values of P is a prime number. Based on these results, can you
conclude that P is always a prime number for every whole number n? Of course
not. You might guess that this is true but we should not make a positive assertion
unless you can supply a proof that is valid for every whole number n; because
when n = 5, the number P is found not to be prime since:
P = 232 + 1 = 4, 294, 967, 297 = 641 × 6,700,417, which is not prime.

313
Mathematics Grade 12

Example 3 Consider the inequality below, where n is a natural number.

2n < n10 + 2 .......................................... ii
If we calculate both sides of (ii) for the first four values of n, you observe that
when n = 1, you get 2<1+2=3
when n = 2, you get 4 < 1024 + 2 = 1026
when n = 3, you get 8 < 59,051
when n = 4, you get 16 < 1,048,578
It certainly appears as if the inequality is true for any natural number n. If you also
try for a larger value of n, say n = 20, then the inequality ii shows that
1,048,576 < 10,240,000,000,002
which is obviously true. But, even this does not prove that the inequality ii is always
true. This assertion is actually false, because when n = 59, you find (approximately) that
259 = 5.764 × 1017 while 5910 + 2 = 5.111 × 1017
The last two examples show that you cannot conclude that an assertion involving an
integer n is true for all positive values of n just by checking specific values of n, no
matter how many you check.
How then is such an assertion proved to be true?
An assertion involving a natural number can be proved by using a method known as the
Principle of Mathematical Induction, stated as follows.

 H IISSTTO
ORRIIC
CAALL N
NOOT
TEE

Augustus Demorgan (1806 - 1871)

One of the techniques to prove mathematical statements discussed
in this unit is the Principle of Mathematical Induction. Even though
the method was used by Fermat, Pascal and others before him, the
actual term mathematical induction was first used by Demorgan.
The method is used in many branches of higher mathematics.

Principle of Mathematical Induction

For a given assertion involving a natural number n, if
i the assertion is true for n = 1
ii it is true for n = k + 1, whenever it is true for n = k (k ≥1),
then the assertion is true for every natural number n.

314
 Unit 7 Mathematical Proofs

Let us now illustrate the use of this principle by considering different examples. Your
first example will be the one which you considered at the beginning of this section.
Example 4 Show that the sum of the first n odd natural numbers is given by n2. i.e.,
show that,
1 + 3 + 5 + . . . + (2n – 1) = n2 ........................................... *
for every natural number n.
Proof:
1 It is clear that * is true when n = 1 because 1 = 12.
2 Now assume that * is true for n = k; that is assume that
1 + 3 + 5 + . . . + (2k – 1) = k2 ........................................... **
To obtain the sum of the first k + 1 odd integers, you simply add the next odd
integer which is 2k + 1, to both sides of ** to get:
1 + 3 + 5 + . . . + (2k – 1) + (2k + 1) = k2 + (2k + 1) = (k + 1)2
This is the same as * replacing n with k + 1. Hence, you have shown that if the
assertion is true for k, it is also true for k + 1.
By the principle of Mathematical Induction, this completes the proof that * is true
for any natural number n.
Example 5 Show that the equation
n(3n − 1)
1 + 4 + 7 + 10 + . . . + (3n − 2) = ........................ i
2
is true for any natural number n.
Proof:
1(3(1) − 1) 1 × 2
1 The equation i is true for n = 1 because 1 = =
2 2
2 Assume that the equation i is true for n = k; that is you assume that,
k (3k − 1)
1 + 4 + 7 + 10 + . . . + (3k - 2) = ......................... ii
2
Now, if you add the next addend which is 3 (k + 1) – 2 or 3k + 1 to both sides of ii,
you get:
k (3k − 1)
1 + 4 + 7 + 10 + . . . + (3k – 2) + (3k + 1) = + (3k + 1)
2
k (3k − 1) + 2(3k + 1) 3k 2 + 5k + 2 (k + 1)(3k + 2) (k + 1)(3(k + 1) − 1)
= = = =
2 2 2 2

315
Mathematics Grade 12

But this last equation is the equation i itself when n is replaced by k + 1. Hence you have
shown that if the equation is true for k, it is also true for k + 1. By the principle of
Mathematical Induction, this completes the proof that equation i is true for any natural
number n.
Example 6 Prove that for any natural number n, n < 2n.
Proof:
1 First for n = 1, 1 < 21 = 2 is true
2 Assume that n < 2n is true for n ≥ 1.
Now you need to show it is true also for n + 1; that is n + 1 < 2n + 1 is also true.
Adding 1 on both sides of n < 2n, you get
n + 1 < 2n + 1
Again because 1 ≤ 2n for any non-negative integer n, you get:
n + 1 < 2n + 1 ≤ 2n + 2n = 2 (2n) = 2n + 1.
Thus, n + 1 < 2n + 1
That means whenever n < 2n is true, n + 1 < 2n + 1 is also true. In other words,
whenever your assertion is true for a natural number n, it is also true for n + 1.
Therefore, by the principle of mathematical induction, the assertion n < 2n is true
for any natural number n.
Example 7 Use Mathematical Induction to prove that n3 – n is divisible by 3.
Proof:
1 The assertion is true when n = 1 because 13 – 1 = 0 and 0 is divisible by 3.
2 For n = k ≥ 1, assume that k3 – k is divisible by 3 is true for a natural number
k and you must show that this is also true for n = k + 1. That means you
have to show that (k + 1)3 – (k + 1) is divisible by 3.
Now, observe that
(k + 1)3 – (k + 1) = (k3 + 3k2 + 3k + 1) – (k + 1) (expanding (k + 1)3 )
= (k3 – k) + (3k2 + 3k) = (k3 – k) + 3 (k2 + k)
Since by the assumption k3 – k is divisible by 3 and 3 (k2 + k) is clearly divisible by 3,
(as it is 3 times some integer), you notice that the sum (k3 – k) + 3 (k2 + k) is divisible
by 3. Thus, it follows that (k + 1)3 – (k + 1) is divisible by 3. Therefore, by the
principle of mathematical induction, k3 – k is divisible by 3 for any natural number k.

316
 Unit 7 Mathematical Proofs

Exercise 7.4
n (n + 1)
1 Show that 1 + 2 + 3 + . . . + n = , for each natural number n.
2
2 Show that 2 + 4 + 6 + . . . + 2n = n (n + 1) for each natural number n.
3 Find 2 + 4 + 6 + . . . + 100.
4 You may now answer Questions c and d of the opening problem of this unit.
Please try them.
5 A set of boxes are put on top of each other. The upper most row has 6 boxes, the
one below it has 8 boxes, and the next lower rows has 10 boxes and so on. If there
are n rows and 4n + 110 boxes all in all, find the value of n.
6 Prove that the nth even natural number is given by 2n.
7 Prove that the nth odd natural number is given by 2n – 1.
8 Show that 6n – 1 is a multiple of 5. ∀n ∈ ℕ
9 Show that 2n–1 ≤ n! ∀n ∈ ℕ
2
n2 ( n + 1)
10 Show that for all n ∈ ℕ , 13 + 23 + ... + n3 = , n ∈ℕ.
4

Key Terms
argument mathematical induction
bi-implication method of cases (exhaustion)
conclusion negation
conjunction open statement
connective premise
counter example proof by contradiction
direct proof rules of inference
disjunction statement (proposition)
existential quantifier universal quantifier
implication validity
indirect proof (contra positive)

317
Mathematics Grade 12

Summary
1 Rules of connectives: For propositions p and q,
p q ¬p p∧q p∨q p⇒q p⇔q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T
2 Universal quantifier:
∀x means for each x, for any x, for every x or for all x.
3 Existential quantifier:
∃x means for some x or there exists x.
4 ( ∀x ) ( P ( x ) ⇒ Q ( x ) ) : Every P (x ) is Q (x )
5 ( ∃x )( P (x ) ∧ Q (x ) ) : Some P (x ) is Q (x ) and some Q (x) is P(x )
6 ¬ ( ∀x ) P (x ) ≡ ( ∃x )¬ P (x )

7 ¬(∃x)P (x) ≡ (∀x) ¬P (x)

8 An argument is an assertion that a given set of statements called premises yield
another statement called a conclusion.
9 An argument is valid, if whenever all the premises are true, the conclusion is also
true. Otherwise it is called a fallacy .
10 An argument is valid, if and only if the conjunction of all premises always implies
the conclusion.
11 Rules of Inference:
p p∧q
a (Addition) b (Simplification)
p∨q p
p
p⇒q
q
c (conjunction) d p (Modus ponens)
p∧q
q
p⇒q p⇒q
¬q q⇒r
e (Modus Tollens) f (syllogism)
¬p p⇒r

318
 Unit 7 Mathematical Proofs

p∨q
¬p
g (disjunctive syllogism)
q

12 Direct proof:
Given a statement of the form p ⇒ q , proving it using steps
p
p1
p2
..
.
pn
q
where p1, p2 . . . pn are previously established theorems, definitions, postulates
etc, is called a direct proof.
13 Method of cases:
When one proves an assertion by considering all possible cases, the proof is done
by method of cases (exhaustion).
14 Indirect (contra positive) proof
To prove p ⇒ q you can prove its contra positive ¬q ⇒ ¬p .

15 Proof by contradiction
To show that p is true, you seek for an assertion r such that ¬p ⇒ ( r ∧ ¬r ) is true.

16 Disproving by counter example

To show that ( ∀ x ) P ( x ) is false, you seek an object x0 from the universe of P(x0)
such that P(x0) is false (called a counter example).
17 Principle of mathematical induction
If for a given assertion involving a natural number n, you can show that
i the assertion is true for n = 1.
ii if it is true for n = k, then it is also true for n = k + 1;
then the assertion is true for every natural number n.

319
Mathematics Grade 12

Review Exercises on Unit 7

1 Using truth tables, show that each of the following pairs of compound statements
are equivalent.
a p⇒q ;¬p∨q b p ⇔ q ; (p ⇒ q) ∧ (q ⇒ p )
c ¬ (p ∧ q) ; ¬p ∨¬ q d p ∧ (q ∨ r) ; (p ∧ q) ∨ (p ∧ r)
2 Using truth tables, show that each of the following is a tautology.
a (p ∧ q) ⇒ p b p ⇒ (p ∨ q)
c [¬p ∧ (p ∨ q)] ⇒ q d [ p ∧ ( p ⇒ q)] ⇒ q
3 Use quantifiers to express each of the following statements.
a There is a student in this class who can speak French.
b Every student in this class knows how to drive a car.
c There is a student in this class who has a bicycle.
4 Let Q(x, y) be the open proposition "x + y = x – y". If the universal set for x and y
is the set of integers, what are the truth values of the following?
a Q (2, 2) b Q (3, 0) c (∀x) Q(x, 0)
d (∃x) Q(x, 4)) e (∃x) (∃y) Q (x, y) f (∀x) (∀y) Q (x, y)
5 If, the universal set is the set of integers, determine the truth value of each of the
following.
a (∀n) (n2 ≥ 0) b (∃n) (n2 = 2)
c (∀n) (n2 ≥ n) d (∀n) (∃m) (n < m2)
e (∀n) (∃m) (n + m = 0) f (∃n) (∀m) (nm = m)
2 2
g (∃n) (∃m) (n + m = 9) h (∃n) (∃m) (n + m = 6 ∧ n – m = 2)
6 If, the universal set is the set of all real numbers, determine the truth value of each
of the following propositions.
a (∃x) (x2 = 3) b (∃x) (x2 = − 2)
c (∀x) (∃y) (x2 = y) d (∀x) (∀y) (x = y2)
e (∃x) (∀y) (xy = 0) f (∃x) (∃y) (xy ≠ yx)
g (∀x) ≠ 0) (∃y) (xy = 1)
7 Check the validity of each of the following arguments given symbolically.
q ⇒ p p ⇒ ¬q p ⇒ q
¬q ⇔ p p∧ r p ⇒ r
a b c
p ¬q ⇔ r q ⇒ r

320
 Unit 7 Mathematical Proofs

p ⇒ q p ⇒ q p ∨ q
¬p r ⇒ q p
d e f
¬q p ⇒ r ¬q
8 Check the validity of each of the following arguments given verbally.
a If you send me an email message, then I will finish my homework.
If you do not send me an email message, then I will go to sleep early.
If I go to sleep early, then I will wake up early.
Therefore, if I do not finish my homework, then I will wake up early.
b If Alemu has an electric car and he drives a long distance, then his car will
need to be recharged. If his car needs to be recharged, then he will visit an
electric station.
Alemu drives a long distance. However, he will not visit an electric station.
Therefore, Alemu does not have an electric car.
9 Prove or disprove each of the following statements.
a If x and y are odd integers, then xy is an odd integer.
b The product of two rational numbers is always a rational number.
c The product of two irrational numbers is always an irrational number.
d The sum of two rational numbers is always a rational number.
e If n is an integer and n3 + 5 is odd, then n is even.
f For every prime number k, k + 2 is prime.
p +q
g For real numbers p and q , if pq ≠
, then p ≠ q.
2
n n 
h ∀n, r ∈ ℤ and n ≥ r ≥ 2,   =  
r  n − r 
10 Prove each of the following statements by the method of Mathematical Induction,
for all natural numbers n.
n
a 1 + 2 + 2 2 + . . . + 2n = ∑2
k =0
k
= 2 n +1 − 1

n ( n + 1) ( 2n + 1)
b 12 + 22 + 32 + 42 + . . . + n2 =
6
n (n + 1) (n + 2)
c (1 × 2) + (2 × 3) + (3 × 4) + . . . + n (n + 1) =
3
2 2 2 2 n(2n − 1) (2n + 1)
d 1 + 3 + 5 + . . . + (2n – 1) =
3
1 1 1 1 n
e + + + . . . + =
1× 2 2×3 3× 4 n(n + 1) n +1

321