Methods of Proof

Mathematics
Week 2
Methods of Proof
Acknowledgement
<<Title>>
These slides have been adapted
from:
Epp, S.S., 2010. Discrete mathematics with

applications. Cengage learning.
Hammack, R.H., 2013. Book of proof.

Richard Hammack.
LO 1 :
Explain basics concepts of logic,
methods of proof, set theory and
function.
.
Contents
Methods of Proofing
1 Direct Proof
1
2 2
Contrapositive Proof
3 3
Mathematical Induction
. 4 4
Counter Example
A theorem is a mathematical statement that is
true and can be (and has been) verified as
true.
A proof of a theorem is a written verification

that shows that the theorem is definitely and
unequivocally true.
A definition is an exact, unambiguous

explanation of the meaning of a mathematical
word or phrase.
Several Definition in Number Theory
Suppose a and b are integers. We say

that a divides b, written a|b, if b = ac for
An integer n is even if n = 2a for some some c  Z. In this case we also say that
integer a  Z. a is adivisor of b, and that b is a multiple
of a.
Example : 10 is even because 10= 2.5 Example : 5 divides 15 because 15= 5. 3.
We write this as 5|15.
An integer n is odd if n = 2a + 1 for
some integer a  Z. The greatest common divisor of
integers a and b, denoted gcd(a,b), is
Example : 7 =2.3+1 the largest integer that divides both a
and b. The least common multiple of
non-zero integers a and b, denoted
.
A natural number n is prime if it has lcm(a,b), is smallest positive integer
exactly two positive divisors, 1 and n. that is a multiple of both a and b.
Example : gcd(18,24) = 6
Example : is prime, as are 5 and 17. lcm(4,6) = 12,
Methods of Proofing
There are various strategy in methods of proofing :
 Direct Proof
 Contrapositive Proof
 Mathematical Induction
 Counter Example
Direct Proof
In the direct proof, the goal is to show that conditional statement of form
P → Q is true.
Begin by assuming that P is true and show this forces Q to be true.
Outline for Direct Proof
Proposition If P, then Q.
Proof. Suppose P.
…
Therefore Q.
Example
Proposition If x is odd, then x2 is odd.
Proof. Suppose x odd.

Then x =2a+1 for some a  Z, by definition of an odd number.
Thus x2 = (2a+1)2 = 4a2+4a+4a+1=2 (2a2+2a)+1,
so x2 =2b+1 where b = 2a2 +2a  Z.
Therefore x2 is odd, by definition of an odd number.
Contrapositive Proof
We observed that P → Q is logically equivalent to ~Q → ~P .
The expression ~Q → ~P is called the contrapositive form of P → Q .
Outline for Contrapositive Proof
Proposition If P, then Q.
Proof. Suppose ~Q.

…
Therefore ~P.
Example
Proposition Suppose x  Z. If 7x+9 is even, then x is odd.
Proof. Suppose x is not odd.

Thus x is even, so x = 2a for some integer a.
Then 7x+9 = 7(2a)+9 = 14a+8+1 = 2(7a+4)+1.
Therefore 7x+9 =2b+1, where b is the integer 7a+4.
Consequently 7x+9 is odd.
Therefore 7x+9 is not even.
Note :
P : 7x+9 is even Q : x is odd
~P : 7x+9 is not even (odd) ~Q : x is not odd (even)
Mathematical Induction
Mathematical induction is designed to answer when we have a set of
statements S1,S2,S3,...,Sn,..., and we need to prove that they are all true.
To visualize it, think of the statements as dominoes, lined up in a row.
Outline for Proof by Induction
Proposition The statements S1,S2,S3,S≥,... are all true.
Proof. (Induction)
(1) Prove that the first statement S1 is true.
(2) Given any integer k ≥ 1, prove that the statement Sk Sk+1 is true.
It follows by mathematical induction that every Sn is true.

Domino’s Effect
Proposition If n  N, then 1+3+5+7+…+(2n+1) =n2.
Proof. We will prove this with mathematical induction.
(1) Observe that if n = 1, this statement is 1 = 12, which is obviously true.
(2) We must now prove Sk Sk+1 for any k ≥ 1. That is, we must show
that if 1+3+5+7+…+(2k-1) = k2, then 1+3+5+7+…+ 2(k+1)-1) = (k+1)2.
We use direct proof. Suppose 1+3+5+7+…+(2k+1) = k2. Then
Thus 1+3+5+7+…+(2(k+1)-1) = (k+1)2. This proves that Sk Sk+1.

It follows by induction that 1+3+5+7+…+(2n-1)= n2 for every n  N.
Counterexample
As we know, many theorems are universally quantified statements, x  S,
P(x). To disprove this statement, we must prove its negation,
~ (x  S, P(x))=  x  S, ~P(x) .
To prove the negation is true, we just need to produce an example of x  S
that makes ~P(x) true, that is, an x that makes P(x) false.
Outline Counterexample
How to disprove x  S, P(x).

Produce an example of an x  S
that makes P(x) false.
Example
For every n  Z, the integer f (n) = n2 –n+11 is prime.
Disproof. The statement “For every n  Z, the integer f (n) = n2 –n+11 is

prime
,” is false. For a counterexample, note that for n = 11, the integer
f (11) = 121 = 11 . 11 is not prime.
REFERENCES
Epp, S.Susanna., 2010. Discrete mathematics with applications.

Cengage learning.
Hammack, R.H., 2013. Book of proof. Richard Hammack.

Thank You

Methods of Proof

Uploaded by

Copyright:

Available Formats

Methods of Proof

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Methods of Proof

Uploaded by

Copyright:

Available Formats

Mathematics

Epp, S.S., 2010. Discrete mathematics with

Hammack, R.H., 2013. Book of proof.

A proof of a theorem is a written verification

A definition is an exact, unambiguous

Suppose a and b are integers. We say

There are various strategy in methods of proofing :

Outline for Direct Proof

Proposition If x is odd, then x2 is odd.

Proof. Suppose x odd.

Outline for Contrapositive Proof

Proof. Suppose ~Q.

Proof. Suppose x is not odd.

Outline for Proof by Induction

Proposition The statements S1,S2,S3,S≥,... are all true.

It follows by mathematical induction that every Sn is true.

Thus 1+3+5+7+…+(2(k+1)-1) = (k+1)2. This proves that Sk Sk+1.

How to disprove x  S, P(x).

Disproof. The statement “For every n  Z, the integer f (n) = n2 –n+11 is

Epp, S.Susanna., 2010. Discrete mathematics with applications.

Hammack, R.H., 2013. Book of proof. Richard Hammack.

You might also like