Methods of Proof

This Lecture

Now we have learnt the basics in logic.

We are going to apply the logical rules in proving mathematical theorems.

• Direct proof

• Contrapositive

• Proof by contradiction

• Proof by cases
 Basic Definitions

An integer n is an even number

if there exists an integer k such that n = 2k.

An integer n is an odd number

if there exists an integer k such that n = 2k+1.
 Proving an Implication

Goal: If P, then Q. (P implies Q)

Method 1: Write assume P, then show that Q logically follows.

Claim: If , then

Reasoning: When x=0, it is true.

When x grows, 4x grows faster than x 3 in that range.

Proof:

When
 Direct Proofs

The sum of two even numbers is even.

Proof x = 2m, y = 2n
x+y = 2m+2n
= 2(m+n)

The product of two odd numbers is odd.

Proof x = 2m+1, y = 2n+1

xy = (2m+1)(2n+1)
= 4mn + 2m + 2n + 1
= 2(2mn+m+n) + 1.
 Divisibility

a “divides” b (a|b):

b = ak for some integer k

5|15 because 15 = 35

n|0 because 0 = n0
1|n because n = 1n
n|n because n = n1

A number p > 1 with no positive integer divisors other than 1 and itself
is called a prime. Every other number greater than 1 is called composite.

2, 3, 5, 7, 11, and 13 are prime,

4, 6, 8, and 9 are composite.
 Simple Divisibility Facts

1. If a | b, then a | bc for all c.

2. If a | b and b | c, then a | c.
3. If a | b and a | c, then a | sb + tc for all s and t.
4. For all c ≠ 0, a | b if and only if ca | cb.

Proof of (1)
a|b
Þ b = ak a “divides” b (a|b):

Þ bc = ack b = ak for some integer k

Þ bc = a(ck)
Þ a|bc
 Simple Divisibility Facts

1. If a | b, then a | bc for all c.

2. If a | b and b | c, then a | c.
3. If a | b and a | c, then a | sb + tc for all s and t.
4. For all c ≠ 0, a | b if and only if ca | cb.

Proof of (2)
a | b => b = ak1
a “divides” b (a|b):
b | c => c = bk2
b = ak for some integer k
=> c = ak1k2
=> a|c
 Simple Divisibility Facts

1. If a | b, then a | bc for all c.

2. If a | b and b | c, then a | c.
3. If a | b and a | c, then a | sb + tc for all s and t.
4. For all c ≠ 0, a | b if and only if ca | cb.

Proof of (3)
a | b => b = ak1
a “divides” b (a|b):
a | c => c = ak2
b = ak for some integer k
sb + tc
= sak1 + tak2

= a(sk1 + tk2)
=> a|(sb+tc)
 This Lecture

• Direct proof

• Contrapositive

• Proof by contradiction

• Proof by cases
 Proving an Implication

Goal: If P, then Q. (P implies Q)

Method 1: Write assume P, then show that Q logically follows.

Claim: If r is irrational, then √r is irrational.

How to begin with?

What if I prove “If √r is rational, then r is rational”, is it equivalent?

Yes, this is equivalent;

proving “if P, then Q” is equivalent to proving “if not Q, then not P”.
 Rational Number
R is rational  there are integers a and b such that

numerator

and b ≠ 0.

denominator

Is 0.281 a rational number? Yes, 281/1000

Is 0 a rational number? Yes, 0/1

If m and n are non-zero integers, is (m+n)/mn a rational Yes

number?
Yes, a/b+c/d=(ad+bc)/bd
Is the sum of two rational numbers a rational number?
Note that 100x-x=12, and so x=12/99.
Is x=0.12121212…… a rational number?
 Proving an Implication

Goal: If P, then Q. (P implies Q)

Method 2: Prove the contrapositive, i.e. prove “not Q implies not P”.

Claim: If r is irrational, then √r is irrational.

Proof: We shall prove the contrapositive –

“if √r is rational, then r is rational.”

Since √r is rational, √r = a/b for some integers a,b.

So r = a2/b2. Since a,b are integers, a2,b2 are integers.

Therefore, r is rational. Q.E.D.

(Q.E.D.) "which was to be demonstrated", or “quite easily done”. 

 Proving an “if and only if”

Goal: Prove that two statements P and Q are “logically equivalent”,

that is, one holds if and only if the other holds.

Example:
An integer is even if and only if the its square is even.

Method 1: Prove P implies Q and Q implies P.

Method 1’: Prove P implies Q and not P implies not Q.

Method 2: Construct a chain of if and only if statement.

 Proof the Contrapositive

An integer is even if and only if its square is even.

Method 1: Prove P implies Q and Q implies P.

Statement: If m is even, then m2 is even

Proof: m = 2k

m2 = 4k2

Statement: If m2 is even, then m is even

Proof: m2 = 2k

m = √(2k)

??
 Proof the Contrapositive

An integer is even if and only if its square is even.

