1

TECHNOLOGICAL UNVERSITY OF THE PHILIPPINES

COLLEGE OF SCIENCE
MATHEMATICS DEPARTMENT

COURSE CODE: CS213 WEEK/ DURATION

COURSE TITLE: COMBINATORICS WITH GRAPH THEORY

MODULE 4.0: METHODS OF PROVING THEOREM II

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 four includes proof by cases, counterexample, existence proofs, and disproving existence statements. 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 4: Methods of Theorems II Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY 2020-2021
 2

LESSON PROPER
4.0 Proof by Cases
To give a proof of a mathematical statement concerning an element x in some set S, it is useful to observe that x posseses one of two or more
properties. A common property which x may possesses belong to a particular subset of S . The truthfulness of the statement may be verify regardless of which
of these properties x may have, will result to a proof of statement. Proof of statement is then divided into parts called cases, one case for each property that x
may possess or for each sub2: set to which x may belong. This method is called proof by cases. And proof of cases may further divide a case in other cases,
called subcases.

Illustration 4.1 a) In a proof of ∀ n ∈ Z , R ( n ), it is convenient to use a proof of cases whose proof is divided into two cases.

Case 1: n is even and Case 2: n is odd.

b) Other possible proofs by cases involve in proving ∀ x ∈ R , P ( x ), using the cases

Case 1: x=0 , Case 2: x <0 , and Case 3: x >0

c) To attempt to prove ∀ n ∈ N , P ( n ), using the cases

Case 1:n=1 and Case 2: n ≥ 2

d) Moreover, for S− { 0 }, and to prove ∀ x , y ∈ S , P ( x , y ) by using the cases, and the cases into subcases

Case 1: xy >0 and Case 2: xy <0

Case 1 can be divided again into two subcases:

Subcase 1.1: x >0 and y >0 and Subcase 1.2: x <0 and y <0 ;

likewise, Case 2 could be divided into two subcases:

Subcase 2.1: x >0 and y <0 and Subcase 2.2: x <0 and y >0 ;

Example 4.2 If n ∈ Z ,then n2 +3 n+5 is an odd integer.

Proof Use the proof by cases, that is, whenever n is even or odd.

Case 1: n is even. Then n=2 x for some x ∈ Z . So

2 2
n +3 n+5=( 2 x ) +3 ( 2 x ) +5
CS 213 Combinatorics with Graph Theory Module 4: Methods of Theorems II Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY 2020-2021
 3

n2 +3 n+5=4 x2 +6 x +5

n2 +3 n+5=4 x2 +6 x +4 +1

n2 +3 n+5=2 ( 2 x 2 +3 x+ 2 ) +1.
Since (2 x 2+3 x +2)∈ Z , the integer n2 +3 n+5 is odd.

Case 2: n is odd. Then n=2 y+1 for some y ∈ Z . So

2 2
n +3 n+5=( 2 y+ 1 ) +3 ( 2 y +1 )+ 5

n2 +3 n+5=4 y 2+ 4 y +1+6 y +3+5

n2 +3 n+5=4 y 2+10 y + 9

n2 +3 n+5=4 y 2+10 y +8+ 1

n2 +3 n+5=2 ( 2 y 2 +5 y + 4 ) +1
Since (2 y 2+ 5 y + 4)∈ Z , then n2 +3 n+5 is odd. ∎
Remark 4.3 Two integers x and y are said to be of the same parity if x and y are both even or are both odd. The integers x and y are of opposite parity if one
of x and y is even and the other is odd. Since the definition of two integers having the same (or opposite) parity requires the two integers to satisfy one of two
properties, any result containing these terms is likely to prove by cases.

Example 4.4 Let x , y ∈ Z . Then x and y are of the same parity if and only if x + y is even.

a) Direct Proof

Proof Assume that x and y are of the same parity. Consider two cases.

Case1: x and y are even. Then x=2 a and y=2b for some x , y ∈ Z . Thus,

x + y=2 a+2 b
x + y=2 ( a+b )
Since (a+ b)∈ Z , the integer x + y is even.
CS 213 Combinatorics with Graph Theory Module 4: Methods of Theorems II Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY 2020-2021
 4

Case 2: x and y are odd. Then x=2 a+1 and y=2b+ 1 for some x , y ∈ Z . Thus

x + y=(2 a+1)+(2 b+1)

x + y=2 a+2 b+2
x + y=2(a+b+1)
Since (a+ b+1 ¿ ¿∈ Z , the integer x + y is even. ∎
b) Proof by Contradiction

Proof Assume that x and y are of opposite parity. Again, consider two cases:

Case 1: x is even and y is odd. Then x=2 a and y=2b+ 1 for some x , y ∈ Z . Thus

x + y=(2 a)+(2 b+1)

