Unit 4

Proof Methods

Proof Methods 4-1

The Pigeonhole Principle
 Suppose that you have n
pigeonholes.
 Suppose that you have
m pigeons, where m > n.
 If you put the m pigeons
into the n pigeonholes,
some pigeonhole will o n = 9 pigeonholes
o m = 10 pigeons
have more than one o Some pigeonhole has
pigeon in it. more than one pigeon.

Is it true? How to prove it?

Proof Methods 4-2
Outline of Unit 4
 4.1 Why Proofs?
 4.2 Validity of Arguments in Predicate Logic
 4.3 Direct Proofs Mathematical
 4.4 Indirect Proofs proofs

Proof Methods 4-3

Unit 4.1

Why Proofs?

Proof Methods 4-4

What is a Proof?
 A proof is a valid argument that establishes the
truth of a statement.
 If the statement is about mathematical objects (integers,
triangles, sets, etc.), then it is a mathematical proof.
 In this unit, we study proofs in predicate logic and
mathematical proofs.
 In mathematical proofs,
 more than one rule of inference is often used in a step,
 steps may be skipped, and
 the rules of inference may not be explicitly stated.

Proof Methods 4-5

Do We Need Proofs?
Mathematics consists
in proving the most
obvious thing in the
least obvious way.

How about
engineers?

George Polya, Toba Beta,

a Hungarian an Indonesian
mathematician poet.
Proof Methods 4-6
Should EE Students Learn Proofs?
 My personal opinion:

Engineering students should learn to

discover, understand, and enjoy proofs.

 Why?
 A way to convince oneself and others that a proposed
engineering solution indeed works.
• Network protocols, cryptographic protocols, database
management, optimality of a (hardware/software) system, etc.
 A sign of understanding.
• Problem solving relies on deep understanding of a problem.
 An intellectual challenge full of fun.
 An art for appreciation.
Proof Methods 4-7
Unit 4.2

Validity of Arguments in Predicate Logic

Proof Methods 4-8

Enlarging the Domain
 Quantified statements are in the form of
∀𝑥𝑥 ∈ 𝐷𝐷1 , 𝑃𝑃 𝑥𝑥 or ∃𝑥𝑥 ∈ 𝐷𝐷2 , 𝑄𝑄 𝑥𝑥

 When there are multiple quantified statements,

it is often more convenient to enlarge different
domains to a common universal set.
 e.g., when 𝐷𝐷1 is the set of all cats and 𝐷𝐷2 is the set of
all birds, we may let 𝑈𝑈 be the set of all animals.

Proof Methods 3-9

Universal Conditional Statements
 Consider the statement “All cats have four legs.”
 We can express it as
∀𝑥𝑥 ∈ 𝐷𝐷, 𝐿𝐿 𝑥𝑥 , where
 𝐷𝐷 is the set of all cats, and 𝐿𝐿(𝑥𝑥) is “𝑥𝑥 has four legs.”

 Alternatively, we can also express it as

∀𝑥𝑥 ∈ 𝑈𝑈, 𝐶𝐶 𝑥𝑥 → 𝐿𝐿 𝑥𝑥 , where
 𝐶𝐶(𝑥𝑥) is “𝑥𝑥 is a cat.”

Proof Methods 3-10

Existential Conjunctive Statements
 Consider the statement “Some birds are angry.”
 We can express it as
∃𝑥𝑥 ∈ 𝐷𝐷, 𝐴𝐴 𝑥𝑥 , where
 𝐷𝐷 is the set of all birds, and 𝐴𝐴(𝑥𝑥) is “𝑥𝑥 is angry.”

 Alternatively, we can also express it as

∃𝑥𝑥 ∈ 𝑈𝑈, 𝐵𝐵 𝑥𝑥 ∧ 𝐴𝐴 𝑥𝑥 , where
 𝐵𝐵(𝑥𝑥) is “𝑥𝑥 is a bird.”

Proof Methods 3-11

