1

TECHNOLOGICAL UNVERSITY OF THE PHILIPPINES

COLLEGE OF SCIENCE
MATHEMATICS DEPARTMENT
COURSE CODE: CS213

COURSE TITLE: COMBINATORICS WITH GRAPH THEORY

MODULE 3.0: METHODS OF PROVING THEOREM 1

Learning Outcome: At the end of the module, the students are expected to:
1. develop a proof strategy,

2. construct the proof,

3. do a proof analysis.

Overview of the Module

The contents of the module three includes the mathematical definitions of axiom, theorem, corollary, lemma and conjecture, definition of even and odd
integer and its properties, divisibility of integers, congruence of integers, and some facts about real numbers, the three proof techniques such as: direct proof,
indirect proof (proof by contrapositive), and proof by contradiction. The student output is to develop a proof a strategy, construct a proof and do the proof
analysis.

References:
1. Rosen, K. (2004). Discrete Mathematics and Its Application. McGraw-Hill Companies, Inc. New York, New York.
(5th ed).

2. Chartrand, G., Polimeni, A. D., Zhang, P. (2008). Mathematical Proofs: A Transition to Advanced Mathematics. Pearson Education, Inc. Boston, MA. (2 nd
edition).

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 2

LESSON PROPER
3.0 Introduction
Proving theorem can be difficult. This section introduces a battery of different proof methods. These methods should be become a part of repertoire for
proving theorems. Many theorems are implications, the techniques for proving implications are important. Recall that,

p ⇒ q is true unless p is true and q is false.

It was noted that when the statement p ⇒q is proved, it needs to be shown that q is true if p is true.

Recall some of the mathematical definitions and topic which are familiar.

Definition 3.1 A true mathematical statement whose truth is accepted without proof is referred to as axiom.

Definition 3.2 A theorem is a statement that can be shown to be true, sometimes it is called propositions, facts, or results. It can be demonstrated to be true
with a sequence of statements that form an argument, called proof. Also, a theorem is a true mathematical statement whose truth can be verified.

Definition 3.3 A corollary is a mathematical result that can be deducted from, and thereby a consequence of, some earlier result. Furthermore, a corollary is a
proposition that can be established directly from a theorem that has been proved.

Definition 3.4 A lemma is a mathematical result that is useful in establishing the truth of some other result. It can also be called as helping theorem (English
translation of the German word “hilsatz”). Thus, a lemma is a simple theorem used in the proof of other theorems.

Definition 3.5 A conjecture is a statement whose truth value is unknown. When a proof of a conjecture is found, it becomes a theorem.

The following definition of odd and even integers; divisibility of integers; congruence of integers and facts about real numbers will be recalled because
they are essential before an example of several proofs is discussed.

Definition 3.6 The integer n is even if there exists an integer k such that n=2 k and it is odd, if there exists an integer k such that n=2 k +1. Note that an integer
is either even or odd. That is,

S= { 2 k|k ∈ Z }={ … ,−4 ,−2,0,2,4 , … }

T ={ 2 k +1|k ∈ Z }= { … ,−5 ,−3 ,−1,3,5 , … }
Observe that S and T are disjoint sets and S ∪ T =Z ; that is, Z is portioned into S and T . Therefore, every integer is either odd or even.

3.6.1 Properties of Integers:

1. The negative of every integer is an integer.

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 3

2. The sum (difference) of every two integers is an integer.

3. The product of every two integers is an integer.

3.6.2 Divisibility of Integer

Definition 3.6.2 For integers a and b with a ≠ 0, a divides b if there is n integer such that b=ac . Its notation is a¿ b.
If a¿ b, then b is a multiple of a and that a is a divisor ofb .

Example 3.6.2.1 4∨48 since 48=4∗12 and −3∨57 since (−3 )∗(−19 ). However, 4 ∤66 since there is no integer c such that 66=4 c .

3.6.3 Congruence of Integers

Definition 3.6.3 For integers a , b , and n ≥ 2, a is congruent to b modulo n , written as a ≡ b mod ( n ) ,if n∨( a−b ) .

Example 3.6.3.1 15 ≡7(mod 4) , since 4∨ (15−7 ) =4∨8 ; 3 ≡−15(mod 9) , since 9∨3− (−15 )=9∨18. But,

14 ≢ 4 (mod 6), since 6 ∤ ( 14−6 )=6 ∤8

Remark 3.6.3.2 Every integer x can be expresses as be expressed as x=2 q or x=2 q+1 for some integer q .

Thus, 2∨ ( x−0 ), that is, x ≡ 0(mod 2) and 2∨ ( x−1 ) is equivalently to x ≡ 1 ( mod 2 ) .

Moreover, since each integer x can be expressed as x=3 q or x=3 q+ 1 for some integer q .

