MAT299 Chapter Notes - Chapter 3: Pigeonhole Principle, Contraposition, Distributive Property
18 May 2020
Department
Course
Professor
Document Summary
This section discusses some common proof methods for validating theorems or supporting claims: direct proof. This method uses axioms/ proven theorems as starting point, or combine them with reasonable premises to derive conclusion; for instance, If integers m and n are even, then their sum is also even. *being even means an integer is divisible by 2 with remainder of 0; it implies that: C,d s. t. m=2 c, n=2 d m+n = 2 c+2 d m+n = 2 (c+d) (distributive law) Note that sum of integers m and n could be expressed as multiple of 2, and therefore is divisible by 2 (q. e. d: proof by contradiction. This method begins with an assumption and then prove that the derived conclusion is false; then it implies that negation of the assumption is true. Proof of pigeonhole principle: if there are k pigeonholes and k+1 pigeons to fit into them, there would be at least 1 hole that contains 2 pigeons.
