Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

King Saud University

College of Sciences
Department of Mathematics

151 Math Exercises

(3,1)
Methods of Proof
1-Direct Proof
2- Proof by Contraposition
3- Proof by Contradiction
4- Proof by Cases
By:

Malek Zein AL-Abidin

‫ه‬
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

Direct Proof: A direct proof shows that a conditional statement p q is true by showing that if p is true,
then q must also be true, so that the combination p true and q false never occurs. In a direct proof, we
assume that p is true and use axioms, definitions, and previously proven theorems, together with rules of
inference, to show that q must also be true

DEFINITION 1 The integer n is even if there exists an integer k such that n = 2k, and n is odd if there
exists an integer k such that n = 2k + 1. (Note that every integer is either even or odd,
and no integer is both even and odd.) Two integers have the same parity when both are
even or both are odd; they have opposite parity when one is even and the other is odd.

EXAMPLE 1 Give a direct proof of the theorem “If n is an odd integer, then is odd.”

Solution: n = 2k + 1 ,

is odd
-------------------------------------------------------------------------------------------------------------------------------------------------------
EXAMPLE 2 Give a direct proof that if m and n are both perfect squares, then nm is also a perfect square.
(An integer a is a perfect square if there is an integer b such that a = .)

Solution: We assume that m and n are both perfect squares. By the definition of a perfect square,
such that m = and n = . mn = =
. .

DEFINITION 3 The real number r is rational if there exist integers p and q with q 0 such that r = p/q.
p and q have no common factors (so that the fraction p/q is in lowest terms.)
A real number that is not rational is called irrational.

EXAMPLE 3 Prove that the sum of two rational numbers is rational.

Solution:
Let r = p/q where p and q are integers, with q 0, and s = t/u where t and u are
integers, with u 0 .
where

is rational number
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

DEFINITION 4 Let

DEFINITION 5 Let and . is congruent to modulo ,

if

EXAMPLE 4 : ,

-------------------------------------------------------------------------------------------------------------------------------------------------------

Exercises
1. Use a direct proof to show that the sum of two odd integers is even.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

2. Use a direct proof to show that the sum of two even integers is even.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

3. Show that the square of an even number is an even number using a direct proof.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

4. Show that the additive inverse, or negative, of an even number is an even number using a
direct proof.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

5. Prove that if m + n and n + p are even integers, where m, n, and p are integers, then
m + p is even.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

6. Use a direct proof to show that the product of two odd numbers is odd.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

7. Use a direct proof to show that every odd integer is the difference of two squares.
Solution:

( is odd)

-------------------------------------------------------------------------------------------------------------------------------------------------------

8. Use a direct proof to show that is an even number where is integer.

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

9. Use a direct proof to show that if is an odd integer number, then

Where is integer .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

10. Use a direct proof to show that if is a prime number, then is a composite
number .
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

11. Use a direct proof to show that if is an odd prime number, then the number 4 is a
divisor to .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

12. Use a direct proof to show that if is an odd number, then is odd.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

13. Use a direct proof to prove that if is an odd number, then .

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

14. Use a direct proof to prove that if is an even number, then .

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

15. Use a direct proof to prove that, if is not a divisor of , then .

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

16. If and where and

prove that :
(i) (ii)
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

Proof by Contraposition Proofs by contraposition make use of the fact that the conditional statement
p → q is equivalent to its contrapositive, ￢q →￢p. This means that the conditional statement p → q can
be proved by showing that its contrapositive, ￢q →￢p, is true. In a proof by contraposition of p → q, we
take ￢q as a premise, and using axioms, definitions, and previously proven theorems, together with rules
of inference, we show that ￢p must follow. the proof by contraposition can succeed when we
cannot easily find a direct proof.

EXAMPLE 1 Prove that if n is an integer and 3n + 2 is odd, then n is odd.

Solution:
Assume that n is even. Then, n = 2k . Substituting 2k for n, we find that
.
This tells us that 3n + 2 is even (because it is a multiple of 2), and therefore not odd. This is
the negation of the premise of the theorem.

-------------------------------------------------------------------------------------------------------------------------------------------------------

EXAMPLE 2 Prove that if n = ab, where a and b are positive integers, then
a≤ .
Solution:
Assume that

-------------------------------------------------------------------------------------------------------------------------------------------------------

EXAMPLE 3 Prove that if n is an integer and is odd, then n is odd.

Solution:
Assume that is even integer,

is even .
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
Exercises

1. Use a proof by contraposition to show that if x + y ≥ 2, where x and y are real numbers,
then x ≥ 1 or y ≥ 1.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

2. Prove that if m and n are integers and mn is even, then m is even or n is even.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

3. Show that if n is an integer and + 5 is odd, then n is even using a proof by

contraposition.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
4. Prove that if n is an integer and 3n + 2 is even, then n is even ,using a proof by
contraposition.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

