Page 106 - Discrete Mathematics and Its Applications

1.7 Introduction to Proofs 85

n
n
EXAMPLE 6 Let P (n) be “If a and b are positive integers with a ≥ b, then a ≥ b ,” where the domain
consists of all nonnegative integers. Show that P(0) is true.
0
0
0
0
Solution:ThepropositionP(0)is“Ifa ≥ b,thena ≥ b .”Becausea = b = 1,theconclusion
0
0
of the conditional statement “If a ≥ b, then a ≥ b ” is true. Hence, this conditional statement,
which is P(0), is true. This is an example of a trivial proof. Note that the hypothesis, which is
the statement “a ≥ b,” was not needed in this proof. ▲
A LITTLE PROOF STRATEGY We have described two important approaches for proving
theorems of the form ∀x(P (x) → Q(x)): direct proof and proof by contraposition. We have
also given examples that show how each is used. However, when you are presented with a
theorem of the form ∀x(P (x) → Q(x)), which method should you use to attempt to prove it?
We will provide a few rules of thumb here; in Section 1.8 we will discuss proof strategy at greater
length. When you want to prove a statement of the form ∀x(P (x) → Q(x)), first evaluate
whether a direct proof looks promising. Begin by expanding the definitions in the hypotheses.
Start to reason using these hypotheses, together with axioms and available theorems. If a direct
proof does not seem to go anywhere, try the same thing with a proof by contraposition. Recall
that in a proof by contraposition you assume that the conclusion of the conditional statement is
false and use a direct proof to show this implies that the hypothesis must be false. We illustrate
this strategy in Examples 7 and 8. Before we present our next example, we need a definition.

DEFINITION 2 The real number r is rational if there exist integers p and q with q = 0 such that r = p/q.
A real number that is not rational is called irrational.

EXAMPLE 7 Prove that the sum of two rational numbers is rational. (Note that if we include the implicit
quantifiers here, the theorem we want to prove is “For every real number r and every real
number s,if r and s are rational numbers, then r + s is rational.)

Solution:Wefirstattemptadirectproof.Tobegin,supposethatr ands arerationalnumbers.From
the definition of a rational number, it follows that there are integers p and q, with q = 0, such
that r = p/q, and integers t and u, with u = 0, such that s = t/u. Can we use this information
to show that r + s is rational? The obvious next step is to add r = p/q and s = t/u, to obtain

p t pu + qt
r + s = + = .
q u qu

Because q = 0 and u = 0, it follows that qu = 0. Consequently, we have expressed r + s as
the ratio of two integers, pu + qt and qu, where qu = 0. This means that r + s is rational. We
have proved that the sum of two rational numbers is rational; our attempt to find a direct proof
succeeded. ▲

2
EXAMPLE 8 Prove that if n is an integer and n is odd, then n is odd.
2
Solution: We first attempt a direct proof. Suppose that n is an integer and n is odd. Then, there
2
exists an integer k such that n = 2k + 1. Can we use this information to show that n is odd?
There seems to be no obvious approach to show that n is odd because solving for n produces
√
the equation n =± 2k + 1, which is not terribly useful.
Because this attempt to use a direct proof did not bear fruit, we next attempt a proof by
contraposition. We take as our hypothesis the statement that n is not odd. Because every integer
is odd or even, this means that n is even. This implies that there exists an integer k such that
n = 2k. To prove the theorem, we need to show that this hypothesis implies the conclusion
2
2
that n is not odd, that is, that n is even. Can we use the equation n = 2k to achieve this? By