Basic Proof Techniques - Washington University in St. Louis

1 Basic Proof TechniquesDavid 13, 20101 Four Fundamental Proof TechniquesWhen one wishes to prove the statementP Qthere are four fundamentalapproaches. This document models those four different approaches by provingthe same proposition four times over using each fundamental central question which we address in this paper is the truth or falsity ofthe following statement:The sum of any two consecutive numbers is youwere put on the spot you could certainly convince most reasonable people thatour question is undoubtedly true. However, we are not interested in convincingthe passing layperson. We seek to demonstrate beyond any doubt that ourproposition is true using only the most formal, bulletproof methods following three definitions are central to the execution of our proofs:Definition integer number n isevenif and only if there exists a numberk such thatn= integer number n isoddif and only if there exists a numberk such thatn= 2k+ integers a and b areconsecutiveif and only ifb=a+ Direct Proof ( Proof by Construction)In a constructive Proof one attempts to demonstrateP Qdirectly.

2 This isthe simplest and easiest method of Proof available to us. There are only twosteps to a direct Proof (the second step is, of course, the tricky part):1. Assume thatPis UsePto show thatQmust be a and b are consecutive integers, then the suma+bis thataandbare consecutive integers. Becauseaandbareconsecutive we know thatb=a+ 1. Thus, the suma+bmay be re-written as2a+ 1. Thus, there exists a numberksuch thata+b= 2k+ 1 so the suma+bis Proof by ContradictionThe Proof by contradiction is grounded in the fact that any proposition mustbe either true or false, but not both true and false at the same time. We arriveat a contradiction when we are able to demonstrate that a statement is bothsimultaneously true and false, showing that our assumptions are can use this to demonstrateP Qby assuming bothPand Qare simul-taneously true and deriving a contradiction.

3 When we derive this contradictionit means that one of our assumptions was untenable. Presumably we have eitherassumed or already provedPto be true so that finding a contradiction impliesthat Qmust be method of Proof by Assume thatPis Assume that Qis UsePand Qto demonstrate a a and b are consecutive integers, then the suma+bis thataandbare consecutive integers. Assume also that the suma+bis not odd. Because the suma+bis not odd, there exists no number ksuch thata+b= 2k+ 1. However, the integersaandbare consecutive , so wemay write the suma+bas 2a+ 1. Thus, we have derived thata+b6= 2k+ 1for any integerkand also thata+b= 2a+ 1. This is a contradiction. If wehold thataandbare consecutive then we know that the suma+bmust Proof by InductionProof by induction is a very powerful method in which we use recursion todemonstrate an infinite number of facts in a finite amount of space.

4 The mostbasic form of mathematical induction is where we first create a propositionalform whose truth is determined by an integer function. If we are able to showthat the propositional form is true for some integer value then we may arguefrom that basis that the propositional form must be true for all Show that a propositional formP(x) is true for some basis Assume thatP(n) is true for somen, and show that this implies thatP(n+ 1) is Then, by the principle of induction, the propositional formP(x) is truefor allngreater or equal to the basis a and b are consecutive integers, then the suma+bis the propositional formF(x) to be true when the sum ofxand itssuccessor is odd.(Step 1)Consider the propositionF(1). The sum 1 + 2 = 3 is odd becausewe can demonstrate there exists an integerksuch that 2k+ 1 = 3.

5 Namely,2(1) + 1 = 3. Thus,F(x) is true whenx= (Step 2)Assume thatF(x) is true for somex. Thus, for somexwe havethatx+ (x+ 1) is odd. We add one to bothxandx+ 1 which gives the sum(x+ 1) + (x+ 2). We claim two things: first, the sum (x+ 1) + (x+ 2) =F(x+ 1).Second, we claim that adding two to any integer does not change that integer sevenness or oddness. With these two observations we claim thatF(x) is oddimpliesF(x+ 1) is odd.(Step 3)By the principle of mathematical induction we thus claim thatF(x) is odd for all integersx. Thus, the sum of any two consecutive numbersis Proof by ContrapositiveProof by contraposition is a method of Proof which is not a method all its ownper se. From first-order logic we know that the implicationP Qis equivalentto Q P. The second proposition is called the contrapositive of the firstproposition.