5. Prove that if n is a positive integer, then n is even if and only if 7n + 4 is even.

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

6. Prove that if is an integer where , then using a proof by

contraposition.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

7. Use a proof by contraposition to show that if , then .

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

8. Use a proof by contraposition to show that if is even number where , then

is even or is even .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

9. Use a proof by contraposition to show that if , then one of

these numbers is at least should be even .
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

10. Use a proof by contraposition to show that if is irrational number, then

is irrational or is irrational .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

11. Use a proof by contraposition to show that if is odd, then is even or is

even .
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
12. Use a proof by contraposition to show that if x + y , where x and y are real
numbers, then x 8 or y 8.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

13. Prove that if is an integer where , then using a proof

by contraposition.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

14. Use a proof by contraposition to show that if is even, then is odd.

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

15. Let . Use a proof by contraposition to show that if ,

then .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

16. Prove that if n is a positive integer, then n is even if and only if 7n + 4 is even .

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
17. Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

18. Prove that if n is integer, then is odd if and only if 9n + 5 is even .

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

19. Use a proof by contraposition to show that if where , then

is even or is even or is even .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

20. Use a proof by contraposition to show that if is even, then is odd.

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

21. Use a proof by contraposition to show that if , where a and b are real
numbers, then or b 3.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
22. Use a proof by contraposition to show that if x + y , where x and y are real
numbers, then x 4 or y 5.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

23. Use a proof by contraposition to show that if , then or

where .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

24. Use a proof by contraposition to show that if where , then

or .
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

25. Use a proof by contraposition to show that if , then or or

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

26. Use a proof by contraposition to show that if is even

then is even or is even or is even, where .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

27. Use a proof by contraposition to show that if is odd, then is even : .

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

Proofs by Contradiction Suppose we want to prove that a statement p is true. Furthermore, suppose
that we can find a contradiction q such that ￢p → q is true. Because q is false, but ￢p → q is true, we can
conclude that ￢p is false, which means that p is true. How can we find a contradiction q that might help us

prove that p is true in this way? Because the statement r ∧￢r is a contradiction whenever r is a

proposition, we can prove that p is true if we can show that ￢p → (r ∧￢r) is true for some proposition r.
Proofs of this type are called proofs by contradiction

EXAMPLE 1 Prove that is irrational by giving a proof by contradiction.