Symbolic Translation
Statement Form Symbolic Translation
All 𝑆𝑆 are 𝑃𝑃. ∀𝑥𝑥, 𝑆𝑆(𝑥𝑥) → 𝑃𝑃(𝑥𝑥)

No 𝑆𝑆 are 𝑃𝑃. ∀𝑥𝑥, 𝑆𝑆 𝑥𝑥 → ~𝑃𝑃 𝑥𝑥

Some 𝑆𝑆 are 𝑃𝑃. ∃𝑥𝑥, 𝑆𝑆(𝑥𝑥) ∧ 𝑃𝑃(𝑥𝑥)

Some 𝑆𝑆 are not 𝑃𝑃. ∃𝑥𝑥, 𝑆𝑆 𝑥𝑥 ∧ ~𝑃𝑃(𝑥𝑥)

When the domain refers to the universal set and is clear from the context,
it can be omitted in the quantified statements.

Proof Methods 3-12

Proof of Validity in Predicate Logic
 To prove arguments consisting of quantified
statements, we need to use
 logical equivalence, and
• (discussed in Units 2 and 3)

 rules of inference for propositional logic, and

• (discussed in Unit 3)

 rules of inference for quantified statements

• Universal Instantiation (UI) UMP, UMT
• Universal Generalization (UG)
• Existential Instantiation (EI) 4 basic rules
• Existential Generalization (EG)

Proof Methods 4-13

Universal Instantiation (UI)
 If some property is true of  This rule allows you to
everything in a set, then it i. apply a universal
is true of any arbitrary statement to a
thing in the set. particular object;
 e.g., as in UMP, UMT
ii. remove the universal
∀𝑥𝑥 ∈ 𝐷𝐷, 𝑃𝑃(𝑥𝑥) quantifier and use an
arbitrary object to
represent the
𝑃𝑃(𝑎𝑎) for any arbitrary 𝑎𝑎 ∈ 𝐷𝐷 statement.
 This allows us to
apply inference rules
of propositional logic.

Proof Methods 4-14

Example: UI
All men are mortal. ∀𝑥𝑥 𝑀𝑀(𝑥𝑥) → 𝑂𝑂(𝑥𝑥)
Socrates was a man. 𝑀𝑀(𝑆𝑆)
Socrates was mortal. 𝑂𝑂(𝑆𝑆)

Proof:
(1) ∀𝑥𝑥 𝑀𝑀 𝑥𝑥 → 𝑂𝑂 𝑥𝑥 (premise)
(2) 𝑀𝑀(𝑆𝑆) (premise)
(3) 𝑀𝑀 𝑆𝑆 → 𝑂𝑂 𝑆𝑆 (UI 1) //apply to a particular object (Socrates)
(4) 𝑂𝑂 𝑆𝑆 (MP)
Proof Methods 4-15
Universal Modus Ponens (UMP)
 Universal instantiation can be combined with
Modus Ponens.
∀𝑥𝑥 ∈ 𝐷𝐷, 𝑃𝑃(𝑥𝑥) → 𝑄𝑄(𝑥𝑥)
𝑃𝑃(𝑎𝑎) for a particular 𝑎𝑎
𝑄𝑄(𝑎𝑎)

All men are mortal. ∀𝑥𝑥, 𝑀𝑀(𝑥𝑥) → 𝑂𝑂(𝑥𝑥)

Socrates was a man. 𝑀𝑀(𝑆𝑆)
Socrates was mortal. 𝑂𝑂(𝑆𝑆)
Proof Methods 4-16
Universal Modus Tollens (UMT)
 Universal instantiation can be combined with
Modus Tollens.

∀𝑥𝑥 ∈ 𝐷𝐷, 𝑃𝑃(𝑥𝑥) → 𝑄𝑄(𝑥𝑥)

~𝑄𝑄(𝑎𝑎) for a particular 𝑎𝑎
~𝑃𝑃(𝑎𝑎)

Validity can be shown in a similar way.

Proof Methods 4-17

