1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
|
