Page 113 - Discrete Mathematics and Its Applications

92 1 / The Foundations: Logic and Proofs

38. Find a counterexample to the statement that every posi- three integers in consecutive locations around the circle
tive integer can be written as the sum of the squares of that have a sum greater than or equal to 17.
three integers. 41. Prove that if n is an integer, these four statements are
39. Prove that at least one of the real numbers a 1 , a 2 ,...,a n equivalent: (i) n is even, (ii) n + 1 is odd, (iii)3n + 1is
is greater than or equal to the average of these numbers. odd, (iv)3n is even.
What kind of proof did you use? 42. Prove that these four statements about the integer n are
2
3
40. Use Exercise 39 to show that if the first 10 positive inte- equivalent: (i) n is odd, (ii)1 − n is even, (iii) n is odd,
2
gers are placed around a circle, in any order, there exist (iv) n + 1iseven.
1.8 Proof Methods and Strategy

Introduction

In Section 1.7 we introduced many methods of proof and illustrated how each method can be
used. In this section we continue this effort.We will introduce several other commonly used proof
methods, including the method of proving a theorem by considering different cases separately.
We will also discuss proofs where we prove the existence of objects with desired properties.
In Section 1.7 we briefly discussed the strategy behind constructing proofs. This strategy
includes selecting a proof method and then successfully constructing an argument step by step,
based on this method. In this section, after we have developed a versatile arsenal of proof
methods, we will study some aspects of the art and science of proofs. We will provide advice
on how to find a proof of a theorem. We will describe some tricks of the trade, including how
proofs can be found by working backward and by adapting existing proofs.
When mathematicians work, they formulate conjectures and attempt to prove or disprove
them. We will briefly describe this process here by proving results about tiling checkerboards
with dominoes and other types of pieces. Looking at tilings of this kind, we will be able to
quickly formulate conjectures and prove theorems without first developing a theory.
We will conclude the section by discussing the role of open questions. In particular, we
will discuss some interesting problems either that have been solved after remaining open for
hundreds of years or that still remain open.

Exhaustive Proof and Proof by Cases

Sometimes we cannot prove a theorem using a single argument that holds for all possible cases.
We now introduce a method that can be used to prove a theorem, by considering different cases
separately. This method is based on a rule of inference that we will now introduce. To prove a
conditional statement of the form

(p 1 ∨ p 2 ∨ ··· ∨ p n ) → q

the tautology

[(p 1 ∨ p 2 ∨ ··· ∨ p n ) → q]↔[(p 1 → q) ∧ (p 2 → q) ∧ ··· ∧ (p n → q)]

can be used as a rule of inference. This shows that the original conditional statement with
a hypothesis made up of a disjunction of the propositions p 1 ,p 2 ,...,p n can be proved by
proving each of the n conditional statements p i → q, i = 1, 2,...,n, individually. Such an
argument is called a proof by cases. Sometimes to prove that a conditional statement p → q is
true, it is convenient to use a disjunction p 1 ∨ p 2 ∨ ··· ∨ p n instead of p as the hypothesis of
the conditional statement, where p and p 1 ∨ p 2 ∨ ··· ∨ p n are equivalent.