Example: UMT
All muggles can’t perform magic.
(∀𝑥𝑥, if 𝑥𝑥 is a muggle, 𝑥𝑥 can’t perform magic.)

Harry Potter can perform magic.

Harry Potter, a fictional
character.
Harry Potter isn’t a muggle.

“In the Harry Potter book series, a Muggle is a person

who lacks any sort of magical ability and was not
born in a magical family.” – Wikipedia.
Proof Methods 4-18
Universal Generalization (UG)
 If some property is true of  This rule allows you
any arbitrary thing in a set, to move from an
arbitrary object to a
then it is true of everything
universal statement
in the set.  Used often implicitly
in mathematical
proofs.
𝑃𝑃(𝑠𝑠) for an arbitrary 𝑠𝑠 ∈ 𝐷𝐷

∀𝑥𝑥 ∈ 𝐷𝐷, 𝑃𝑃(𝑥𝑥)

Proof Methods 4-19

Example: UG
All elephants are mammals. ∀𝑥𝑥 𝐸𝐸(𝑥𝑥) → 𝑀𝑀(𝑥𝑥)
All mammals are animals. ∀𝑥𝑥 𝑀𝑀(𝑥𝑥) → 𝐴𝐴(𝑥𝑥)
All elephants are animals. ∀𝑥𝑥 𝐸𝐸(𝑥𝑥) → 𝐴𝐴(𝑥𝑥)

Proof:
(1) ∀𝑥𝑥, 𝐸𝐸 𝑥𝑥 → 𝑀𝑀 𝑥𝑥 (premise)
(2) ∀𝑥𝑥, 𝑀𝑀(𝑥𝑥) → 𝐴𝐴(𝑥𝑥) (premise)
(3) 𝐸𝐸 𝑦𝑦 → 𝑀𝑀 𝑦𝑦 (UI 1; 𝑦𝑦 is arbitrary)
(4) 𝑀𝑀(𝑦𝑦) → 𝐴𝐴(𝑦𝑦) (UI 2; 𝑦𝑦 is arbitrary)
(5) 𝐸𝐸 𝑦𝑦 → 𝐴𝐴 𝑦𝑦 (HS 3, 4)
(6) ∀𝑥𝑥 𝐸𝐸(𝑥𝑥) → 𝐴𝐴(𝑥𝑥) (UG 5)
Proof Methods 4-20
Existential Generalization (EG)
 If some property is true of a  This rule allows you
particular thing in a set, then to move from a
particular object to
there exists a thing in the set
an existential
that has the property. statement.

𝑃𝑃(𝑐𝑐) for a particular 𝑐𝑐 ∈ 𝐷𝐷.

∃𝑥𝑥 ∈ 𝐷𝐷, 𝑃𝑃(𝑥𝑥).

Proof Methods 4-21

Example: EG
All logicians are mathematicians. ∀𝑥𝑥 𝐿𝐿(𝑥𝑥) → 𝑀𝑀(𝑥𝑥)
Gödel is a logician. 𝐿𝐿(𝐺𝐺)
There is a mathematician. ∃𝑥𝑥 𝑀𝑀(𝑥𝑥)

Proof:
(1) ∀𝑥𝑥 𝐿𝐿 𝑥𝑥 → 𝑀𝑀 𝑥𝑥 (premise)
(2) 𝐿𝐿(𝐺𝐺) (premise)
(3) 𝑀𝑀(𝐺𝐺) (UMP 1, 2)
(4) ∃𝑥𝑥 𝑀𝑀(𝑥𝑥) (EG 3)

Proof Methods 4-22

Existential Instantiation (EI)
 If some property is true of  This rule allows
something in a set, then it is you to move
from a particular
true of a particular thing in the
object to an
set. existential
statement.
∃𝑥𝑥 ∈ 𝐷𝐷, 𝑃𝑃(𝑥𝑥)

𝑃𝑃(𝑐𝑐) for a particular 𝑐𝑐 ∈ 𝐷𝐷.

Proof Methods 4-23

