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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
[\<- 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
---
- To prove `p<->q`, we must show
1. `p->q`
2. `q->p`
- Ex. Let n∈ℤ. Prove `n` is odd iff `n^2` is odd.
Proof:
- (=>)(implication arrow) "If `n` is odd, then `n^2` is odd"
- We already proved this in [1.7](1.7.md)
- (<=)(implication arrow; reverse direction) "If `n^2` is odd, then `n` is odd"
- **Direct Proof**:
- Ǝk∈ℤ s.t. `n^2 = 2k+1`
- `n = ±sqrt(2k+1)`
- not sure if `±sqrt(2k+1)` is an integer :(
- **Contraposition**: "If `n` is even, then `n^2` is even`
- Let `n` be even. Ǝk∈ℤ s.t. `n = 2k`.
- Then, `n^2 = (2k)^2 = 4k^2 = 2(2k^2)` which is even since `(2k)^2`∈ℤ
- ∴ `n` is odd iff `n^2` is odd. ▣
- Definition: A **theorem** is a mathematical statement that can be shown/proven to be true
- Definition: A **proposition** is a "less important" **theorem**
- Definition: A **corollary** is a theorem that is a direct result of another theorem
- Ex. Let n∈ℤ. `n` is even iff `n^2` is even
- Proof Sketch: Both directions are contrapositives of the above example
---
# 1.8 Proof Methods p2
- Proposition: `[(p->q)^(q->r)] -> (p->r)` is a tautology.
- Transitive Law
- Suppose we want to show `p1 <-> p2 <-> p3 <-> ... <-> pn` for `n >= 3`. When this is true we say:
- "the following are equivalent" (TFAE):
1. `p1`
2. `p2`
3. `p3`
n. `pn`
- To prove this, it is sufficient to show: `p1 -> p2 -> p3 -> ... -> pn -> p1`
- Ex. Let n∈ℤ. Prove TFAE:
1. `5n+4` is even
2. `n^2` is even
3. `n-3` is odd.
- Proof: (iii) -> (ii)
- Let n∈ℤ s.t. `n-3` is odd
- Then, Ǝk∈ℤ s.t. `n-3 = 2k+1`
- `n^2` = `(2k+4)^2` = `4k^2 + 16k + 16` = `2(2k^2 + 8k + 8)`
- It's **even** since `2k^2 + 8k + 8`∈ℤ
- Proof: (ii) -> (i)
- Let n∈ℤ s.t. `n^2` is even
- We have previously proved that n is even iff n^2 is even. Ǝl∈ℤ s.t. `n = 2l`
- Then, `5n+4` = `5(2l)+4` = `10l+4`
- It's **even** since `5l+4`∈ℤ
- Proof: (i) -> (iii)
- Direct Proof:
- `5n+4 = 2k`
- `n = (2k-4)/5`... too hard, lets use a different strategy
- Contrapositive: "If `n-3` is even, then `5n+4` is odd"
- Let n∈ℤ s.t. `n-3` is even
- Ǝk∈ℤ s.t. `n-3 = 2k`
- Then, `n = 2k+3`, so `5n+4` = `5(2k+3) + 4` = `10k+15+4` = `10k+19` = `10k + 18 + 1` = `2(5k+9) + 1`
- It's **odd** since `5k+9`∈ℤ
∴ (i), (ii), and (iii) are equivalent. ▣
---
Ex. Prove that for all nonnegative reals, `x` and `y`, `(x+y)/2 >= sqrt(xy)`
- The left hand is the "Arithmetic Mean"
- The right hand is called the "Geometric Mean
- AM - GM Inequality for `n = 2`
- Direct Proof is hard
- We will use a new method called **Backwards Reasoning**
### Backward Reasoning
Show conclusion is **equivalent** to a true statement
- Proof:
- `(x+y)/2 >= sqrt(xy)`
- <-> `((x+y)/2)^2 >= xy`
- <-> shows that going from the previous step to this step is reversible
- squaring both sides preserves the inequality
- <-> `(x^2 + 2xy + y^2)/4 >= xy`
- <-> `(x^2 + 2xy + y^2) >= 4xy`
- <-> `(x^2 - 2xy + y^2) >= 0`
- <-> `(x-y)^2 >= 0`
- `a^2 >= 0` is a tautology; it's called "Trivial Inequality"
- `≡T`
- Since `(x+y)/2 >= sqrt(xy)` is equivalent to a true statement, this inequality is also true
- **Note**: For a proof using Backward Reasoning, ensure each step is reversible. Failure to do so could lead to Circular Reasoning
---
Ex: Prove `sqrt(2)` is irrational.
- Proof:
- Assume for the sake of contradiction that `sqrt(2)`∈ℚ
- Then, `sqrt(2)` = `a/b` for some a,b∈ℤ, `b!=0`
- Suppose `a/b` is written in "lowest terms"
- `(sqrt(2))^2 = (a/b)^2`
- -> `2 = (a^2)/(b^2)`
- -> `2b^2 = a^2`
- This means `a^2` is **even** since `b^2`∈ℤ
- Recall: "`a` is even iff `a^2` is even"
- This implies that `a` is even.
- Ǝk∈ℤ s.t. `a=2k`
- Substituting `a=2k` into `2b^2 = a^2`, we get `2b^2 = (2k)^2`
- -> `2b^2 = 4k^2`
- -> `b^2 = 2k^2`
- This means `b^2` is even since `k^2`∈ℤ
- This implies that `b` is even
- However, `a` and `b` being even **contradicts** the assumption that `a/b` is written in lowest terms
- As a result, `sqrt(2)` is irrational. ▣
---
[2.1 ->](2.1.md)
|
