[\<- 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)