Example: EI
All EE students are CityU students. ∀𝑥𝑥 𝐸𝐸 𝑥𝑥 → 𝐶𝐶 𝑥𝑥
Some EE students are musicians. ∃𝑥𝑥 𝐸𝐸 𝑥𝑥 ∧ 𝑀𝑀(𝑥𝑥)
Some musicians are CityU students. ∃𝑥𝑥 𝑀𝑀 𝑥𝑥 ∧ 𝐶𝐶(𝑥𝑥)

Proof:
(1) ∀𝑥𝑥 𝐸𝐸 𝑥𝑥 → 𝐶𝐶 𝑥𝑥 (premise)
(2) ∃𝑥𝑥 𝐸𝐸 𝑥𝑥 ∧ 𝑀𝑀(𝑥𝑥) (premise)
(3) 𝐸𝐸 𝑎𝑎 ∧ 𝑀𝑀(𝑎𝑎) (EI 2; 𝑎𝑎 is a particular object)
(4) 𝐸𝐸 𝑎𝑎 (S 3)
(5) 𝐶𝐶(𝑎𝑎) (UMP 1,4)
(6) 𝑀𝑀(𝑎𝑎) (S 3) UG can’t be used
(7) 𝑀𝑀 𝑎𝑎 ∧ 𝐶𝐶(𝑎𝑎) (C 4, 6) because 𝑎𝑎 is not an
(8) ∃𝑥𝑥 𝑀𝑀 𝑥𝑥 ∧ 𝐶𝐶(𝑥𝑥) (EG 7) arbitrary object.
Proof Methods 4-24
Class Work
1) If you enjoy watching a movie, you
love the lead actress of it.
2) You enjoy watching Harry Potter.
3) If you love the lead actress of Harry
Hermione Granger, a fictional
Potter, then you love the lead actress character in Harry Potter.
of Beauty and the Beast.

You must enjoy watching Beauty and

the Beast.

Belle, a fictional character in

Beauty and the Beast.
Is it valid? Why or why not?
Proof Methods 4-25
Analysis
1) ∀𝑥𝑥, 𝑒𝑒(𝑥𝑥) → 𝑙𝑙(𝑥𝑥) (Premise 1)
2) 𝑒𝑒(𝐻𝐻) (Premise 2)
3) 𝑙𝑙(𝐻𝐻) → 𝑙𝑙(𝐵𝐵) (Premise 3)
4) 𝑙𝑙(𝐻𝐻) (UMP 1,2)
5) 𝑙𝑙(𝐵𝐵) (MP 3,5)
6) 𝑒𝑒(𝐵𝐵) → 𝑙𝑙(𝐵𝐵) (UI 1)

The argument is invalid.

We can’t conclude from lines 5 and 6 that 𝑒𝑒 𝐵𝐵 is
true, since “affirming the consequent” is a fallacy.
Proof Methods 4-26
Classwork
1. A person without a dream is
like a salted fish.
2. Martin Luther King is not ≉
like a salted fish.
Martin Luther King has a dream.

Prove its validity.

𝑑𝑑(𝑥𝑥): 𝑥𝑥 has a dream

𝑓𝑓(𝑥𝑥): 𝑥𝑥 is like a salted fish
domain: the set of all persons

Proof Methods 4-27

Classwork: Is Death a Bad Thing?
 This is a speech of Socrates from Apology.
 “For Death is to be as it were nothing, and to be
deprived of all sensation... And if no sensation remains,
then death is like a dreamless sleep. In this case, death
will be a blessing. For, if anyone compares such a night
as this, in which he so profoundly sleeps as not even to
see a dream, with the other nights and days of his life,
and should declare how many he had passed better and
more pleasantly than this night, I think that not only a
private man, but even the great king himself, would find
so small a number that they might be easily counted.”
See next page…
Proof Methods 4-28
Classwork: Socrates’s Argument
1) Death is to be deprived of
all sensation.
2) Anything without sensation
is like a dreamless sleep.
3) Anything like a dreamless
sleep is better than most days
and nights.
4) Anything better than most
days and nights is a blessing.
Death is a blessing.