Then, 3∨( x−0 ) , that is , x ≡0 ( mod 3 ) ; 3∨( x−1 ), that is, x ≡ 1(mod 3); 3∨( x−2 ), that is, x ≡ 2(mod 3)

Similar statements can also made when x is divided by n for each integer n ≥ 4.

3.6.4 Some Facts about Real Numbers

1. a 2 ≥ 0 for every real number a .

2. a n ≥ 0 for every real number n if n is a positive even integer.

3. If a< 0 and n is a positive odd integer, then a n ¿ 0.

4. The product of two real numbers is positive if and only if both numbers are positive or both are negative.

5. If the product of two real numbers is zero, then at least one of these numbers is zero.

6. Let a , b , c ∈ R. If a ≥ b and c ≥0 , then the inequality ac ≥bc holds.

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 4

a b
If c >0 ,then ≥ .
c c
a b
If a> b and c >0 , then ac >bc and > .
c c
If c <0 ,then the above inequalities are reversed; namely:

a b
If a> b and c <0 , then ac <bc and < .
c c
The following shows the most common techniques for proving implications.

3.1 Direct Proofs

The implication p ⇒ q can be proven by showing that if p is true, then q must also be true. A proof of this kind is called direct proof. To carry out
such a proof, assume that p is true and use rules of inference and theorems already proved to show that q must also be true.

Example 3.1.2 Give a direct proof of the theorem” If n is odd integer, then n2 is odd.”

Proof: Assume that n is odd. Sincen is odd, then rewrite n=2 n+k for some integer k . It follows that
2 2
n =( 2n+ k )
n2 =4 k 2+ 4 k +1
n2 =2 ( 2 k 2+2 k )+ 1
Since 2 k 2 +2 k is an integer, then n2 is odd. ∎
Example 3.1.3 “If n is odd integer, then 3 n+7 is an even integer.”

Proof: Assume that n is odd integer. Since n is odd, rewrite n=2 k +1 for some integer k . Thus,

3 n+7=3 ( 2 k +1 ) +7
3 n+7=6 k +3+ 7
3 n+7=6 k +10
3 n+7=2 ( 3 k +5 )
Since 3 k +5 is an integer, then3 n+7 is an even integer. ∎

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 5

Example 3.1.4 “If n is an even integer, then −5 n−3 is an odd integer.”

Proof: Assume that n is an even integer. Since n is even, rewrite n=2 k for some integer k . It follows that,

−5 n−3=−5 ( 2 k ) −3
−5 n−3=−10 k −3
−5 n−3=−10 k −4 +1
−5 n−3=(−10 k −4 ) +1
−5 n−3=2 (−5 k −2 )+ 1
−5 n−3=2 (−5 k −2 )+ 1
Since −5 k −2 is an integer, then −5 n−3 is an odd integer. ∎
Example 3.1.5 “If is an even integer, then 3 n5is an even integer. “

Proof: Since n is an integer, n=2 x for some integer k . Therefore,

5 5
3 n =3 ( 2 x )

3 n5=3 ( 32 x 5 )=96 x 5=2 ( 48 x 5 )

Since 48 x 5 ∈ Z , the integer 3 n5 is even. ∎
Example 3.1.6 Let a , b and c be integers with a ≠ 0 and b ≠ 0. If a∨b and b∨c , then a∨c .

Proof Assume that a∨b and b∨c . Then b=ax and c=by , where x , y ∈ Z .

c= ( ax ) y=a ( xy )
Since xy is an integer, then a∨c . ∎
Example 3.1.7 Let a , b , c , and d be integers with a ≠ 0 and b ≠ 0. If a∨c and b∨d , then ab∨cd .

Proof Let a∨c and b∨d . Then c=ax and d=by , where x , y ∈ Z . Then

cd =( ax )( by ) =(ab)( xy )

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 6

Since, xy is an integer, then ab∨cd . ∎

Example 3.1.8 Let a , b , k , and n be integers, where n ≥ 2. If a ≡ b(mod n), then ka ≡ kb( mod n).

Proof Assume that a ≡ b(mod n). Then n∨a−b. Thus, a−b=nx for some integer . Therefore,

ka−kb=k ( a−b )=k (nx)

ka−kb=k (nx)
ka−kb=n (kx)
Since kx is an integer, n∨ka−kb . Hence, ka ≡ kb( mod n). ∎
Example 3.1.8 Let a , b , k , n ∈ Z , where n ≥ 2. If a ≡ b(mod n) and c ≡d ( mod n ) , then a+ c ≡ b+d ( mod n )

Proof Assume that a ≡ b(mod n) and c ≡d ( mod n ) . Then n∨a−b and n∨c−d . Hence, a−b=nx and c−d=ny for some integers x and y . Adding these two
equations,