x + y=2 a+2 b+1
x + y=2(a+b)+1
Since (a+ b ¿∈ Z , the integer x + y odd. Which is a contradiction.

Case 2: x is odd and y is even. Then x=2 a+1 and y=2b for some x , y ∈ Z . Thus

x + y=(2 a+1)+(2 b)
x + y=2 a+2 b+1
x + y=2(a+b)+1
Since (a+ b ¿∈ Z , the integer x + y odd. Which is a contradiction. ∎
It was observed that the proof of the two cases are similar. In this case, the proof of Case 2 can be omitted. Hence the alternative for the proof by
contradiction is considered.

Alternative Proof Assume that x and y are of opposite parity. WLOG, assume that x is even and y is odd. Then

x=2 a and y=2b+ 1 for some x , y ∈ Z . Thus

x + y=(2 a)+(2 b+1)
CS 213 Combinatorics with Graph Theory Module 4: Methods of Theorems II Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY 2020-2021
 5

x + y=2 a+2 b+1

x + y=2(a+b)+1
Since (a+ b ¿∈ Z , the integer x + y odd. Which is a contradiction. ∎
Remark 4.5 The phrase WLOG (without loss of generality) is used to indicate that the two proofs of the two situations are similar, and only one proof is needed.

Example 4.6 Let a and b are integers. Then ab is even if and only if a is even or b is even.

a) Direct Proof

Proof Assume that a is even or b is even. WLOG, let a be even. Then a=2 x for some integer x . Hence

ab=( 2 x ) b=2(xb)
Since ( xb ) ∈ Z , then ab is even. ∎
b) Proof by Contradiction

Proof Assume to the contrary that a is odd and b is odd. WLOG, let a be even. Then a=2 x+1and b=2 y+ 1

where x , y ∈ Z . Hence

ab=( 2 x+1 ) (2 y +1)

ab=4 xy+ 2 x +2 y+ 1
ab=2(2 xy + x+ y)+1
Since ( 2 xy+ x+ y ) ∈ Z , then ab is odd. ∎

Example 4.7 Let x ∈ Z . If 3 ∤ ( x 2−1 ) , then 3∨x .

Proof Using proof by contrapositive. Assume that 3 ∤ x . Then either x=3 q+ 1 or x=3 q+ 2, where q ∈ Z . Consider two cases.

Case 1: x=3 q+ 1 for some q . Then

x 2−1=( 3 q +1 )2−1

x 2−1=9 q2 +6 q+ 1−1

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

x 2−1=3 (3 q¿¿ 2+2 q) ¿

Since (3 q ¿¿ 2+ 2q)¿ is an integer, 3∨x2 −1.

Case 2: x=3 q+ 2 for some q . Then

x 2−1=( 3 q +2 )2−1

x 2−1=9 q2 +12 q+ 4−1

x 2−1=3 (3 q¿¿ 2+ 4 q+1)¿

Since (3 q ¿¿ 2+ 4 q +1)¿ is an integer, then 3∨x2 −1.
∎
The following section consider problems that involve directly or indirectly, quantified statements involving existential quantifiers, that is, statements of
the type ∃ x ∈ S , R ( x ) .

4.1 Counterexamples
Some quantified statements of the type ∀ x ∈ S , R ( x ) is false. Its negation is equivalent to

¿ R ( x )) ≡∃ x ∈ S , R( x )
that is, if the statement ∀ x ∈ S , R ( x ) is false, then there exists some element x ∈ S for which R ( x ) is false. Such an element is called a counterexample of the
(false) statement ∀ x ∈ S , R ( x ). Finding a counterexample verifies that
∀ x ∈ S , R ( x ) is false.

Example 4.1.1 Consider the statement:

2
If x ∈ R , then ( x 2−1 ) >0 ,
or, equivalently,
2
For every real number x , ( x 2−1 ) >0 ,

Show that the statement is false by giving a counterexample.

2 2
Solution: For x=1 , ( x 2−1 ) =( 12−1 ) =0. Hence x=1 is a counterexample. Similarly, for x=−1.

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

For the statement to be true, then the new statement will be

2
If x ∈ R− {−1,1 } , then ( x 2−1 ) >0 ,

Example 4.1.2 Disprove the statement:

If n is an odd integer, then n2 −n is odd.

Solution For the odd integer n=1 , then integer n2 −n=12 −1=0, 0 is an even integer. Thus,n=1 is a counterexample.

Example 4.1.3 Disprove the statement:

For every odd positive integer n , 3∨n2−1.

Solution: If n=3 ,3∨32−1 , but 3 ∤7 . It follows that n=3 is counterexample.

4.2 EXISTENCE PROOFS

In an existence theorem, the existence of an object(objects) possessing some specified property or properties is asserted. An existence theorem
concerning an open sentence R(x ) over a domain S can be expressed as a qualified statement

∃ x ∈ S , R ( x ) ,that is, there exits x ∈ S such that R ( x ).

The statement is true provided that R ( x ) is true for some x ∈ S . A proof of an existence theorem is called an existence proof. An existence proof may then
consist of displaying or constructing an example of such an object or with the aid of known results, verifying that such objects must exist without ever producing
a single example of the desired type.

Example 4.2.1 There exists an integer whose cube equals its square.

Proof Since 13=12=1 , the integer 1 has the desired property.