Is it valid? If so, prove it.

Proof Methods 4-29
Unit 4.3

Direct Proofs

Proof Methods 4-30

Terminology
 Definition
 a precise description of a mathematical term (e.g. odd number).
 Axiom
 A statement assumed true without proof.
 Axioms form a basic building block from which all theorems are
proved.
 Theorem
 a mathematical statement that is proved to be true using rigorous
reasoning (i.e. rules of inference).
 Lemma
 a minor result whose purpose is to help in proving a theorem.
• Very occasionally, some lemmas are very important on their own.
 Corollary
 a result whose (usually short) proof follows directly from a theorem.

Proof Methods 4-31

Forms of Theorems
 Many theorems assert that a property holds for
all elements in a domain, such as the integers, the
real numbers, the triangles, the sets.
 The universal quantifier is, however, often omitted.

 Example:
“If x > y, where x and y are positive real numbers, then x2 > y2.”

can be written as the following universal statement:

“∀𝑥𝑥, 𝑦𝑦 ∈ 𝑅𝑅+ , if 𝑥𝑥 > 𝑦𝑦, then 𝑥𝑥 2 > 𝑦𝑦 2 .”

Proof Methods 4-32

Direct Proofs
 A way of showing the truth of a statement by
using established facts (e.g. definition, lemmas,
theorems), rules of inference, and logical
equivalences.
 Proving Existential Statements
 Proof by example
 Proving Universal Statements
 Proof by exhaustion (a.k.a proof by cases)
 Proof by UG

Proof Methods 4-33

Proving Existential Statements
 Consider an existential statement
∃𝑥𝑥 ∈ 𝐷𝐷, 𝑄𝑄(𝑥𝑥).

Proof by example
Find an 𝑥𝑥 in 𝐷𝐷 that makes 𝑄𝑄(𝑥𝑥) true.

 Validity follows from Existential Generalization

(EG).

Proof Methods 4-34

Disproving Universal Statements
 Consider a universal statement
∀𝑥𝑥 ∈ 𝐷𝐷, 𝑄𝑄(𝑥𝑥).
 That it is false is equivalent to that its negation
is true.
∃𝑥𝑥 ∈ 𝐷𝐷, ~𝑄𝑄(𝑥𝑥).

Proof by counter-example
Find an 𝑥𝑥 in 𝐷𝐷 that makes 𝑄𝑄(𝑥𝑥) false.

Proof Methods 4-35

One Example is Enough
 It is easy to find an example to prove that
There exists positive integers a, b, c such that
𝑎𝑎2 + 𝑏𝑏 2 = 𝑐𝑐 2 .
 It can be proved by giving an example:
32 + 42 = 52

 Euler’s conjecture (1769):

Given any positive integers a, b, c, d, we must have
𝑎𝑎4 + 𝑏𝑏 4 + 𝑐𝑐 4 ≠ 𝑑𝑑 4 .
 It was disproved in 1986 by a counter-example:
28624404 + 153656394 + 187967604 = 206156734

Proof Methods 4-36

Cutting Figures
 Congruent pieces: of the same shape and size,
possibly rotated or flipped over.
 Prove that this figure can be cut into 2 congruent
pieces.
Too easy? How
about cutting into
4 congruent pieces?

Proof Methods 4-37

Methods to Prove Universal Statements

 Consider a universal statement

∀𝑥𝑥 ∈ 𝐷𝐷, 𝑄𝑄(𝑥𝑥).
1. Proof by Exhaustion (also called Proof by Cases)
a) Split the domain D into a finite number of cases (i.e.
subsets).
b) Check that the statement is true for each case (i.e.
𝑄𝑄(𝑥𝑥) for all 𝑥𝑥 in each subset.)
2. Proof by Universal Generalization (UG)
a) Pick an arbitrary element 𝑥𝑥 in D.
b) Show that 𝑥𝑥 has the property Q.