( a−b ) + ( c−d )=nx +ny

a−b+ c−d=n( x+ y)
( a+ c )−( b+ d )=n ( x+ y )
Since x + y is an integer and n∨¿ Therefore, a+ c ≡ ( b+d ) ( mod n ) . ∎
Example 3.1.9 Let x ∈ R . If x 3−5 x 2+3 x=15 , then x=5.

Proof Assume that x 3−5 x 2+3 x=15 . Then x 3−5 x 2+3 x−15=0. Observe that

( x 3−5 x 2 ) + ( 3 x−15 )=0

x 2 ( x−5 )+3 ( x−5 )=0

( x−5 ) + ( x 2 +3 ) =0
By Factor Theorem,
( x 2 +3 )=0 and x−5=0
However, x 2+ 3≥ 0 , x−5=0 implies that x=5. ∎
CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 7

3.2 Indirect Proof (Proof by Contrapositive)

Since the implication p ⇒ q is equivalent to its contrapositive, that is, ( p ⇒ q ) ≡( q ⇒ p), the implication
p ⇒q can be proved by showing that its contrapositive q ⇒ p is true. An argument of this type is called indirect proof.
Example 3.2.1 Give an indirect proof of the theorem “If 3 n+2 is odd , then n is odd .”
Proof Assume that the conclusion of this implication is false; namely assume that n is even. Then n=2 k for some integer k . It follows that

3 n+2=3 (2 k )+ 2
3 n+2=6 k +2
3 n+2=2(3 k +1)
Since 3 k +1 is an integer, then 3 n+2 is even, therefore not odd. Because the negation of the conclusion of the implication implies that the hypothesis is false,
and the original implication is true.

Example 3.2.2 Prove that if n is an integer and n2 is odd, then n is odd by indirect proof.

Proof Suppose n is even. This implies that n=2 k for some integer k . Observe that

n2 =( 2 k )2

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

Since ( 2 k 2 ) is an integer, it follows that n2 is even and therefore not odd. Because the negation of the conclusion of the implication implies that the hypothesis is
false, and the original implication is true. ∎
Example 3.2.3 Let x , y ∈ Z , If 3 ∤ xy , then 3 ∤ x and 3 ∤ y by indirect proof.

Proof Assume that 3∨x∨3∨ y . Without loss of generality(WLOG), assume that 3 divides x .Then x=3 z for some integer z . Hence

xy=( 3 z ) y=3 ( zy ) .
Since zy is an integer, then 3∨xy . ∎

3.3 Proof of Contradiction

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 8

Suppose that a contradiction can be found so that p ⇒ q is true, that is, p ⇒ F is true. Then the proposition p must be false. It follows, p must be true.
This technique can be used when a contradiction, such as r ∧∼r , can be found so that it is possible to show that the implication ∼ p ⇒ ( r ∧∼ r ) is true. An
argument of this type is called a proof of contradiction.

Note: In a proof by contraction, begin by assuming that the statement is false and attempt to show that this leads to contradiction.

Example 3.3.1 Show that at least four of any 22 days must fall on the same day of the week.

Proof Let p be a proposition “At least four of the 22 chosen days are on the same day of the week.”

Suppose ∼ p is true. Then at most three of the 22 days are the same day of the week.

Because there are seven days of the week, this implies that at most 21 days could have been chosen since three is the most days chosen that could be a
particular day of the week. This is a contradiction.

Example 3.3.2 Prove that √ 2 is irrational by giving proof of contradiction.

Proof Let p be the proportion “√ 2is irrational .”

Suppose ∼ p is true. Then √ 2is rational .

a a
Under the assumption that √ 2 is rational, there exist integer a and b such that √ 2= , where a and b have no common factor. Since √ 2= , when both
b b
sides are squared, it follows that

