Two way bounding
def: prove $f(x) = k$ by proving both $f(x)\leq k$ and $f(x)\geq k$
Suppose that T is an equilateral triangle with sides of length 2 units We can place a maximum of four points in the triangle such that every pair of points are more than 1 unit apart.
To show that 4 is the maximum number of points we can place with the required separations, we need to show that it’s possible to place 4 points, but it is not possible to place 5 points
To show that the maximum is at least four, notice that we can place three points at the corners of the triangle and one point in the center. The points at the corners are two units apart. To see that the point in the center is more than one unit from any corner, notice that the center, the corner, and the midpoint of the side form a right triangle.
To show that the maximum number of points cannot be greater than four, divide up the triangle into four smaller equilateral triangles as follows:
Suppose we tried to place five or more points into the big triangle. Since there are only four small triangles, by the pigeonhole principle, some small triangle would have to contain at least two points. But since the small triangle has side length only 1, these points can’t be separated by more than one unit.
Graph coloring
A coloring of a graph G assigns a color to each node of G, with the restriction that two adjacent nodes never have the same color.
Complete graph: $K_n$ need n colors since each nodes are adjacent
Standard proof: To establish that n is the chromatic number for a graph G, we need to establish two facts:
- χ(G) ≤ n: G can be colored with n colors.
- χ(G) ≥ n: G cannot be colored with less than n colors
Set Equality
prove set $A$ = $B$ by proving both $A ⊆ B$ and $B ⊆ A$
Let A = {15p + 9q | p, q ∈ Z} Then A = {multiples of 3}
(1) Show that A ⊆ {multiples of 3}.
Let x be an element of A. By the definition of A, x = 15s + 9t, for some integers s and t.
But then x = 3(5s + 3t). 4s + 3t is an integer, since s and t are integers. So x is a multiple of 3.
(2) Show that {multiples of 3} ⊆ A.
Notice that (*) 15 · (−1) + 9 · 2 = 3. Let x be a multiple of 3. Then x = 3n for some integer n.
Substituting (*) into this equation, we get x = (15 ·(−1)+ 9 · 2)n. So x = 15 · (−n) + 9 · (2n). So x is an element of A.
Since we’ve shown that A ⊆ {multiples of 3} and {multiples of 3} ⊆ A, we can conclude that A = {multiples of 3}.
Simple Induction
Mathematical induction is a technique for showing that a statement P(n) is true for all natural numbers n, or for some infinite subset of the natural numbers
Proving
P(n) is true for all positive integers n.
Proof: We’ll use induction on n.
Base: We need to show that P(1) is true.
Induction: Suppose that P(n) is true for n = 1, 2, . . . , k−1. We need to show that P(k) is true.
Why make sense: Domino Theory/ Recursion fairy/ Defining property of the integers
Induction is similar to recursion which applied on bases firstly and then prove another value to be true and continues on till prove every infinite subset of nature number.
P(n) is $\sum_{i=1}^ni=\frac{n(n+1)}{2}$, proving if this proposition is true
We will show that $\sum_{i=1}^ni=\frac{n(n+1)}{2}$ for any positive integer n, using induction on n.
Base: We need to show that the formula holds for $n = 1$. $\sum_{i=1}^1i=\frac{1\times2}{2}=1$. And also $\frac{1\times2}{2}=1$. So the two are equal for $n=1$
Induction: Suppose that $\sum_{i=1}^ni=\frac{n(n+1)}{2}$ for n = 1, 2, . . . , k − 1. We need to show that $\sum_{i=1}^ki=\frac{k(k+1)}{2}$. By the definition of summation notation, $\sum_{i=1}^ki=(\sum_{i=1}^{k-1}i)+k$ Our inductive hypothesis states that at n = k − 1, $\sum_{i=1}^{k-1}i=\frac{(k-1)k}{2}$. Combine the two equation, we get $\sum_{i=1}^ki=\frac{k(k+1)}{2}$
Q.E.D.
For any natural number $n$, $n^3 − n$ is divisible by 3
Proof: by induction on n
Base: Let $n=0$. Then, $n^3-n=0^3-0=0$ which is divisible by 3
Induction: Suppose $n^3-n$ is divisible by 3, for $n=0, 1...,k$. we need to show that $(k+1)^3-(k+1)$ is divisible by 3.
$$(k+1)^3-(k+1)=(k^3+3k^2+3k+1)-(k+1)=(k^3-k)+3(k^2+k)$$
From the inductive hypothesis, $(k^3 − k)$ is divisible by 3. And $3(k^2 + k)$ is divisible by 3 since $(k^2 + k)$ is an integer. So their sum is divisible by 3. That is $(k + 1)^3 − (k + 1)$ is divisible by 3.
Geometrical
For any positive integer D, if all nodes in a graph G have degree ≤ D, then G can be colored with D + 1 colors.
The objects involved in this claim are graphs. To apply induction to objects like graphs, we organize our objects by their size. Each step in the induction process will show that the claim holds for all objects of a particular (integer) size. For graphs, the “size” would typically be either the number of nodes or the number of edges. For this proof, it’s most convenient to use the number of nodes.
Proof: Let’s pick a positive integer D and prove the claim by induction on the number of nodes in G.
Base: Since D ≥ 1, the graph with just one node can obviously be colored with D + 1 colors.
Induction: Suppose that any graph with at most k −1 nodes and maximum node degree ≤ D can be colored with D + 1 colors. Let G be a graph with k nodes and maximum node degree ≤ D. Remove some node v (and its edges) from G to create a smaller graph G′ . G′ has k − 1 nodes. Also, the maximum node degree of G′ is no larger than D, because removing a node can’t increase the degree. So, by the inductive hypothesis, G′ can be colored with D + 1 colors. Because v has at most D neighbors, its neighbors are only using D of the available colors, leaving a spare color that we can assign to v. The coloring of G′ can be extended to a coloring of G with D + 1 colors.
Postage example
Strong inductive step: assumed that P(n) was true for all values of n from the base up through k − 1
Weak inductive step: just assumed that P(k − 1) was true