Proof Methods 4-38

Examples (Proof by Exhaustion/Cases)
1. Prove that 𝑥𝑥 2 ≤ 16 for 1 ≤ 𝑥𝑥 ≤ 4, 𝑥𝑥 is an integer.
Solution:
 12 = 1 ≤ 16, 22 = 4 ≤ 16, 32 = 9 ≤ 16, 42 = 16 ≤ 16.
Q.E.D.

2. Prove that min(𝑥𝑥, 𝑦𝑦) ≤ max(𝑥𝑥, 𝑦𝑦), where 𝑥𝑥, 𝑦𝑦 ∈ 𝑅𝑅.

Solution:
 Case 1: 𝑥𝑥 ≤ 𝑦𝑦. Then min 𝑥𝑥, 𝑦𝑦 = 𝑥𝑥 ≤ 𝑦𝑦 = max(𝑥𝑥, 𝑦𝑦).
 Case 2: 𝑥𝑥 > 𝑦𝑦. Then min 𝑥𝑥, 𝑦𝑦 = 𝑦𝑦 ≤ 𝑥𝑥 = max(𝑥𝑥, 𝑦𝑦).
Q.E.D.
Proof Methods 4-39
Even and Odd Integers
 Before we give an example to explain the proof
method based on UG, we need the following:
 Definition
 The integer 𝑛𝑛 is even if there exists an integer 𝑘𝑘 such
that 𝑛𝑛 = 2𝑘𝑘, and
 𝑛𝑛 is odd if there exists an integer 𝑘𝑘 such that 𝑛𝑛 = 2𝑘𝑘 + 1.

• Note that every integer is either even or odd, and no integer is

both even and odd.

Proof Methods 4-40

Example (Proof by UG)
Theorem: Given any integer 𝑛𝑛, if 𝑛𝑛 is even, then 𝑛𝑛2 is even.
 For a direct proof of 𝑃𝑃 → 𝑄𝑄, we assume the truth of P and show
the truth of Q necessarily follows.
Proof: Let 𝑛𝑛 be an (arbitrary) even numbers.
By the definition of even numbers, we can express it as
𝑛𝑛 = 2𝑘𝑘, where 𝑘𝑘 is an integer.
Then, 𝑛𝑛2 = 4𝑘𝑘 2 = 2(2𝑘𝑘 2 ).
Since 2𝑘𝑘 2 is an integer, 𝑛𝑛2 is even.
Hence, (by UG), the statement is true.
Q.E.D.

Proof Methods 4-41

Example (Proof by UG)
Theorem: The sum of any two even numbers is even.
(Given any two numbers, if they are even, then their sum is even.)

Proof: Let 𝑚𝑚 and 𝑛𝑛 be two (arbitrary) even numbers.

By the definition of even numbers, 𝑚𝑚 = 2𝑟𝑟 and 𝑛𝑛 = 2𝑠𝑠 for some integers 𝑟𝑟
and 𝑠𝑠.

Let 𝑡𝑡 = 𝑟𝑟 + 𝑠𝑠. Then

By the definition of even numbers, 𝑚𝑚 + 𝑛𝑛 is even.

Hence, (by UG), the sum of any two even numbers is even.

Q.E.D.
Proof Methods 4-42
Rational Numbers
 Definition:
 A real number 𝑟𝑟 is rational if there exists integers 𝑎𝑎
𝑎𝑎
and 𝑏𝑏 such that 𝑟𝑟 = and 𝑏𝑏 ≠ 0.
𝑏𝑏
 Otherwise, the real number 𝑟𝑟 is irrational.
 Examples:
2 22
• Rational numbers: −1, 0, , 3, , 25
3 7
3
• Irrational numbers: 2, 7, 𝜋𝜋

 The set of rational numbers is denoted by ℚ.

Proof Methods 4-43

Exercise
Prove that the sum of any two rational numbers is
rational.
Solution:

Proof Methods 4-44

