Page 104 - Discrete Mathematics and Its Applications

1.7 Introduction to Proofs 83

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.

2
EXAMPLE 1 Give a direct proof of the theorem “If n is an odd integer, then n is odd.”
Solution: Note that this theorem states ∀nP ((n) → Q(n)), where P (n) is “n is an odd integer”
2
and Q(n) is “n is odd.” As we have said, we will follow the usual convention in mathematical
proofs by showing that P (n) implies Q(n), and not explicitly using universal instantiation. To
begin a direct proof of this theorem, we assume that the hypothesis of this conditional statement
is true, namely, we assume that n is odd. By the definition of an odd integer, it follows that
2
n = 2k + 1, where k is some integer. We want to show that n is also odd. We can square
2
both sides of the equation n = 2k + 1 to obtain a new equation that expresses n . When we do
2
2
2
2
this, we find that n = (2k + 1) = 4k + 4k + 1 = 2(2k + 2k) + 1. By the definition of an
2
odd integer, we can conclude that n is an odd integer (it is one more than twice an integer).
2
Consequently, we have proved that if n is an odd integer, then n is an odd integer. ▲
EXAMPLE 2 Give a direct proof that if m and n are both perfect squares, then nm is also a perfect square.
2
(An integer a is a perfect square if there is an integer b such that a = b .)
Solution: To produce a direct proof of this theorem, we assume that the hypothesis of this
conditional statement is true, namely, we assume that m and n are both perfect squares. By the
2
definition of a perfect square, it follows that there are integers s and t such that m = s and
2
n = t . The goal of the proof is to show that mn must also be a perfect square when m and n are;
2
2
looking ahead we see how we can show this by substituting s for m and t for n into mn. This
2 2
2 2
2
tells us that mn = s t . Hence, mn = s t = (ss)(tt) = (st)(st) = (st) , using commutativity
and associativity of multiplication. By the definition of perfect square, it follows that mn is also
a perfect square, because it is the square of st, which is an integer. We have proved that if m
and n are both perfect squares, then mn is also a perfect square. ▲
Proof by Contraposition
Direct proofs lead from the premises of a theorem to the conclusion. They begin with the
premises, continue with a sequence of deductions, and end with the conclusion. However, we
will see that attempts at direct proofs often reach dead ends. We need other methods of proving
theorems of the form ∀x(P (x) → Q(x)). Proofs of theorems of this type that are not direct
proofs, that is, that do not start with the premises and end with the conclusion, are called
indirect proofs.
An extremely useful type of indirect proof is known as 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. We will illustrate proof by contraposition
with two examples. These examples show that proof by contraposition can succeed when we
cannot easily find a direct proof.
EXAMPLE 3 Prove that if n is an integer and 3n + 2 is odd, then n is odd.

Solution: We first attempt a direct proof. To construct a direct proof, we first assume that 3n + 2
is an odd integer. This means that 3n + 2 = 2k + 1 for some integer k. Can we use this fact