6 By saying that the two propositions are equivalent we mean thatif one can proveP Qthen they have also proved Q P, and vice by contraposition can be an effective approach when a traditionaldirect Proof is tricky, or it can be a different way to think about the substanceof a the suma+bis not odd, then a and b are not is important to beextremelypedantic when interpreting a would be tempting to claim that the above theorem claims that the sum oftwo numbers is odd only when those two numbers are consecutive . However,this is that the sum of the integersaandbis not odd. Then, thereexists no integer k such thata+b= 2k+ 1. Thus,a+b6=k+ (k+ 1) for allintegersk. Becausek+ 1 is the successor ofk, this implies thataandbcannotbe consecutive Direct ProofThere are two steps to directly provingP Q:1.

7 AssumePis Demonstrate thatQmust follow AX(a, b)be a function which returns whichever ofaorbis (a)be defined to be such that if a is postiive thenABS(a) =a, and if a is negative thenABS(a) = following proofs demonstrate that sometimes it s easiest to break aproposition into separate cases and prove each case a,b,c,d be integers. Ifa > candb > c, thenM AX(a, b) cis always thata > candb > know thata > candb > c, but we cannot say for certain ifa > borb > a. Therefore we proceed by Case 1: Assume thata > b. Becausea > bwe know thatM AX(a, b) = may thus claim thatM AX(a, b) c=a c. By assumption we knowthata > cso the differencea cmust be Case 2: Assume thatb > a. Becauseb > awe know thatM AX(a, b) = may thus claim thatM AX(a, b) c=b c. By assumption we knowthatb > cso the differenceb cmust be , in all possible casesM AX(a, b) cis a and b are integers, thenABS(a)ABS(b) =ABS(ab).

8 Thataandbare integers. We proceed by cases:1. Case 1: Supposeais negative andbis positive. By definitionABS(a) = aandABS(b) =b. Thus,ABS(a)ABS(b) = ab. Likewise, the productabis negative soABS(ab) = ab. Thus,ABS(a)ABS(b) =ABS(ab).2. Case 2: Suppose thatais positive andbis negative. By definitionABS(a) =aandABS(b) = b. Thus,ABS(a)ABS(b) =a( b) = ab. Likewise, the productabis negative soABS(ab) = ab. Thus,ABS(a)ABS(b) =ABS(ab).3. Case 3: Suppose that bothaandbare positive. By definitionABS(a) =aandABS(b) =b. Thus,ABS(a)ABS(b) =ab. Likewise, the productabis positive soABS(ab) =ab. Thus,ABS(a)ABS(b) =ABS(ab).4. Case 4: Suppose that bothaandbare negative. By definitionABS(a) = aandABS(b) = b. Thus,ABS(a)ABS(b) = ( a)( b) =ab. Like-wise, the productabis then positive soABS(ab) =ab.

9 Thus,ABS(a)ABS(b) =ABS(ab).Therefore, in every possible case we have thatABS(a)ABS(b) =ABS(ab). Proof by ContradictionSteps to proving a theorem by contradiction:1. AssumePis Assume Qis Demonstrate a statement of the following Proof is different from those we have seen sofar in that there is no explicitly stated starting assumption. In these cases weare free to assume we have at our disposal the general machinery of the subjectwhich we are studying. In this case, we implicitly assume all of number and settheory to tackle the that there are an infinite number of , by way of contradiction, that there are a finite number ofprimesp1, p2, Letkbe the product of all these primes plus one:k= + 1. The integer k is clearly greater than one and because k is aninteger, there must exist some prime numberPwhich divides it.

10 However,Pcannot be any one ofp1, p2, if it were thenPcould divide thedifferencek divide one andalso be prime (which is by definition greater than one). This is a contradic-tion. Therefore our assumption is false so there must be an infinite number Proof by Mathematical InductionTo demonstrateP Qby induction we require that the truth ofPandQbeexpressed as a function of some ordered (Basis)Show thatP Qis valid for a specific (Inductive Hypothesis)Assume thatP Qfor some Demonstrate thatP Qfor the elementn+ 1 Conclude thatP Qfor all elements greater than or equal that the summation formulan i=1i=n(n+ 1)2(1)is valid for all integers (Basis case)We demonstrate that the formula is valid forn= 1. Bysubstituting one fornthe formula gives us 1 =1(2)2, which is true.