Post-class 04/15

2 files changed, 93 insertions, 0 deletions

diff --git a/1.7.md b/1.7.md
index 5508169..1fd525a 100644
--- a/1.7.md
+++ b/1.7.md
@@ -109,3 +109,68 @@ Scratch Work
 
 - Proof:
 	- We proceed by contraposition, and assume a,b, are arbitrary odd integers. This means Ǝk,l∈ℤ s.t. a=2k+1 and b=2l+1. ab = (2k+1)(2l+1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1. Since 2kl+k+l∈ℤ, ab is odd. ▣
+
+---
+
+### Proof by Contradiction
+
+**Idea**: To show `p->q` **by contradiction**
+1. First assume q is false (┓q is true)
+2. Show this leads to a **contradiction**
+3. This means our assumption that q is false is **wrong**, which means q is true
+
+- Ex. Prove that there are no positive integer solutions to `x^2 - y^2 = 1`
+	- Tipoff to Contradiction: the word "no"
+	- Try contradition:
+
+Scratch Work
+
+|Know/Assumptions|Want to Show|
+|----------------|------------|
+|Ǝx,y∈ℤ^+ s.t. x^2 - y^2 = 1|Leads to a Contradiction|
+||Maybe show both x and y are not positive integers|
+
+Proof: Assume for the sake of contradiction that there are x,y∈ℤ^+ s.t. `x^2 - y^2 = 1`. Then, `(x-y)(x+y) = 1`. Since x,y∈ℤ, x-y∈ℤ and x+y∈ℤ. There are two possibilities: if both equal 1 or both equal -1. `2x=2` -> `x=1` and `y=0` is a solution. `2x=-2` -> `x=-1` and `y=0`. Neither of these solutions work, since in both, x or y are not ∈ℤ^+. This **contradicts** our assumption that x,y are positive integers. It follows that there are no positive integer solutions to `x^2 - y^2 = 1`. ▣
+
+---
+
+Recall: An **irrational** number is real, but not rational. (cannot be written as a ratio of integers)
+- e.g. π, sqrt(2), sqrt(17), e
+
+- Ex. Prove that the sum of a rational and an irrational number is irrational.
+	- Reworded: "Prove if x is ratinoal and y is irratino, then x+y is irrational"
+
+Direct Proof? x+y = (a/b)+y (a,b∈ℤ, b!=0) = (a +yb)/b. We know the denominator is an integer, but we're not sure if the numerator is an integer :(
+
+Contraposition?
+- "If x+y is rational, then x is irrational or y is rational"
+- x+y = a/b: a,b∈ℤ, b!=0
+- It's hard to say something about x,y individually :(
+	- It is possible, however
+
+### Proof by Contradition:
+
+Scratch Work
+
+|Known/Assumptions|Want to Show|
+|-----------------|------------|
+|x is rational    |Want to show Contradiction|
+|y is irrational  |Maybe x is irrational or y is rational|
+|x+y is ratioan   ||
+|`x` + `y` = `x+y`||
+|`y` = `x+y` - `x`||
+
+Proof: Let x be rational and y be irrational. Assume for the sake of contradiction that x+y is rational. Then, x+y = a/b for some a,b∈ℤ, b!=0. Also, x = c/d for some c,d∈ℤ, d!=0. Then, `y=(x+y)-x` = `(a/b) - (c/d)` = `(ad - cb)/(bd)`∈ℚ since `ad-cd` and `bd` are integers and `bd!=0`. This contradicts the statement that y is irrational. It follows that `x+y` is irrational. ▣
+
+---
+
+## Tips
+
+1. For proofs about **rationals**, if x∈ℚ, then `x=(a/b)` for some a,b∈ℤ, b!=0
+2. For proofs about ℤ, avoid operations that give you non-integers like division or squareroot
+
+Warning: When proving `p->q`, never assume what you are trying to prove (q) (it's called **circular reasoning**)
+
+---
+
+[1.8 ->](1.8.md)
diff --git a/1.8.md b/1.8.md
new file mode 100644
index 0000000..a783ec9
--- /dev/null
+++ b/1.8.md
@@ -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