diff options
Diffstat (limited to '1.8.md')
| -rw-r--r-- | 1.8.md | 28 |
1 files changed, 28 insertions, 0 deletions
@@ -0,0 +1,28 @@ +[\<- 1.7](1.7.md) + +--- + +# 1.8 Proof Methods p1 + +## Proof by Cases + +- Ex. Prove that `n^2 + 5n + 8` is even for all n∈ℤ. + - case 1 (n is odd): Let `n` be odd. Ǝk∈ℤ s.t. `n=2k+1`. Then `n^2 + 5n + 8` = `(2k+1)^2 + 5(2k+1) + 8` = `4k^2 + 4k + 1 + 10k + 5 + 8` = `4k^2 + 14k + 14` = `2(2k^2 + 7k + 7)` which is **even** since (2k^2 + 7k + 7)∈ℤ. + - case 2 (n is even): Let `n` be even. Ǝk∈ℤ s.t. `n=2k`. Then `n^2 + 5n + 8` = `(2k)^2 + 5(2k) + 8` = `4k^2 + 10k + 8` = `2(2k^2 + 5k + 4)` which is **even** since `2k^2 + 5k + 4` is an integer. + - ∴ `n^2 + 5n + 8` is even for all n∈ℤ + - ∴ means "therefore" + +--- + +Sometimes, the proofs of multiple cases are essentially the same, so we will say "without loss of generality" (or **WLOG**) and just show the argument for one of the similar cases and omit the others + +- Ex. Let max(x,y) be the maximum of `x` and `y`. For example, max(7.2, 11.4) = 11.4 and max(-3,-3) = -3. Similarly define min(x,y) as the minimum of `x` and `y`. +- Prove `max(a,b) - min(a,b) = |b-a|` for all a,b∈ℝ. + - We could do cases: + - Case 1: `a>=b` + - Case 2: `b>=a` + - Notice the problem is **symmetric** in a,b (`max(b,a)-min(b,a) = max(a,b)-min(a,b)`) + - `a` and `b` are interchangeable + +Proof: Let a,b∈ℝ. without loss of generality, assume `a>=b`. Then, LHS (left hand side) = `max(a,b)-min(a,b)` = `a-b`. Note `|x| = x` for `x>0` and `|x| = -x` if `x<=0`. RHS (right hand side) = `|b-a|` = `-(b-a)` = `a-b`. ∴ LHS = RHS as desired. ▣ +- We don't need to consider the other case since it would have been identical |