Proof : Let p be the proposition “ is irrational.” We will show that assuming that ￢p is
true leads to a contradiction. If is rational, there exist integers a and b with
where b 0 and gcd( ; a and b have no common factors (so that the fraction a/b
is in lowest terms.)
(1)

is even
is even too
This is contradiction with the assumption that gcd( . is true .

-------------------------------------------------------------------------------------------------------------------------------------------------------

EXAMPLE 2 Give a proof by contradiction of the theorem “If 3n + 2 is odd, then n is

odd.”
Solution: Let p be “3n + 2 is odd” and q be “n is odd.” To construct a proof by
contradiction, assume that both p and ￢q are true. That is, assume that 3n + 2 is odd and
that n is not odd.
Because n is not odd, we know that it is even. Because n is even, there is an integer k such
That n = 2k. This implies that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). Because 3n + 2
is 2t , where t = 3k + 1, 3n + 2 is even. Note that the statement “3n + 2 is even” is
equivalent to the statement ￢p, because an integer is even if and only if it is not odd.
Because both p and￢p are true, we have a contradiction. This completes the proof by
contradiction, proving that if 3n + 2 is odd, then n is odd.
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

Exercises
1. Use a proof by contradiction to prove that the sum of an irrational number and a rational
number is irrational.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

2. Show that if n is an integer and + 5 is odd, then n is even using a proof by

contradiction.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
3. Prove that if n is an integer and 3n + 2 is even, then n is even using a proof by
contradiction.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------
4. Use a proof by contradiction to show that there is no rational number r for which

[Hint: Assume that r = a/b is a root, where a and b are integers and a/b is in lowest terms.
Obtain an equation involving integers by multiplying by b3. Then look at whether a and b
are each odd or even.]
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

5. Prove that is irrational by giving a proof by contradiction.

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------
6. Prove that is irrational by giving a proof by contradiction.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
7. Let is irrational, prove that is irrational number.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------
8. Let is irrational, prove that is irrational number.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

9. Let is irrational, prove that is irrational number.

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

10. Let is irrational, prove that is irrational number.

Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

11. Let are rational numbers : and is irrational, prove that is

irrational number.
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

12. Let , use a proof by contradiction to show that

or or .
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

13. Let , use a proof by contradiction to show that

or or .
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

14. Use a proof by contradiction to prove that the product of an irrational number and a
non-zero rational number is irrational.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------
15. Let is a prime number . use a proof by contradiction to prove that if , then
.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

16. Use a proof by contradiction to prove that , such that

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

17. Prove or disprove that the product of two irrational numbers is irrational.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------
18. Prove or disprove that the sum of two irrational numbers is irrational.
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------

19. Use a proof by contradiction to prove that for .

Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

20. Use a proof by contradiction to prove that , such that

and gcd(
Solution:

-------------------------------------------------------------------------------------------------------------------------------------------------------
21. Prove or disprove that if then : .
Solution:
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

PROOF BY CASES A proof by cases must cover all possible cases that arise in a theorem.
We illustrate proof by cases with a couple of examples. In each example, you should check that
all possible cases are covered.

EXAMPLE 1 Prove that if n is an integer, then ≥ n.

Solution: We can prove that n2 ≥ n for every integer by considering three cases,
when n = 0, when n ≥ 1, and when n ≤ −1.We split the proof into three cases because it
is straight forward to prove the result by considering zero, positive integers, and negative
integers separately.
Case (i): When n = 0, because , we see that ≥ 0. It follows that ≥ n is true in
this case.
Case (ii): When n ≥ 1, when we multiply both sides of the inequality n ≥ 1 by the positive
Integer n, we obtain n · n ≥ n · 1. This implies that ≥ n for n ≥ 1.
Case (iii): In this case n ≤ −1. However, ≥ 0. It follows that ≥ n.
Because the inequality ≥ n holds in all three cases, we can conclude that if n is an
integer, then ≥ n.

EXAMPLE 4 Use a proof by cases to show that |xy| = |x||y|, where x and y are real
numbers. ( Recall that |a| )
Solution: In our proof of this theorem, we remove absolute values using the fact that |a| = a
when a ≥ 0 and |a| = −a when a < 0. Because both |x| and |y| occur in our formula, we will
need four cases: (i) x and y both nonnegative,
(ii) x nonnegative and y is negative,
(iii) x negative and y nonnegative
(iv) x negative and y negative.
We denote by p1, p2, p3, and p4, the proposition stating the assumption for each of these
four cases, respectively.
(Note that we can remove the absolute value signs by making the appropriate choice of
signs within each case.)
Case (i):We see that p1 → q because xy ≥ 0 when x ≥ 0 and y ≥ 0,
so that |xy| = xy =|x||y|.
Case (ii): To see that p2 → q, note that if x ≥ 0 and y < 0, then xy ≤ 0,
so that |xy| =−xy = x(−y) = |x||y|. (Here, because y < 0, we have |y| = −y.)
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin

Case (iii): To see that p3 → q, we follow the same reasoning as the previous case with the
roles of x and y reversed.
Case (iv): To see that p4 → q, note that when x < 0 and y < 0, it follows that xy > 0.
Hence, |xy| = xy = (−x)(−y) = |x||y|.
Because |xy| = |x||y| holds in each of the four cases and these cases exhaust all possibilities,
we can conclude that |xy| = |x||y|, whenever x and y are real numbers.

EXAMPLE 7 Show that if x and y are integers and both xy and x + y are even,
then both x and y are even.
Solution: We will use proof by contraposition, the notion of without loss of generality, and
proof by cases. First, suppose that x and y are not both even. That is, assume that x is odd or
that y is odd (or both).Without loss of generality, we assume that x is odd, so that
x = 2m + 1 for some integer k. To complete the proof, we need to show that
xy is odd or x + y is odd. Consider two cases:
(i) y even
(ii) y odd.
In (i), y = 2n for some integer n, so that x + y =(2m + 1) + 2n = 2(m + n) + 1 is odd.

In (ii), y = 2n + 1 for some integer n, so that xy =(2m + 1)(2n + 1) = 4mn + 2m + 2n + 1

= 2(2mn + m + n) + 1 is odd. This completes the proof by contraposition.
(Note that our use of without loss of generality within the proof is justified because the
proof when y is odd can be obtained by simply interchanging the roles of x and y in the
proof we have given.)
 Math 151 Discrete Mathematics [Methods of Proof] By: Malek Zein AL-Abidin
Exercises
1. Prove that if x and y are real numbers, then max(x, y) + min(x, y) = x + y.
[Hint: Use a proof by cases, with the two cases corresponding to x ≥ y andx < y,
respectively.]

Solution: If x ≤ y, then max(x, y) + min(x, y) = y + x = x + y.

If x ≥ y, then max(x, y) + min(x, y) = x + y.
Because these are the only two cases, the equality always holds .

-------------------------------------------------------------------------------------------------------------------------------------------------------

2. Use a proof by cases, to prove that + 1 ≥ 2n when n is a positive integer

with 1 ≤ n ≤ 4.
Solution: + 1 = 2 ≥ 2 = 2(1) ;
+ 1 = 5 ≥ 4 = 2(2);
+ 1 =10 ≥ 8 = 2(3);
+ 1 =17 ≥ 16 = 2(4)