Proofs 1.2 Proofs in practice n principle, a proof can be any sequence of logical deductions from axioms and previously- proved statements that concludes with the proposition in question. This freedom in con- structing a proof can seem overwhelming at first. How do you even start a proof? Here's the good news: many proofs follow one of a handful of standard templates Proofs all differ in the details, of course, but these templates at least provide you with an outline to fill in. Well go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit ogether; one may give you a top-level outline while others help you at the next level of detail. And well show you other, more sophisticated proof techniques later on The recipes below are very specific at times, telling you exactly which words to write down on your piece of paper. You're certainly free to say things your own way instead were just giving you something you could say so that you're never at a complete loss 2 Proving an implication An enormous number of mathematical claims have the form "If P, then Q"or, equiva lently, "P implies Q". Here are some examples ·( Quadratic Formula)fax2+bx+c=0anda≠O, then x=(-b± 4ac)/2a . Goldbach's Conjecture)If n is an even integer greater than 2, then n is a sum of two rimes ·If0<x<2,then-x3+4x+1>0. There are a couple standard methods for proving an implication 2.1 Method #1 In order to prove that P implies Q 1. Write,"Assume p 2. Show that Q logically follows� Proofs 5 1.2 Proofs in Practice In principle, a proof can be any sequence of logical deductions from axioms and previously￾proved statements that concludes with the proposition in question. This freedom in con￾structing a proof can seem overwhelming at first. How do you even start a proof? Here’s the good news: many proofs follow one of a handful of standard templates. Proofs all differ in the details, of course, but these templates at least provide you with an outline to fill in. We’ll go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit together; one may give you a top­level outline while others help you at the next level of detail. And we’ll show you other, more sophisticated proof techniques later on. The recipes below are very specific at times, telling you exactly which words to write down on your piece of paper. You’re certainly free to say things your own way instead; we’re just giving you something you could say so that you’re never at a complete loss. 2 Proving an Implication An enormous number of mathematical claims have the form “If P, then Q” or, equiva￾lently, “P implies Q”. Here are some examples: • (Quadratic Formula) If ax2 + bx + c = 0 and a = 0, then x = (−b ± √b2 − 4ac)/2a. • (Goldbach’s Conjecture) If n is an even integer greater than 2, then n is a sum of two primes. • If 0 ≤ x ≤ 2, then −x3 + 4x + 1 > 0. There are a couple standard methods for proving an implication. 2.1 Method #1 In order to prove that P implies Q: 1. Write, “Assume P.” 2. Show that Q logically follows