a 2 a2
(
( √ 2=
b ) ; 2= 2 ; 2 b2=a2
b
This means that a 2 is even, implying that a is even. Furthermore, since a is even, a=2 c for some integer c. Thus,

2 b2=4 c 2 ; b 2=2 c2
This means that b 2 is even. Hence b is even. ∎
a
Remark 3.3.3 It has been shown that ∼ p implies that √ 2= ,where a and b have no common factors, and 2 divides a and b . This is a contradiction since we
b
have shown that ∼ p implies bothr and ∼ r wherer is the statement that a and b are integers with no common factors. Hence ∼ p is false, so that “√ 2 is
rational” is true.

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 9

Example 3.3.4 There is no smallest possible positive real numbers.

r r
Proof Assume to the contrary, that there is a smallest positive real number, say r . Since 0< < r , it follows that is a positive real number that is smaller than r .
2 2
This is however a contradiction. ∎

Example 3.3.5 If a is an even integer and b is an odd integer, then 4 ∤ ( a 2+2 b 2) .

Proof Assume to the contrary, that there exists an even integer a and an odd integer b such that 4∨( a2 +2 b2 ). Thus,

a=2 x , b=2 y +1 , ( a2 +2 b2 ) =4 z for some integer x , y ,∧z .

Hence a 2+2 b2 =4 z
( 2 x )2 +2 ( 2 y+1 )2 =4 z

4 x2 +2 ( 2 y 2+ 4 y +1 ) =4 z

4 x2 + 4 y 2 +8 y +2=4 z

2=4 z−4 x 2−4 y 2−8 y

2=4 ( z−x 2− y2 −2 y )
Since 4 x2 + 4 y 2 +8 y is an integer, 4∨2 which is impossible. ∎

Remark 3.3.6 Begin assuming that there exists an even integer a and an odd integer b such that 4∨(a ¿ ¿ 2+2 b2 ) ¿. Then deduced that 4∨2 , which is a false
statement and thereby produced a desired contradiction.

The following table summarizes how to start a proof and what the goal should be.
TABLE 1: The Three Basic Methods of Proof Techniques
First step of the “Proof” Remarks/Goal
1 A direct proof is used.
Assume that P is true. Show that Q is true.
2 Assume that P is false. A mistake has been made.
3 Assume that Q is true. A mistake has been made.
A proof by contrapositive (indirect proof) is used.
4 Assume that Q is false. Show that P is false.

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 10

5 Assume that P is true and Q is true. A mistake has been made.

A proof by contradiction is being used.
6 Assume that P is true and Q is false. Obtain a contradiction.
7 Assume that P is false and Q is true. A mistake has been made.
8 Assume that P is false and Q is false. A mistake has been made.
9 Assume that P ⇒ Q is true. A mistake has been made.
A proof by contradiction is being used.
10 Assume that P ⇒ Q is false. Obtain a contradiction.

The following example illustrates the three proof techniques:

Example 3.3.7 If n is an even integer, then 3 n+7 is odd.

Direct Proof: Let n be an integer. Then n=2 x for some integer x . Therefore,

3 n+7=3 ( 2 x ) +7
3 n+7=6 x+ 7
3 n+7=6 x+ 6+¿1
3 n+7=2(3 x+ 3)+1
Since 3 x+ 3 is an integer, 3 n+7 is odd.` ∎
Indirect Proof: Assume that 3 n+7 is even. Then 3 n+7=2 y for some integer y . Hence
n=( 3 n+7 ) +(−2 n−7)
n=2 y−2 n−7
n=2 y−2 n−8+ 1
n=2 ( y −n−4 )+ 1 2
Since y−n−4 is an integer, n is odd. ∎
Proof by Assume, to the contrary, that there exists an even integer n such that 3 n+7 is even. Since n is even,
Contradiction n=2 x for some integer x . Hence
3 n+7=3 ( 2 x ) +7
3 n+7=6 x+ 7
3 n+7=6 x+ 6+1
CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 11

3 n+7=( 6 x+ 6 ) +1
3 n+7=2 ( 3 x +3 ) +1

Since 3 x+ 3 is an integer, 3 n+7 is odd. Which is a contradiction. ∎

Surname, Name: __________________________Course &Sec.:________ Module No: _________________ Date of Submission: ___

Exercise for 3.0 – 3.3

Direction: Please answer Exercises 3.0 – 3.3 and submit based on the following requirements:
 Use proper paging for each copy (for example 1/5).
 Write your answer after each question on a clean bond paper.
 Answer should be handwritten.
 Scan your answer.
 Send to the President of the class before the dateline, so that the President can consolidate the exercise to be submitted.
Start Here

1. Prove that there is no largest negative rational number.

2. Let m∈ Z

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 12

a. Give a direct proof of the following: If 3∨m ,then 3∨m 2 .

b. State the contrapositive of the implication in (a).

c. Give a direct proof of the following: If 3 ∤m ,then 3 ∤m 2

d. State the contrapositive of the implication in(c).

3. Let a , b , c , n∈ Z , where n ≥ 2. Prove that a ≡ b(mod n) and a ≡ c ( mod n ) , then b=c (mod n).

4. Let a , b , c , m∈ Z . Prove that if 2 a+3 b ≥ 12m+1 , then a ≥ 3 m+1 or b ≥ 2 m+1.

5. Prove by contradiction that the product of an irrational and a nonzero rational number is irrational.

6. Prove that if n is an odd integer, then 7 n−5 is even by (a) direct proof, (b) proof by contrapositive, and (c) proof by contradiction.

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 13

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 14

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 15

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 16

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021
 17

CS 213 Combinatorics with Graph Theory Module 3: Methods of Proving Theorems Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY: 2020-2021