Alternative Proof Let x ∈ Z such that

2
x 3=x 2; x 3−x 2=0 ; x ( x−1 ) =0 ;
Equating each factor to zero: x 2=0 ; x=0 | x−1=0 ; x =1.
Obviously, there are only two integers with this desired property, 1 and 0. ∎

Example 4.2.2 There exists real numbers a∧b such that ( a+ b )2=a 2+ b2 .

Proof Let a , b ∈ Z such that ( a+ b )2=a 2+ b2 . It follows that

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

a 2+2 ab+ b2=¿ a 2+b 2

a 2+2 ab+ b2−¿ a 2−b2=0
2 ab=0.
Since a=1 ,b=0 is a solution to this equation,
( a+ b )2=a 2+ b2
( 1+0 )2=12 +0 2
1=1
2 2 2
Therefore ( a+ b ) =a + b . ∎
2 2 2
Remark 4.2.5 The proof of Example 4.2.2 illustrates that all real numbers a and b for which ( a+ b ) =a + b is true if and only if at least one of a∧b
is zero.

4.3 Disproving Existence Statements

Let R ( x ) be a statement for each element x in domain S . In module 3, to disapprove a quantified statement of the type ∀ x ∈ S , R ( x ) , it is enough
to produce a counterexample(that is, an element x in S for which R ( x ) is false). Meanwhile, disproving a quantified statement of the type ∃ x ∈ S , R ( x )
requires different approach. Since
( ∃ x ∈ S , R ( x) ) ≡ ∀ x ∈ S , R ( x ) .

Thus, the statement ∃ x ∈ S , R ( x ) is false if R ( x ) for every x ∈ S .

Example 4.3.1 Disprove the statement: There exists an odd integer n such that n2 +2 n+3 is odd.

Solution Show that if n is an odd integer, then n2 +2 n+3 is even. Let n be an odd integer. Then n=2 k +1 for some integer k . Hence,
2 2
n +2 n+3=( 2 k +1 ) + 2 ( 2 k +1 ) +3
n2 +2 n+3=4 k 2 +4 k +1+4 k +2+3
n2 +2 n+3=4 k 2 +8 k +6
n2 +2 n+3=2(2 k ¿¿ 2+4 k +3) ¿

Since (2 k ¿¿ 2+ 4 k +3) ¿ is an integer, n2 +2 n+3 is even.

Note that R ( x ) :n 2+2 n+3 is odd and its negation, R ( x ) :n2 +2 n+3 is even. Hence ( ∃ x ∈ S , R ( x) ) ≡ ∀ x ∈ S , R ( x ), that is, Example 4.3.1 can be replaced as
“For every odd integer n , n2 +2 n+3 is even.” And it will be a true statement.
CS 213 Combinatorics with Graph Theory Module 4: Methods of Theorems II Prepared by: Editha Rivera-Jorda, Ph.D.
1st semester SY 2020-2021
 9

Example 4.3.2 Disprove the statement: There exits an integer n , such that n3 −n+1 is even.

Solution: Let n ∈ Z . Consider two cases.

Case 1. n is even. Then n=2 a, where a ∈ Z . So
n3 −n+1= (2 a )3 −(2 a)+1
n3 −n+1=8 a3−2 a+1
n3 −n+1=2( 4 a¿¿ 3−a)+1 ¿
Since ( 4 a¿¿ 3−2 a)∈ Z ¿, n3 −n+1 is odd and so it is not even.

Case 2: n is odd. Then n=2 b+1, where b ∈ Z . So

n3 −n+1= (2 b+1 )3 −(2 b+1)+1
n3 −n+1=8 b3 +12b 2+ 6 b+1−2 b−1+1
n3 −n+1=8 b3 +12b 2+ 4 b +1
n3 −n+1=2(4 b ¿ ¿ 3+6 b2 +2 b)+1¿

Since ¿ ¿, n3 −n+1 is odd and so it is not even.

Note that R ( x ) :n3 −n+1 is even and its negation, R ( x ) :n3 −n+1 is odd. Hence ( ∃ x ∈ S , R ( x) ) ≡ ∀ x ∈ S , R ( x ), that is, Example 4.3.2 can be replaced as
“For every integer n , n2 +2 n+3 is odd.” And it will a true statement for both cases.

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

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

Exercise for 4.0 – 4.3

Direction: Please answer Exercises 4.0 – 4.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

A. Disprove the following statements:

1. If a and b are any two real numbers, then log ( ab )=log a+ log b.

2. If n ∈ { 0,1,2,3,4 } ,then 3∨( 2n2 +1 ).

3. For every two positive integers a and b , ( a+ b )3=a3+ 2 a2 b+ 2 ab+2 a b2 +b3 .

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

4. There exist odd integers a and b such that 4∨( 3 a2 +7 b2 ) .

5. There is an integer a such that n 4 +n3 +n2 +n is odd.

B. Show that there exits:

6. a rational number a and an irrational number such that a b is irrational.
7. two distinct irrational numbers a and b such that a b is rational.

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