=========================================================================== CSC 236 Lecture Summary for Week 2 Winter 2012 =========================================================================== Definitions (reminders): - Integer m is "divisible" by integer n (or n is a "divisor" of m) if m/n is an integer (i.e., -] k, m = k*n). - Integer n is "prime" if n >= 2 and n has no divisor in the set {2,...,n-1} (i.e., n's only divisors are 1 and n). - A "prime factorization" of an integer n is a sequence of prime numbers whose product equals n, e.g., 84 = 2 * 2 * 3 * 7 -- because it's a sequence, it can contain the same number multiple times. Example 4: All integers >= 2 have a prime factorization. 0. P(n): n has a prime factorization, i.e., there is a sequence of prime numbers whose product equals n. (Hard to express purely with symbols.) 1. Base Case: (Remember, we want to prove P(n) for all n >= 2.) Prove P(2): 2 has a prime factorization. 2 is its own prime factorization, so P(2) holds. 2. Ind. Hyp.: Let n >= 2 and suppose P(n): n has a prime factorization. 3. Ind. Step: Prove P(n+1): n+1 has a prime factorization. Problem! No obvious relationship between prime factorization of n+1 and prime factorization of n (e.g., 84 = 2*2*3*7, 85 = 5*17). ------------------ Complete induction ------------------ Let's think about simple induction. When we prove P(0) /\ \-/ n, P(n) -> P(n+1), what allows us to conclude P(k) for some k? We know P(0), and P(0) -> P(1) so P(1), and P(1) -> P(2) so P(2), ..., and P(k-1) -> P(k) so P(k). Notice: by the time we use this to conclude P(k), we actually know each of P(0), P(1), ..., P(k-1) is true. This is the basis for the Principle of Complete Induction (also called "Strong Induction" or "Course of Values Induction" in some textbooks). ( \-/ n, (\-/ k < n, P(k)) -> P(n) ) -> \-/ n, P(n). In English: if, for any n, P(n) is true when P(k) is true for all k < n, then P(n) is true for all n. Suppose we prove \-/ n, (\-/ k < n, P(k)) -> P(n). - Why does P(0) holds? Because we proved (\-/ k < 0, P(k)) -> P(0), and \-/ k < 0, P(k) is vacuously true (universal quantifier over empty domain), which means we proved P(0). Note 1: this corresponds to base case in simple induction. Note 2: here's another way to see that \-/ k < 0, P(k) is true: recall that \-/ k < 0, P(k) is shorthand for \-/ k (- N, k < 0 -> P(k); but k < 0 is false for all k (- N, so k < 0 -> P(k) is vacuously true, i.e., \-/ k (- N, k < 0 -> P(k) is true! - Why does P(1) holds? Because we proved (\-/ k < 1, P(k)) -> P(1), and \-/ k < 1, P(k) is true (P(0) is true). - Why does P(2) holds? Because we proved (\-/ k < 2, P(k)) -> P(2), and \-/ k < 2, P(k) is true (P(0) and P(1) are true). - Etc. Back to example of prime factorization. Goal: Prove \-/ n >= 2, n has a prime factorization. Use complete induction, except modified to conclude property for all n >= 2. 0. P(n): n has a prime factorization, i.e., there is a sequence of prime numbers whose product equals n. 1. (No explicit base case required with complete induction.) 2. Ind. Hyp.: Let n >= 2 and suppose that \-/ k, 2 <= k < n -> k has a prime factorization. 3. Ind. Step: Prove P(n): n has a prime factorization. Now what? Either n is prime or it is not. Case 1: If n is prime, then n is its own prime factorization. Case 2: If n is not prime, then it has a divisor a such that a > 1 and a < n, i.e., n = a * b with 2 <= a < n and 2 <= b < n. By the IH, both a and b have prime factorizations, whose concatenation is a prime factorization of n. 4. Conclusion: By complete induction, \-/ n >= 2, n has a prime factorization. Example 5: Chocolate bars are divided into squares. How many breaks does it take to split up a chocolate bar into individual squares? Explore: 1x1, 1x2, 1x3, 2x2, 2x3, 2x4, 3x3, 3x4, ... Q: What quantity to do induction on? A: Could try length, width and do nested induction. But messy! Try some combined measure instead, e.g., total number of squares. Conjecture: For all n >= 1, every chocolate bar with n squares can be split up (into individual squares) with n-1 breaks. Q: Does this handle every possible chocolate bar? How do we know there are chocolate bars with n squares for every n? A: Think about it -- ask if you're not sure! Let's practice using complete induction. 0. P(n): All chocolate bars with n squares can be split up with n-1 breaks. 2. Ind. Hyp.: Let n >= 1 and suppose P(1), ..., P(n-1) all hold, i.e., all chocolate bars with 1 <= k < n squares can be split up with k-1 breaks. 3. Ind. Step: Prove P(n), i.e., all chocolate bars with n squares can be split up with n-1 breaks. Consider an arbitrary chocolate bar C with n squares. Idea: Make one break into two pieces and think about each piece. Careful! Can this always be done? (Hint: think about value of n.) Case 1: If n = 1, then C is already split up and needs 0 = 1-1 breaks. So P(n) holds. Case 2: If n > 1, then make one break into two pieces A and B, with a and b squares, respectively. Note that 1 <= a < n, 1 <= b < n, and n = a + b. By the IH, A can be split up with a-1 breaks and B can be split up with b-1 breaks. Hence, C can be entirely split up with 1 + a-1 + b-1 = a + b - 1 = n - 1 breaks. Hence, P(n) holds. NOTE: We need complete induction here because A and B could contain any number of squares smaller than n, not necessarily n-1. In every case, P(n) holds. 4. Conclusion: By complete induction, \-/ n >= 1, P(n) (for all n >= 1, every chocolate bar with n squares can be split up with n-1 breaks). Format: Proofs using complete induction sometimes written in style closer to simple induction, using one (or more) base case(s). Only difference then is in form of inductive hypothesis. For example, previous proof's format could look like: 0. Define P(n). 1. Base Case(s): Prove P(1). [Case 1 in proof above.] 2. Ind. Hyp.: Let n > 1 (careful: n is next value to prove, not last value proven in base case) and suppose P(1), ..., P(n-1) hold. 3. Ind. Step: Prove P(n). [Case 2 in proof above.] 4. Conclusion: By complete induction, \-/ n >= 1, P(n). -------------------- Structural Induction -------------------- Why is it OK to tweak the structure of inductive proofs? One reason: possible to achieve same result by defining P(n) appropriately and using "standard" inductive structure. Another reason: structure of proof simply follows structure of N. Structure of N? N can be defined recursively. Formally, define set S as follows: - 0 (- S, - if n (- S, then n+1 (- S, - S contains nothing else. Then S = N: - every element in S is a natural number (by construction and because of last clause), - every natural number belongs to S (every natural number is 1 more than another natural number, except for 0). Principle of simple induction just follows this recursive structure for N. What about other proof structures? Also follows structure of set. For example, S = { n (- N : n >= 2 } is uniquely characterized by properties: - 2 (- S, - if n (- S, then n+1 (- S, - S contains nothing else. So to prove \-/ n >= 2, P(n), we can use inductive structure with base case 2, inductive hypothesis that assumes n >= 2, and inductive step that works with n+1. Example 2: Suppose we want to prove \-/ n (- Z, P(n), for some predicate P. - Define Z recursively: . 0 (- Z, . \-/ n (- Z, n+1 (- Z /\ n-1 (- Z, . Z contains nothing else. - Write down inductive structure that follows recursive definition: 1. Base Case: Prove P(0). 2. Ind. Hyp.: Assume n (- Z and P(n). 3. Ind. Step: Prove P(n+1) and P(n-1). 4. Conclusion: \-/ n (- Z, P(n). But this idea is more general: it applies to *any* set defined recursively, not just sets of numbers! You will see an example in tutorial.