CS 70 Discrete Mathematics for CSFall 2006 Papadimit rio u & Vazirani Lecture 3InductionInduction is an extremeley powerful tool in mathematics. It is a way of proving propositions thathold for all natural numbers (i.e., universally quantified ∀k ∈ N):1) ∀k ∈ N, 0 + 1 + 2 + 3 + · · · + k =k(k+1)22) ∀k ∈ N, th e sum of the first k odd numbers is k2.3) Any graph with k vertices and k edges contains a cycle.Each of these propositions is of the form ∀k ∈ N P (k). For example, in the first proposition, P (k)is the statement 0 + 1 + · · · + k =k(k+1)2, P (0) says 0 =0(0+1)2, P (1) says 0 + 1 =1(1+1)2, etc. Theprinciple of induction asserts that you can prove P (k) is true ∀k ∈ N, by following these threesteps:Base Case: Prove that P (0) is true.Inductive Hypothesis: Assume that P (k) is true.Inductive Step: Prove that P (k + 1) is true.The prin ciple of induction formally says that if P (0) and ∀n ∈ N (P (n) =⇒ P (n + 1)), then∀n ∈ N P (n). Intuitively, the base case says that P (0) holds, while the indu ctive s tep says th atP (0) =⇒ P (1), and P (1) =⇒ P (2), and so on. The fact that this domino effect eventually showsthat ∀n ∈ N P (n) is what the principle of induction (or the induction axiom) states. In fact,dominoes are a wonderful analogy: we have a domino for each proposition P (k). The dominoes arelined up so that if the kthdomino is knocked over, then it in turn knocks over the k + 1st. Knockingover the kthdomino corresponds to proving P (k) is true. So the induction step corresponds to thefact that the kthdomino knocks over the k + 1stdomino. Now, if we knock over the first domino(the one numbered 0), then this s ets off a chain reaction th at knocks down all th e dominoes.Theorem: ∀k ∈ N,kXi=0i =k(k + 1)2.Proof (by induction on k):Base Case: P (0) asserts:0Xi=0i =0(0 + 1)2. This clearly holds, since the left and r ight handsides both equal 0.1Inductive Hypothesis: Assume P (k) is true. That is,kXi=0i =k(k + 1)2.Inductive Step: We must show P (k + 1). That is,k+1Xi=0i =(k + 1)(k + 2)2:k+1Xi=0i = (kXi=0i) + (k + 1)=k(k + 1)2+ (k + 1) (by the inductive hypothesis)= (k + 1)(k2+ 1)=(k + 1)(k + 2)2Note the structure of the indu ctive step. You try to show P (k +1) with the assum ption that P (k) istrue. The idea is that P (k + 1) by itself is a difficult proposition to prove. Many difficult problemsin computer science are solved by breaking the problem into smaller, easier ones. This is preciselywhat we did in the inductive step - P (k + 1) is difficult to prove, but we were able to recursivelydefine it in terms of P (k).We will now look at another proof by induction, but first we w ill introduce some notation and adefinition for divisibility. We write a|b (a divides b, or b is divisible by a), and define divisibility asfollows: for all integers a and b, a|b if and only if for some integer q, b = aq.Theorem: ∀n ∈ N, n3− n is divisible by 3.Proof (by ind uction over n):Base Case: P (0) asserts that 3|(03− 0) or 3|0, which is clearly true (since 0 = 3 · 0).Inductive Hypothesis: Assume P (n) is true. That is, 3|(n3− n).Inductive Step: We must sh ow that P (n + 1) is true, which asserts that 3|((n + 1)3− (n + 1)).Let u s expand this out:(n + 1)3− (n + 1) = n3+ 3n2+ 3n + 1 − (n + 1)= (n3− n) + 3n2+ 3n= 3q + 3(n2+ n), q ∈ Z (by the inductive hypothesis)= 3(q + n2+ n)Hence, by the principle of induction, ∀n ∈ N , 3|(n3− n).The next example we will look at is an inequality between two functions of n. Such inequalities areuseful in computer science when showing that one algorithm is more efficient than another. Noticethat for this example, our base case does not begin at n = 0.Theorem: ∀n ∈ N, n > 1 =⇒ n! < nn.Proof (by ind uction over n):CS 70, Fall 2006, Lecture 3 2Base Case: P (2) asserts that 2! < 22, or 2 < 4, which is clearly true.Inductive Hypothesis: Assume P (n) is true (i.e., n! < nn).Inductive Step: We must show P (n + 1), w hich states that (n + 1)! < (n + 1)n+1. Let usbegin with the left side of the inequality:(n + 1)! = (n + 1) · n!< (n + 1) · nn(by the inductive hypothesis)< (n + 1) · (n + 1)n= (n + 1)n+1Hence, by the induction principle, ∀n ∈ N, if n > 1, then n! < nn.Induction is a widely applicable proof techniqu e. We now turn to a geometrical example:Two Color Theorem: There is a famous theorem called the four color theorem. It states that anymap can be colored with four colors such that any two adjacent countries (which share a border)must have different colors. The four color theorem is very difficult to prove, and a proof was claimedin 1969 but turned out to be fallacious. It was not until 1976 that the theorem was finally provenwith the aid of a computer. We consider a simpler scenario, where we divide the plane into regionsby drawing straight lines. We want to know if we can color this map using no more than two colors(say red and blue) such that no two regions that share a boundary have the same color. Here is anexample of a two-colored map:We will prove this “two color theorem” by induction on n, the numb er of lines:Base Case: Prove that P (0) is true, w hich is the proposition that a map with n = 0 lines canbe can be colored using no more than two colors. But this is easy, since we can just color theentire plane using one color.Inductive Hypothesis: Assume P (n). That is, a map with n lines can be two-colored.Inductive Step: Prove P (n + 1). We are given a map with n + 1 lines and wish to show thatit can be two-colored. Let’s see what happens if we remove a line. With only n lines on theplane, we know we can two-color the map (by the inductive hypothesis). Let us make thefollowing observation: if we swap red ↔ blue, we still have a two-coloring. With this in mind,let us place back the line we removed, and leave colors on one side of the line unchanged. Onthe other side of the line, swap red ↔ blue. We claim that this is a valid two-coloring for themap with n + 1 lines.CS 70, Fall 2006, Lecture 3 3Why does this work? We can say with certainty that regions which do not border the lineare properly two-colored. But what about regions that do share a border with the line? Wemust be certain that any two s uch regions …
View Full Document
Unlocking...