September 8 * Proof By Induction How do we prove something is true about a finite set? Show it is true for each element. How do we prove something is true about an infinite set? One method is to use proof by induction. 1. Show that the property applies to one specific member of the set (Base Case) 2. Show that IF the property holds for N members of the set (Inductive Hypothesis), then 3. The property MUST hold for N+1 members of the set (Inductive Step) If we can prove the base case and the inductive step, then we could apply the inductive step first to the base case producing the next case (now true for 2 instances), then apply it again (now true for 3 instances), and so on, to show the property holds for each element of the set. Inductive proofs are often used to prove properties hold for infinitely large sets. - Example Prove that for any n>=0 (n in N), sum_{x=1}^{n} x = (n+1)n / 2. 1) Base case Let n = 0. The sum on the left side is 0, the expression on the right is 1*0 / 2 = 0. Can prove similarly for n=1, n=2 n=2 1 + 2 = 2*3 / 2, so the property holds 2) Inductive hypothesis Assume the property is true for n=k. 3) Inductive Step (if true for n=k, is it then true for n=k+1?) The left side is 1 + 2 + 3 + ... + k + k+1, or (sum_{x=1}{k} x) + k+1 Plugging in the formula we know to be true for n=k, we get the left hand side = ((k+1)k / 2) + k+1, which equals (k+1)k + 2(k+1) k^2 + 3k + 2 (k+2)(k+1) --------------- = ------------ = ----------, 2 2 2 which is the right hand side of the equation for n=k+1. Thus the property holds. - Example Prove that for any n>=0 (n in N), sum_{i=1}{n} i^2 = n(n+1)(2n+1) ------------. 6 1) Base case. Let n=0, left side = 0, right side = 0, property holds. 2) Inductive hypothesis. True for n-1 (another way of rephrasing the same approach). 3) Inductive Step. Is it then true for n? Left side = (n-1)n(2n-1) (n^2 - n)(2n-2) ------------ + n^2 = --------------- 6 6 2n^3 - 2n^2 - 2n^2 + 2n + 6n^2 2n^3 + 3n^2 + 2n n(n+1)(2n+1) = ------------------------------ = ----------------- = ------------ 6 6 6 Thus the property holds. * Pigeonhole Principle Example: If you have a drawer full of black and white socks, how many socks must you select before you have at least one pair? You must select three socks before you have a pair. The number of "pigeonholes", or colors, is two. When the number of socks exceeds the number of possible colors, at least two must be the same color. "Pigeonholes" were types of mail slots. If there are x pieces of mail and y mail slots, x>y, then at least one mail slot will have two pieces of mail. If there are more pigeons than pigeonholes, then some pigeonhole must contain two or more pigeons. More generally, if there are more than k times as many pigeons as pigeonholes, then some pigeonhole must contain at least k+1 pigeons. If A and B are nonempty finite sets and |A|>|B|, then there is no one-to-one function from A to B. Example: Two people in NYC must have the same number of hairs on their heads. NYC has over 7.5 million people, the average scalp contains 100,000 hairs. In fact, we should be able to fill a subway car with 75 New Yorkesr all of whom have the same number of hairs on their head. Example: There are 20 small towns in a region of west Texas. We want 3 people from one of these towns to help us with a survey of their town. We advertise in a newspaper that reaches all 20 towns. How many responses to our ad do we need? We need at least 41 response (two from each town and one more) * Languages and Strings To study the theory of computation we need to consider models of machines, models of the data they manipulate and models of the functions they perform. We will represent the data computers manipulate as strings of symbols. - symbols Any representation component 1, a, z, 110, $, ... - alphabet A nonempty finite set of symbols English alphabet, for example Sigma = {0,1} is an alphabet that we will use often, this is the "binary alphabet" - string A combination of symbols, order is important (abc <> cba) One special string is the empty string (no symbols), represented by epsilon, labmda, e We will often use the variables u, v, w, x, y, z to represent entire strings. The "length" of a string is the length of the sequence. - language A subset of the power set of an alphabet (a set of strings) A set of strings over a specific alphabet (a language over an alphabet) Sigma* is the language over the alphabet Sigma Sigma* = {e, 0, 1, 00, 01, 10, 11, 000, 111, ...} Two strings over the same alphabet can be combined to form a third string using "concatenation". This is written x.y or xy. This is the string x followed by the string y. w = x.y iff |w| = |x| + |y|, w(j) = x(j) for j=1, ..., |x|, and w(|x| + j) = y(j) for j=1, ..., |y|. Concatenation is associative (wx)y = w(xy) for any strings w, x, and y. A string v is a "substring" of a string w iff there are strings x and y (x or y could be empty) s.t. w = xvy. Every string is a substring of itself. If w = xv, then v is a suffix of w. If w = vy, then v is a prefix of w. Common English prefixes are "in", "anti", "super" infamous, insupportive, insufficient supersaturate, supercharge, superhuman Common English suffixes are "ly", "tion" sufficiently, commotion Inductive definition of concatenation (recursive definition) w^0 = e w^{i+1} = w^i . w, i>=0 w^1 = w (do)^2 = dodo We can also concatenate languages. If L1 and L2 are languages over alphabet sigma, L = L1.L2 = L1L2, where L = {w: w = x.y for some x in L1 and y in L2}. L* = L^n, n>=0 (n in N) This is called the Kleene closure or Kleene star of a single language. L+ = L^n, n>=1 (n in N+) Let X be language {a, b, c} and Y be language {abb, ba}. Then XY = {aabb, babb, cabb, aba, bba, cba} X^0 = {e} X^1 = X = {a,b,c} X^2 = XX = {aa, ab, ac, ba, bb, bc, ca, cb, cc} Inductive definition of reverse w^R is the reverse of a string 1. If |w| = 0, then w^R = w = e 2. If |w| = n+1 > 0, then w = ua for a in Sigma, and w^R = au^R - Show inductive proof on strings. Prove that for strings w and x, (wx)^R = x^Rw^R. (superhuman)^R = (human)^R(super)^R We will prove by induction on the length of string x. 1) Base case. Let |x| = 0. Then x = e and (wx)^R = w^R = x^Rw^R. 2) Inductive Hypothesis. Assume true for all strings x of length <= n. 3) Inductive Step. Show that property then holds for x length=n+1. We know x = va, where |v| = n and a in Sigma (a is a single character). Then (wx)^R = (w(va))^R = ((wv)a)^R (associativity of concatenation) = a(wv)^R (definition of reverse) = a(v^Rw^R) (inductive hypothesis) = (av^R)w^R (associativity of concatenation) = (va)^Rw^R (definition of reverse) = x^Rw^R Thus the property holds. Q.E.D.