Method 1’: Prove P implies Q and not P implies not Q.

Statement: If m2 is even, then m is even

Contrapositive: If m is odd, then m2 is odd.

Proof (the contrapositive):

Since m is an odd number, m = 2k+1 for some integer k.

So m2 = (2k+1)2

= (2k)2 + 2(2k) + 1

So m2 is an odd number.
 This Lecture

• Direct proof

• Contrapositive

• Proof by contradiction

• Proof by cases
 Proof by Contradiction

PF
P
To prove P, you prove that not P would lead to ridiculous result,
and so P must be true.

You are working as a clerk.

If you have won the lottery, then you would not work as a clerk.
You have not won the lottery.
 Proof by Contradiction

Theorem: 2 is irrational.

Proof (by contradiction):

• Suppose 2 was rational.

• Choose m, n integers without common prime factors (always
possible) such that m
2
n
• Show that m and n are both even, thus having a common factor 2,
a contradiction!
 Proof by Contradiction

Theorem: 2 is irrational.

Proof (by contradiction): Want to prove both m and n are even.

m so can assume m  2l
2
n
m 2  4l 2
2n  m
2n 2  4l 2
2n 2  m 2 n 2  2l 2
so m is even. so n is even.
 Infinitude of the Primes
Theorem. There are infinitely many prime numbers.

Proof (by contradiction):

Assume there are only finitely many primes.

Let p1, p2, …, pN be all the primes.

We will construct a number N so that N is not divisible by any p i.

By our assumption, it means that N is not divisible by any prime number.

On the other hand, we show that any number must be divisible by some prime.

It leads to a contradiction, and therefore the assumption must be false.

So there must be infinitely many primes.

 Divisibility by a Prime
Theorem. Any integer n > 1 is divisible by a prime number.

• Let n be an integer.

• If n is a prime number, then we are done.

• Otherwise, n = ab, both are smaller than n.

• If a or b is a prime number, then we are done.

• Otherwise, a = cd, both are smaller than a.

• If c or d is a prime number, then we are done.

• Otherwise, repeat this argument, since the numbers are

getting smaller and smaller, this will eventually stop and
we have found a prime factor of n.

Idea of induction.
 Infinitude of the Primes
Theorem. There are infinitely many prime numbers.

Proof (by contradiction):

Let p1, p2, …, pN be all the primes.

Consider p1p2…pN + 1.

Claim: if p divides a, then p does not divide a+1.

Proof (by contradiction):

a = cp for some integer c

a+1 = dp for some integer d
=> 1 = (d-c)p, contradiction because p>=2.

So none of p1, p2, …, pN can divide p1p2…pN + 1, a contradiction.

 This Lecture

• Direct proof

• Contrapositive

• Proof by contradiction

• Proof by cases
 Proof by Cases

e.g. want to prove a nonzero number always has a positive square.

x is positive or x is negative

if x is positive, then x2 > 0.

if x is negative, then x2 > 0.

x2 > 0.
 The Square of an Odd Integer

Idea 0: find counterexample.

32 = 9 = 8+1, 52 = 25 = 3x8+1 …… 1312 = 17161 = 2145x8 + 1, ………

Idea 1: prove that n2 – 1 is divisible by 8.

n2 – 1 = (n-1)(n+1) = ??…

Idea 2: consider (2k+1)2

(2k+1)2 = 4k2+4k+1
If k is even, then both k2 and k are even, and so we are done.

If k is odd, then both k2 and k are odd, and so k2+k even, also done.
 Trial and Error Won’t Work!
Fermat (1637): If an integer n is greater than 2,

then the equation an + bn = cn has no solutions in non-zero integers a, b, and c.

Claim: has no solutions in non-zero integers a, b, and c.

False. But smallest counterexample has more than 1000 digits.

Euler conjecture:

has no solution for a,b,c,d positive integers.

Open for 218 years, until Noam Elkies found

958004  2175194  414560 4  4224814

 The Square Root of an Even Square

Statement: If m2 is even, then m is even

Contrapositive: If m is odd, then m2 is odd.

Proof (the contrapositive):

Since m is an odd number, m = 2l+1 for some natural number l.

So m2 = (2l+1)2

= (2l)2 + 2(2l) + 1

So m2 is an odd number.

Proof by contrapositive.
 Rational vs Irrational

Question: If a and b are irrational, can ab be rational??

We know that √2 is irrational, what about √2 √2 ?

Case 1: √2√2 is rational

Then we are done, a=√2, b=√2.

Case 2: √2√2 is irrational

Then (√2√2)√2 = √22 = 2, a rational number

So a=√2√2, b= √2 will do.

So in either case there are a,b irrational and a b be rational.

We don’t (need to) know which case is true!

 Summary

We have learnt different techniques to prove mathematical statements.

• Direct proof

• Contrapositive

• Proof by contradiction

• Proof by cases

Next time we will focus on a very important technique, proof by induction.