Ecuador. Iglesia Y Estado

CHAPTER

3

Proof Strategies and Diagrams
The main purpose of this book is to help you develop your mathematical reasoning ability and to help you learn how to use the language and notation of mathematics. In this chapter we will present a variety of proof and assumption strategies. Each proof strategy is motivated by the logical structure of the statement to be proven. A proof strategy willtypically be followed by a corresponding assumption strategy. An assumption is an assertion that can be taken to be true.

3.1 Conjecture and Proof in Mathematics
A conjecture is a statement for which there is some evidence supporting the belief that the statement is true. We will now illustrate this idea. Consider the values of the elements in the sequence 1, 1 + 3, 1 + 3 + 5, 1 + 3 + 5 + 7,. . . , 1 + 3 + 5 + · · ·+ (2n − 1), . . . where the first entry is 1, the second entry is 1 + 3, the third entry is 1 + 3 + 5, and the n-th entry is 1 + 3 + 5 + · · · + (2n − 1) (the sum of the first n odd numbers). The table of values below is obtained by evaluating the sums of the first six entries of the sequence.
n 1 2 3 4 5 6 1 + 3 + 5 + · · · + (2n − 1) 1 1+3 1+3+5 1+3+5+7 1+3+5+7+91+3+5+7+9+11 value 1 4 9 16 25 36

Is there a pattern? Is there a general rule? It appears that the sum of the first n odd numbers is equal to n2 . Conjecture 1. Let n be a natural number. Then 1 + 3 + 5 + · · ·+ (2n − 1) = n2 . For another example, let us investigate the values of the elements in the sequence 12 + 1 + 41, 22 + 2 + 41, 32 + 3 + 41, 42 + 4 + 41, 52 + 5 + 41, . . . , n2 + n + 41, . . .D.W. Cunningham, A Logical Introduction to Proof, DOI 10.1007/978-1-4614-3631-7 3, © Springer Science+Business Media New York 2012 61

62

3 Proof Strategies and Diagrams

What could possibly be interesting about these numbers? Let us begin by evaluating a sample of the natural numbers that have the form n2 + n + 41. By computing the first six values of this sequence, we obtain the table
n 1 23 4 5 6 n2 + n + 41 12 + 1 + 41 22 + 2 + 41 32 + 3 + 41 42 + 4 + 41 52 + 5 + 41 62 + 6 + 41 value 43 47 53 61 71 83

What property do these values have? They cannot be factored! One observes that the formula n2 + n + 41 seems to produce a prime number (see Definition 4.1.3). Conjecture 2. Let n be a natural number. Then n2 + n + 41 is a prime. Conjecture + Proof = Theorem Mathematicians statetheir results in a form called a theorem which is a mathematical statement that has been proven to be true. A conjecture is a statement that one thinks is plausible but whose truth has not been established. In mathematics one never accepts a conjecture as being true until a proof of the conjecture has been given. A proof is a logical argument that establishes the truth of the conjecture. Once amathematical proof of the conjecture is produced, then the conjecture becomes a theorem. For example, one can give a proof of Conjecture 1 (see Exercise 1 on page 122) and thus, this conjecture will become a theorem. On the other hand, to show that a conjecture is false one must find an assignment of values (an example) which makes all of the assumptions of the conjecture true while making theconclusion false. Such an assignment is called a counterexample to the conjecture. Consequently, a counterexample shows that the assumptions of the conjecture do not imply its conclusion. Actually, Conjecture 2 is false and to show this we will give a counterexample. Let n = 41. So, n ≥ 1 and n2 + n + 41 = (41)2 + 41 + 41 = 41(41 + 1 + 1) = 41 · 43, which is not a prime. Hence, Conjecture 2 is false.Example 1. Find a counterexample showing that the following conjecture is false: Conjecture. Suppose x and y are real numbers satisfying x > 2 and y < 3. Then x(1 − y) > 2 − x.

3.1 Conjecture and Proof in Mathematics

63

Solution. We must find a counterexample that refutes the conjecture. Let x = 3 and y = 2. Since x > 2 and y < 3, the assumptions of the conjecture hold. Furthermore, x(1 −...