Exercise
Prove that 𝑛𝑛2 + 𝑛𝑛 is even for any integer 𝑛𝑛.
 Hint: Use the method of cases, and then apply UG to each case.
Solution:

Proof Methods 4-45

Unit 4.4

Indirect Proofs

Proof Methods 4-46

 Indirect Proofs (Two Major Types)

Proof by Contradiction Proof by Contraposition

 Used to prove a  Use to prove a conditional
proposition 𝑝𝑝. statement 𝑝𝑝 → 𝑞𝑞.
 Based on the following  Based on the following
logical equivalence: logical equivalence:

𝑝𝑝 ≡ (~𝑝𝑝 → 𝐜𝐜) 𝑝𝑝 → 𝑞𝑞 ≡ ~𝑞𝑞 → ~𝑝𝑝

Assume 𝑝𝑝 is false, and Prove its contrapositive.

then show that it leads Assume ~𝑞𝑞 is true, and
to a contradiction. then show that ~𝑝𝑝 is true.

Why? ~𝑝𝑝 → 𝐜𝐜 ≡ ~~𝑝𝑝 ∨ 𝐜𝐜 ≡ 𝑝𝑝 ∨ 𝐜𝐜 ≡ 𝑝𝑝

Proof Methods 4-47
Example (Proof by Contradiction)
Theorem: There is no greatest integer.

Proof: We prove by contradiction. Suppose there is

a greatest integer 𝑁𝑁. Then 𝑁𝑁 ≥ 𝑘𝑘 for all integer 𝑘𝑘.
Let 𝑀𝑀 = 𝑁𝑁 + 1. Now 𝑀𝑀 is an integer and 𝑀𝑀 > 𝑁𝑁.
Therefore, 𝑁𝑁 is not a greatest integer.
We have reached a contradiction.
Hence, the statement is true.
Q.E.D.
Proof Methods 4-48
Example (Proof by Contraposition)
Theorem: Given any integer n, if n2 is even, then n is
even.
Proof: Suppose 𝑛𝑛 is not even.
We can express 𝑛𝑛 = 2𝑘𝑘 + 1 for some integer 𝑘𝑘.
Then,
𝑛𝑛2 = (2𝑘𝑘 + 1)2 = 4𝑘𝑘 2 + 4𝑘𝑘 + 1 = 2 2𝑘𝑘 2 + 2𝑘𝑘 + 1
Then, 𝑛𝑛2 = 2𝑡𝑡 + 1. 𝑡𝑡 is an integer
Therefore, 𝑛𝑛2 is odd (i.e., not even).
Hence, the statement is proved.
Q.E.D.
Proof Methods 4-49
Exercise
Prove that if 7𝑥𝑥 + 9 is even, then 𝑥𝑥 is odd.

Proof Methods 4-50

Proof of Biconditional Statement
 To prove a biconditional statement 𝑝𝑝 𝑞𝑞, we
usually make use of the following logical
equivalence:

𝑝𝑝 𝑞𝑞 ≡ (𝑝𝑝 → 𝑞𝑞) ∧ (𝑞𝑞 → 𝑝𝑝)

Prove the Prove its

conditional converse
𝑝𝑝 → 𝑞𝑞. 𝑞𝑞 → 𝑝𝑝.

Proof Methods 4-51

Example
Prove that for any integers 𝑥𝑥 and 𝑦𝑦, the product 𝑥𝑥𝑥𝑥 is
even if and only if 𝑥𝑥 is even or 𝑦𝑦 is even.

