Direct Proof
Prove that the product of two consecutive odd numbers is always odd
- Let and be the two consecutive odd numbers. 1.1. Without loss of generality, assume that , hence 1.2. Now, for some integer (by definition of odd numbers) 1.3. Similarly, 1.4. Therefore, (by basic algebra) 1.5. let which is an integer (by closure of integers under addition and multiplication) 1.6. Then, , which is odd (by definition of odd numbers)
- Therefore, the product of two consecutive odd numbers is always odd
WLOG
“Without loss of generality” may be abbreviated to WLOG
- This is used before an assumption in a proof which narrows the premise to some special case
- It implies that the proof of this special case can be easily applied to all other cases
Disproof by Counter Example
Prove that the following statement is not true: The product of two irrational numbers is always irrational.
- Let the two irrational numbers be and 1.1. Then, (by basic algebra), which , which is a rational number
- Therefore, the statement “the product of two irrational numbers is always irrational” is not true
Proof by Construction
Prove the following: s.t. (such that) and
- Let
- Note that and
- Also,
Notes
- Proof by construction is where you explicitly find the value with the correct properties
- It is a form of Direct Proof
- No need to explain how you found the result (e.g. 17), you just need to show that the result has the required properties
Proof by Contradiction
- Assume that ~S (not S) is true
- Based on this, use known facts and theorems to arrive at a logical contradiction.
- Since every step of the argument thus far is logically correct, the problem must lie in the assumption (that ~S is true)
- Thus, it can be concluded that ~S is false, that is, S is true
Example
Prove that is irrational
- Suppose not, that is rational 1.1. Then, s.t. (by definition of rational numbers) 1.2. Convert to its lowest term, 1.3. (by basic algebra) (note: this is done by squaring both sides of ) 1.4. Hence, is even (by definition of even numbers, as is an integer by closure) 1.5. Hence, is even (by Proposition 4.6.4 (has been proved somewhere else)) 1.6. Let ; Substituting into 1.3: , or 1.7. Hence, is even (by definition of even numbers) 1.8. Hence, is even (by Proposition 4.6.4) 1.9. So both and are even, but this contradicts that is in its lowers term
- Therefore, the assumption that is rational is false
- Hence is irrational
Proof by Exhaustion
Prove that the difference of two consecutive squares between 30 and 100 is odd
- The squares between 30 and 100 are 36, 49, 64 and 81 1.1. Case 1: which is odd 1.2. Case 2: which is odd 1.3. Case 3: which is odd
- Therefore, the difference of two consecutive squares between 30 and 100 is odd
Note
- Also known as proof by cases, or proof by brute force
- This is suitable when the number of cases is finite