Page 121 - Discrete Mathematics and Its Applications

100 1 / The Foundations: Logic and Proofs
EXAMPLE 14
Proof Strategies
Finding proofs can be a challenging business. When you are confronted with a statement to
prove, you should first replace terms by their definitions and then carefully analyze what the
hypotheses and the conclusion mean. After doing so, you can attempt to prove the result using
one of the available methods of proof. Generally, if the statement is a conditional statement,
you should first try a direct proof; if this fails, you can try an indirect proof. If neither of these
approaches works, you might try a proof by contradiction.
FORWARD AND BACKWARD REASONING Whichever method you choose, you need
a starting point for your proof. To begin a direct proof of a conditional statement, you start
with the premises. Using these premises, together with axioms and known theorems, you can
construct a proof using a sequence of steps that leads to the conclusion. This type of reasoning,
called forward reasoning, is the most common type of reasoning used to prove relatively simple
results. Similarly, with indirect reasoning you can start with the negation of the conclusion and,
using a sequence of steps, obtain the negation of the premises.
Unfortunately, forward reasoning is often difficult to use to prove more complicated results,
because the reasoning needed to reach the desired conclusion may be far from obvious. In such
cases it may be helpful to use backward reasoning. To reason backward to prove a statement q,
we find a statement p that we can prove with the property that p → q. (Note that it is not helpful
to find a statement r that you can prove such that q → r, because it is the fallacy of begging
the question to conclude from q → r and r that q is true.) Backward reasoning is illustrated in
Examples 14 and 15.
Given two positive real numbers x and y, their arithmetic mean is (x + y)/2 and their geo-
√
metric mean is xy. When we compare the arithmetic and geometric means of pairs of distinct
positive real numbers, we find that the arithmetic mean is always greater than the geometric
√ √
mean. [For example, when x = 4 and y = 6, we have 5 = (4 + 6)/2 > 4 · 6 = 24.] Can
we prove that this inequality is always true?
√
Solution: To prove that (x + y)/2 > xy when x and y are distinct positive real numbers,
we can work backward. We construct a sequence of equivalent inequalities. The equivalent
inequalities are
√
(x + y)/2 > xy,
2
(x + y) /4 >xy,
2
(x + y) > 4xy,
2
2
x + 2xy + y > 4xy,
2
2
x − 2xy + y > 0,
2
(x − y) > 0.
2
Because (x − y) > 0 when x = y, it follows that the final inequality is true. Because all these
√
inequalities are equivalent, it follows that (x + y)/2 > xy when x = y. Once we have carried
out this backward reasoning, we can easily reverse the steps to construct a proof using forward
reasoning. We now give this proof.
2
Suppose that x and y are distinct positive real numbers. Then (x − y) > 0 because
2
the square of a nonzero real number is positive (see Appendix 1). Because (x − y) =
2
2
2
2
x − 2xy + y , this implies that x − 2xy + y > 0. Adding 4xy to both sides, we obtain
2
2
2
2
2
2
x + 2xy + y > 4xy. Because x + 2xy + y = (x + y) , this means that (x + y) ≥ 4xy.
2
Dividing both sides of this equation by 4, we see that (x + y) /4 >xy. Finally, taking square
roots of both sides (which preserves the inequality because both sides are positive) yields