Solution:
[First part]
We first prove that if 𝑥𝑥 is even or 𝑦𝑦 is even, then 𝑥𝑥𝑥𝑥 is
even, using a direct proof.
Suppose 𝑥𝑥 is even, i.e., 𝑥𝑥 = 2𝑘𝑘 for some integer k.
Then, 𝑥𝑥𝑥𝑥 = 2𝑘𝑘 𝑦𝑦 = 2(𝑘𝑘𝑘𝑘), which is even.
Suppose 𝑦𝑦 is even. Similarly, we can also prove that
𝑥𝑥𝑥𝑥 is even. [As the steps are similar, they are omitted.]
Proof Methods 4-52
[Second part]
Next, we prove the converse:
“if 𝑥𝑥𝑥𝑥 is even, then 𝑥𝑥 is even or 𝑦𝑦 is even.”
We use proof by contraposition.
The contrapositive of the above statement:
“if 𝑥𝑥 is odd and 𝑦𝑦 is odd, then 𝑥𝑥𝑥𝑥 is odd.”
Let both 𝑥𝑥 and 𝑦𝑦 be odd, i.e.,
𝑥𝑥 = 2𝑚𝑚 + 1 and 𝑦𝑦 = 2𝑛𝑛 + 1,
for some integers 𝑚𝑚 and 𝑛𝑛.
Then, 𝑥𝑥𝑥𝑥 = 2𝑚𝑚 + 1 2𝑛𝑛 + 1
= 4𝑚𝑚𝑚𝑚 + 2𝑚𝑚 + 2𝑛𝑛 + 1
= 2 2𝑚𝑚𝑚𝑚 + 𝑚𝑚 + 𝑛𝑛 + 1, which is odd.
Q.E.D.
Proof Methods 4-53
Theorem: 2 is Irrational.
 Why does it matter?
 https://www.youtube.com/watch?v=nT4geKdKVfw (~5 min.)

Proof Methods 4-54

Proof (by Contradiction):
𝑎𝑎
Suppose 2 = where a and b are integers. We can
,
𝑏𝑏
assume that a and b have no common factors.
 Otherwise, we can cancel out the common factors.
𝑎𝑎2
Squaring both sides, 2 = 2 , or 2𝑏𝑏 2 = 𝑎𝑎2 .
𝑏𝑏
Therefore, 𝑎𝑎2 is even ⇒ a is even (by the theorem in p.49).
We can write a as 2k, where k is an integer.
Then, 2𝑏𝑏 2 = 𝑎𝑎2 = 4𝑘𝑘 2 , or 𝑏𝑏 2 = 2𝑘𝑘 2 .
Therefore, 𝑏𝑏 2 is even ⇒ b is even.
This contradicts with the assumption that a and b
have no common factor.
Q.E.D.
Proof Methods 4-55
The Pigeonhole Principle (revisited)
 There are 𝑚𝑚 pigeons and 𝑛𝑛
pigeonholes, where 𝑚𝑚 > 𝑛𝑛.
 Some pigeonhole will have
more than one pigeon.

Theorem: Let 𝑚𝑚 objects be distributed into 𝑛𝑛 bins.

If 𝑚𝑚 > 𝑛𝑛, then some bin contains more than one object.

[If 𝑚𝑚 > 𝑛𝑛, ∃ a bin that contains more than one object.]

Proof Methods 4-56

Theorem: Let 𝑚𝑚 objects be distributed into 𝑛𝑛 bins.
If 𝑚𝑚 > 𝑛𝑛, then some bin contains more than one object.

Proof:
Assume that every bin contains no more than one object. We
want to prove 𝑚𝑚 ≤ 𝑛𝑛. (proof by contraposition)
Let 𝑥𝑥𝑖𝑖 be the number of objects in bin 𝑖𝑖.
Since each bin contains no more than one object, 𝑥𝑥𝑖𝑖 ≤ 1.
Since m is the number of objects, we have
𝑚𝑚 = 𝑥𝑥1 + 𝑥𝑥2 + ⋯ + 𝑥𝑥𝑛𝑛
≤ 1 + 1 +⋯ + 1
= 𝑛𝑛.
Hence, 𝑚𝑚 ≤ 𝑛𝑛, as required.
Q.E.D.
Proof Methods 4-57
Recommended Reading
 Sections 3.4, 4.1-4.7, Susanna S. Epp,
Discrete Mathematics with
Applications, 4th ed., Brooks Cole,
2010.

Proof Methods 4-58