Discrete Structures for Computer Science Presented by: Andrew F. Conn Adapted from: Adam Lee Lecture #6: Proof Methods and Strategies September 19th, 2016 Announcements HW #1 is due Wednesday HW #2 will come out today. It is tentatively due next Wednesday 9/28 Proof Methods and Strategies

Last class we discussed 3 proof methods: 1. Direct Proof 2. Proof by Contraposition 3. Proof by Contradiction Today we will add 2 more proof methods: 4. Exhaustive Proof and Proof by Cases. 5. Existence Proof 6. Uniqueness Proof Then we will discuss 4 types of strategy: 7. Forward reasoning 8. Backward reasoning 9. Searching for counterexamples

10. Adapting existing proofs Sadly, not all theorems are of the form p q Sometimes, we need to prove a theorem of the form: Note: So, we might need to examine multiple cases! Exhaustive Proof: Try every possibility!

Prove that where is a positive integer with . Proof: , , , , and and and and Since we have verified each case, we have shown that where is a positive integer with .

With only 4 cases to consider, exhaustive proof was a good choice! Sometimes, exhaustive proof isnt an option, but we still need to examine multiple possibilities Example: Prove the triangle inequality. That is, if and are real numbers, then . Clearly, we cant use exhaustive proof here since there are infinitely many real numbers to consider. We also cant use a simple direct proof either, since our proof depends on the signs of and .

What should we do? Proof by Cases: Triangle Inequality Case 1: Assume . Then we can drop the absolute value and we have . Case 2: Assume The we can multiply everything by and get Case 3: Assume Then we have We need 2 more cases, and 3a) We can drop the absolute value from the right hand side

and we get , and we already have 3b) We can multiply the right hand side by to get . Since is positive, we have In both sub cases, we have as required. Case 4: Similar to Case 3. Making mistakes when using proof by cases is all too easy! Mistake 1: Proof by a few cases is not equivalent to proof by cases. These are there exists proofs, not a for all proof!

Example: Prove that all odd numbers are prime. Proof: Case 1: The number 3 is both odd and prime Case 2: The number 5 is both odd and prime Case 3: The number 7 is both odd and prime Thus, we have shown that odd numbers are prime. Making mistakes when using proof by cases is all too easy!

Mistake 2: Leaving out critical cases. Example: Prove that for all integers Proof: Case 1: Assume that . Since the product of two negative numbers is always positive, . Case 2: Assume that . Since the product of two positive numbers is always positive, . Since we have proven the claim for all cases, we can conclude that for all integers . What about the case in which x = 0? Sometimes we need to prove the existence of a given element

There are two ways to do this Prove the claim by showing how to construct an example The constructive approach Show that it is possible for such an element to exist The non-constructive approac A constructive existence proof Prove: Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways.

Proof: 1729 = 103 + 93 = 123 + 13 Obviously, the claim has been proven because we have shown that a specific instance of the claim is valid. Constructive existence proofs are really just instances of existential generalization. A non-constructive existence proof Prove: Show that there exist two irrational numbers and such that is rational. Proof: We know that is irrational, so let If is rational, then we are done! (i.e., )

If is irrational, then let and , both of which are irrational Now, , which is rational (i.e., ) Note: We dont know whether 22 is rational or irrational. However, in either case, we can use it to construct a rational number. Sometimes, existence is not enough and we need to prove uniqueness This process has two steps: 1. Provide an existence proof 2. Show that any other solution to the problem is equivalent to the solution generated in step 1

Example: Prove that if a and b are real numbers, then there exists a unique real number such that Proof: Existence Note that is a solution to this equality since . Uniqueness Assume that Then , so , which is a contradiction The scientific process is not always

straightforward Conjecture Gather evidence, prove lemmas Prove theorem Proof strategies can help preserve your sanity Proof strategies help us

Organize our problem solving approach Effectively use all of the tools at our disposal Develop a coherent plan of attack Proof Strategies Convince yourself with examples or

counterexamples! Often times an example can expose a pattern that can be used in the proof. If you find a counterexample, youre done! Try to work forward from the premises Many proofs involve stepwise applications of basic logic. Try to work backwards from the result Sometimes the conclusion will yield a property that the premise implies to be true! Look for existing strategies that might fit this

problem What strategy might one use with even and odd integer proofs? Even Backwards Reasoning Forward reasoning can lead down multiple paths. In these cases, it is often helpful to reason backwards, starting with the goal that we want to prove. Example: Prove that given two distinct positive real numbers and , the arithmetic mean of and is always greater than the geometric mean of

and . + Try: and . Geometric vs Arithmetic? Try it: Since whenever , the final inequality is true.

Since all of these inequalities are the same, we can work backwards and it follows that . Searching for a counterexample Proof by counterexample is helpful if: Proof attempts repeatedly fail The conjecture to be proven looks funny Example: Prove that every positive integer is the sum of two squares. This seems strange to me, since other factorizations (e.g., prime factorizations) can be complex.

Counterexample: 3 is not the sum of two squares, so the claim is false. These four proof strategies are just a start! When trying to prove a new conjecture, a good meta strategy is to: 1. If possible, try to reuse an existing proof 2. If the conjecture looks fishy, check for a counterexample 3. Attempt a real proof a) Either apply the forward reasoning strategy b) Or, apply the backward reasoning strategy

Unfortunately, not every proof can be solved using this nice little meta strategy In fact, there are many, many proof strategies out there, and NONE of them can be guaranteed to find a proof!!! Group work! Problem 1: Prove that there exists a positive integer that is equal to the sum of all positive integers not exceeding it. Is your proof constructive or non-constructive? Problem 2: Prove that there is no positive integer n such that n2 + n3 = 100. Problem 3: Use proof by cases to show that

min(a, min(b,c) = min(min(a,b),c) whenever a, b, and c are real numbers. Final Thoughts Proving theorems is not always straightforward Having several proof strategies at your disposal will make a huge difference in your success rate! We are done with our intro to logic and proofs Next lecture: Intro to set theory Please read sections 2.1 and 2.2

Weve been doing forward reasoning all along! In the forward reasoning strategy, we begin with our premises and axioms and reason towards our goal Potential steps in the forward reasoning process: 1. Try a simple direct proof Could be of form p q Could be of form (p1 p2 pn) q

2. If direct proof fails, try proof by contraposition