Proving Techniques PDF

Math Month Introduction Some Terminology Proving Techniques Direct Proof Trivial Proof/Vacuous Proof Shielden Grail S. Domilies Proof by Contradiction Benguet State University Proof by...

Math Month Introduction Some Terminology Proving Techniques Direct Proof Trivial Proof/Vacuous Proof Shielden Grail S. Domilies Proof by Contradiction Benguet State University Proof by Contraposition Proof by March 22, 2024 Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 1 / 26  What is proof? Math Month Proof Introduction A proof is a logical argument that demonstrates the validity Some of a mathematical statement. Terminology Direct Proof Many famous mathematical theorems, e.g., Pythagorean Trivial theorem, Fermat’s last theorem Proof/Vacuous Proof Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 2 / 26  What is proof? Math Month Proof Introduction A proof is a logical argument that demonstrates the validity Some of a mathematical statement. Terminology Direct Proof Many famous mathematical theorems, e.g., Pythagorean Trivial theorem, Fermat’s last theorem Proof/Vacuous Proof Pythagorean Theorem Proof by Contradiction Let a, b the length of the two sides of a right triangle, and let Proof by Contraposition c be the hypotenuse. Then, a2 + b 2 = c 2. Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 2 / 26  What is proof? Math Month Proof Introduction A proof is a logical argument that demonstrates the validity Some of a mathematical statement. Terminology Direct Proof Many famous mathematical theorems, e.g., Pythagorean Trivial theorem, Fermat’s last theorem Proof/Vacuous Proof Pythagorean Theorem Proof by Contradiction Let a, b the length of the two sides of a right triangle, and let Proof by Contraposition c be the hypotenuse. Then, a2 + b 2 = c 2. Proof by Induction Fermat’s Last Theorem Proof by Cases Biconditional For any integer n greater than 2, the equation an + b n = c n Statements has no solutions for non-zero a, b, c. Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 2 / 26  Introduction Math Month Axioms Axioms are statements or propositions that are assumed to be Introduction true without requiring proof. Some Terminology Direct Proof Trivial Proof/Vacuous Proof Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 3 / 26  Introduction Math Month Axioms Axioms are statements or propositions that are assumed to be Introduction true without requiring proof. Some Terminology Direct Proof Lemma Trivial Proof/Vacuous A lemma is a minor theorem or proposition that is proven as a Proof stepping stone toward proving a larger, more significant result. Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 3 / 26  Introduction Math Month Axioms Axioms are statements or propositions that are assumed to be Introduction true without requiring proof. Some Terminology Direct Proof Lemma Trivial Proof/Vacuous A lemma is a minor theorem or proposition that is proven as a Proof stepping stone toward proving a larger, more significant result. Proof by Contradiction Proof by Corollary Contraposition A corollary is a direct consequence or immediate inference Proof by Induction drawn from a previously proven theorem or result. Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 3 / 26  Introduction Math Month Axioms Axioms are statements or propositions that are assumed to be Introduction true without requiring proof. Some Terminology Direct Proof Lemma Trivial Proof/Vacuous A lemma is a minor theorem or proposition that is proven as a Proof stepping stone toward proving a larger, more significant result. Proof by Contradiction Proof by Corollary Contraposition A corollary is a direct consequence or immediate inference Proof by Induction drawn from a previously proven theorem or result. Proof by Cases Biconditional Statements Proposition Counterexample A proposition is a statement that can be either true or false. Valid Proof? (Benguet State University) Math Month March 22, 2024 3 / 26  Types of Proof Math Month Introduction Some Terminology Direct Proof Trivial Proof/Vacuous Proof Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 4 / 26  Direct Proof Math Month Introduction Some Terminology Direct Proof There are only two steps to a direct proof: Trivial Proof/Vacuous 1 Assume that P is true. Proof Proof by 2 Use P to show that Q must be true. Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 5 / 26  Direct Proof Math Month Introduction Some Terminology Direct Proof Prove the following: Trivial For integers m and n, if m and n are odd integers, then Proof/Vacuous Proof m + n is an even integer. Proof by Contradiction If n is an odd integer, then n2 is also odd. Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 6 / 26  Trivial Proof/Vacuous Proof Math Month Introduction Some Terminology Trivial Proof: If we know q is true then p =⇒ q is true Direct Proof regardless of the truth value of p. Trivial Proof/Vacuous Vacuous Proof: If p includes other statements, and we Proof know one or more of these statements is false, then p is Proof by Contradiction false. As a result, regardless of the truth value of q, the Proof by statement ”if p then q” is considered true without Contraposition evaluating q. Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 7 / 26  Trivial Proof/Vacuous Proof Math Month Introduction Some Terminology Direct Proof Prove the two statements below: Trivial Proof/Vacuous 1 If 1+1 = 3, then 2 is greater than 1. Proof Proof by 2 If 6 and 7 are even numbers, then 6+3 = 10. Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 8 / 26  Proof by Contradiction Math Month Introduction Some Terminology Direct Proof Methods: Trivial 1 Assume that P is true. Proof/Vacuous Proof 2 Assume that ¬Q is true. Proof by Contradiction 3 Use P and ¬Q to demonstrate a contradiction. Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 9 / 26  Proof by Contradiction Math Month Introduction Some Terminology Direct Proof Trivial Prove that if 3n + 2 is odd, then n is odd, where n is an Proof/Vacuous Proof integer. Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 10 / 26  Proof by Contraposition Math Month Introduction Some Terminology Statement: P =⇒ Q Direct Proof Contrapositive Statement: ¬Q =⇒ ¬P Trivial Proof/Vacuous Proof Proof by Contradiction If one can prove P =⇒ Q, they have also proven Proof by ¬Q =⇒ ¬P, and vice versa. Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 11 / 26  Proof by Contraposition Math Month Introduction Some Terminology Direct Proof Trivial Proof/Vacuous Prove: If n2 is odd, then n is odd for any integer n. Proof Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 12 / 26  Proof by Mathematical Induction Math Month Introduction To demonstrate P =⇒ Q by induction we require that the Some truth of P and Q be expressed as a function of some ordered Terminology set S. Direct Proof 1 (Basis) Show that P =⇒ Q is valid for a specific Trivial Proof/Vacuous element k in S. Proof Proof by 2 (Inductive Hypothesis) Assume that P =⇒ Q for some Contradiction element n in S. Proof by Contraposition 3 Demonstrate that P =⇒ Q for the element n + 1 in S. Proof by Induction 4 Conclude that P =⇒ Q for all elements greater than or Proof by Cases equal to k in S. Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 13 / 26  Proof by Mathematical Induction Math Month Introduction Some Terminology Direct Proof Use induction to prove that Trivial Proof/Vacuous Proof 1 + 3 + 5 + · · · + (2n − 1) = n2. Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 14 / 26  Proof by Strong Induction Math Month Introduction Some Terminology Direct Proof Step 1. Demonstrate the base case: This is where you verify Trivial that P(k0 ) is true. Proof/Vacuous Proof Step 2. Prove the inductive step: This is where you assume Proof by that all of P(k0 ), P(k0 + 1), P(k0 + 2),... , P(k) is true. Then Contradiction you show that P(k + 1) is true. Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 15 / 26  Proof by Strong Induction Math Month Introduction Some Terminology The Fibonacci sequence is defined by Fn = Fn−1 + Fn−2 for Direct Proof integers n ≥ 0 with F1 = F2 = 1. Show that Trivial Proof/Vacuous " √ !n √ !n # Proof 1 1+ 5 1− 5 Proof by Fn = √ − Contradiction 5 2 2 Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 16 / 26  Proof by Cases Math Month Introduction Some Terminology Proof by cases says that to show (p1 ∨ p2... ∨ pk ) =⇒ q it Direct Proof suffices to show: Trivial Proof/Vacuous p1 =⇒ q Proof p2 =⇒ q Proof by Contradiction... Proof by pk =⇒ q Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 17 / 26  Proof by Cases Math Month Introduction Some Terminology Direct Proof Trivial For any natural number n, it follows that n2 + 3n + 2 is Proof/Vacuous Proof composite. Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 18 / 26  Biconditional Statements Math Month Introduction Some Terminology Direct Proof Trivial Key word: ”if and only if” Proof/Vacuous Proof Show P =⇒ Q and Q =⇒ P Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 19 / 26  Biconditional Statements Math Month Introduction Some Terminology Direct Proof Trivial Proof/Vacuous Show that a positive integer n is odd if and only if n2 is odd. Proof Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 20 / 26  Counterexamples Math Month Introduction Some Terminology Direct Proof Determine if the following statement are true. Trivial Proof/Vacuous 1 2n + 1 is prime for any natural number n. Proof Proof by 2 For all integers n such that n ≥ 0, n2 ≥ 2n. Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 21 / 26  1 = 2? Math Month Assume Introduction a=b Some Terminology ab = b 2 Direct Proof Trivial ab − a2 = b 2 − a2 Proof/Vacuous Proof a(b − a) = (b + a)(b − a) Proof by Contradiction a=b+a Proof by a = 2a Contraposition Proof by ∴1=2 Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 22 / 26  1 = 2? Math Month Assume Introduction a=b Some Terminology ab = b 2 Direct Proof Trivial ab − a2 = b 2 − a2 Proof/Vacuous Proof a(b − a) = (b + a)(b − a) Proof by Contradiction a=b+a Proof by a = 2a Contraposition Proof by ∴1=2 Induction Proof by Cases Biconditional Statements Division by zero is not allowed from b − a. Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 22 / 26  1 = 2? Math Month Assume x ̸= 0 Introduction x =x Some Terminology =⇒ x + x = 2x 2 Direct Proof {z· · · + x} = x =⇒ x| + x + Trivial x times Proof/Vacuous Proof Differentiate both sides Proof by Contradiction 1| + 1 + 1{z+ · · · + 1} = 2x Proof by Contraposition x times Proof by =⇒ x = 2x Induction Proof by Cases =⇒ 1 = 2. Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 23 / 26  1 = 2? Math Month Assume x ̸= 0 Introduction x =x Some Terminology =⇒ x + x = 2x 2 Direct Proof {z· · · + x} = x =⇒ x| + x + Trivial x times Proof/Vacuous Proof Differentiate both sides Proof by Contradiction 1| + 1 + 1{z+ · · · + 1} = 2x Proof by Contraposition x times Proof by =⇒ x = 2x Induction Proof by Cases =⇒ 1 = 2. Biconditional 2 Statements {z· · · + x} = x for non-integers Cannot do x| + x + Counterexample x times Valid Proof? (Benguet State University) Math Month March 22, 2024 23 / 26  0 = 1? Math Month Introduction Suppose we have 0. We know that Some Terminology 0=1−1 Direct Proof 0=1−1+1−1 Trivial Proof/Vacuous Proof 0 = 1 − 1 + 1 − 1 + 1 − 1 + ··· Proof by 0 = 1 + (−1 + 1) + (−1 + 1) + (−1 + 1) · · · Contradiction Proof by 0 = 1 + (−1 + 1) + (−1 + 1) + (−1 + 1) · · · Contraposition 0 = 1. Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 24 / 26  0 = 1? Math Month Introduction Suppose we have 0. We know that Some Terminology 0=1−1 Direct Proof 0=1−1+1−1 Trivial Proof/Vacuous Proof 0 = 1 − 1 + 1 − 1 + 1 − 1 + ··· Proof by 0 = 1 + (−1 + 1) + (−1 + 1) + (−1 + 1) · · · Contradiction Proof by 0 = 1 + (−1 + 1) + (−1 + 1) + (−1 + 1) · · · Contraposition 0 = 1. Proof by Induction Proof by Cases This is not possible because Grandi’s series is divergent. Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 24 / 26  Exercise Math Month Introduction Some Terminology Direct Proof 1 If 3n + 1 is even, then n ∈ N is odd. Trivial Proof/Vacuous 2 Prove or disprove: The sum of two irrational numbers is Proof irrational. Proof by Contradiction 3 Show that x is odd if and only if 5x + 4 is odd. Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 25 / 26  Math Month Introduction Some Terminology Direct Proof Trivial ‘Obvious’ is the most dangerous word in mathematics. Proof/Vacuous Proof — Eric Temple Bell Proof by Contradiction Proof by Contraposition Proof by Induction Proof by Cases Biconditional Statements Counterexample Valid Proof? (Benguet State University) Math Month March 22, 2024 26 / 26