EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 3InductionInduction is an extremely powerful tool in mathematics. It is a way of proving propositions that hold for allnatural numbers:1) ∀k ∈ N, 0 + 1 + 2 + 3 + · ·· + k =k(k+1)22) ∀k ∈ N, the sum of the first k odd numbers is a perfect square.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 thestatement 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. The principle ofinduction asserts that you can prove P(k) is true ∀k ∈ N, by following these three steps: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 principle 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 inductive step says that P(0) =⇒ P(1), and P(1) =⇒P(2), and so on. The fact that this “domino effect" eventually shows that ∀n ∈ N P(n) is what the principleof induction (or the induction axiom) states. In fact, dominoes are a wonderful analogy: we have a dominofor each proposition P(k). The dominoes are lined up so that if the kthdomino is knocked over, then it in turnknocks over the k + 1st. Knocking over the kthdomino corresponds to proving P(k) is true. So the inductionstep corresponds to the fact that the kthdomino knocks over the k + 1stdomino. Now, if we knock over thefirst domino (the one numbered 0), then this sets off a chain reaction that knocks down all the dominoes.Let’s see some examples.Theorem: ∀k ∈ N,k∑i=0i =k(k + 1)2.Proof (by induction on k):• Base Case: P(0) asserts:0∑i=0i =0(0 + 1)2. This clearly holds, since the left and right hand sides bothequal 0.EECS 70, Spring 2014, Note 3 1• Inductive Hypothesis: Assume P(k) is true. That is,k∑i=0i =k(k + 1)2.• Inductive Step: We must show P(k + 1). That is,k+1∑i=0i =(k + 1)(k + 2)2:k+1∑i=0i = (k∑i=0i) + (k + 1)=k(k + 1)2+ (k + 1) (by the inductive hypothesis)= (k + 1)(k2+ 1)=(k + 1)(k + 2)2.Hence, by the principle of induction, the theorem holds. ♠Note the structure of the inductive step. You try to show P(k + 1) under the assumption that P(k) is true.The idea is that P(k + 1) by itself is a difficult proposition to prove. Many difficult problems in computerscience are solved by breaking the problem into smaller, easier ones. This is precisely what we did in theinductive step: P(k + 1) is difficult to prove, but we were able to recursively define it in terms of P(k).We will now look at another proof by induction, but first we will introduce some notation and a definitionfor divisibility. We say that integer a divides b (or b is divisible by a), written as a|b, if and only if for someinteger q, b = aq.Theorem: ∀n ∈ N, n3− n is divisible by 3.Proof (by induction 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 show that P(n + 1) is true, which asserts that 3|((n + 1)3− (n + 1)). Let usexpand 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 are usefulin computer science when showing that one algorithm is more efficient than another. Notice that for thisexample, we have chosen as our base case n = 2 rather than n = 0. This is because the statement is triviallyEECS 70, Spring 2014, Note 3 2true for n < 2: more precisely it is vacuously true for n < 2, since for any such n, the condition n > 1 isfalse.1Theorem: ∀n ∈ N, n > 1 =⇒ n! < nn.Proof (by induction over n):• Base 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), which states that (n + 1)! < (n + 1)n+1. Let us begin withthe 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. ♠In the middle of the last century, a colloquial expression in common use was "that is a horse of a differentcolor", referring to something that is quite different from normal or common expectation. The famousmathematician George Polya (who was also a great expositor of mathematics for the lay public) gave thefollowing proof to show that there is no horse of a different color!Theorem: All horses are the same color.Proof (by induction on the number of horses):• Base Case: P(1) is certainly true, since with just one horse, all horses have the same color.• Inductive Hypothesis: Assume P(n), which is the statement that n horses all have the same color.• Inductive Step: Given a set of n + 1 horses {h1,h2,. .. ,hn+1}, we can exclude the last horse in the setand apply the inductive hypothesis just to the first n horses {h1,. .. ,hn}, deducing that they all havethe same color. Similarly, we can conclude that the last n horses {h2,. .. ,hn+1} all have the samecolor. But now the “middle” horses {h2,. .. ,hn} (i.e., all but the first and the last) belong to both ofthese sets, so they have the same color as horse h1and horse hn+1. It follows, therefore, that all n + 1horses have the same color. Thus, by the principle of induction, all horses have the same color. ♠Clearly, it is not true that all horses are of the same color, so where did we go wrong in our induction proof?It is tempting to blame the induction hypothesis — which is clearly false. But the whole point of inductionis that if the base case is true (which it is in this case), and assuming the induction hypothesis for any n wecan prove the case n + 1, then the statement is true for all n. So what we are looking for is a flaw in thereasoning!1Alternatively, if you think about the underlying induction principle, it should be clear that this is perfectly valid, for the samereason that standard induction starting at n = 0 is valid (think back again to the domino analogy, where now the first domino isdomino number 2).EECS 70, Spring 2014,
View Full Document
Unlocking...