《Mathematics for Computer》Lecture 3 Notes for Recitation

6.042/18.] Mathematics for Computer Science February 9, 2005 Srini devadas and Eric Lehman Notes for Recitation 3 1 Induction Recall the principle of induction: Principle of Induction. Let P(n) be a predicate. If ·P(0) is true,an for all nE N, P(n) implies P(n+1), then P(n) is true for all nE N As an example let's try to find a simple expression equal to the following sum and then use induction to prove our guess correct 1·2+2·3+3:4+…+n·(mn+1) To help find an equivalent expression, we could try evaluating the sum for some small n and(with the help of a computer) some larger n sum 3×sum 1 2 6 2 24 3 60 4 120 210 100343400≈10°/31030200 10033901000

6.042/18.062J Mathematics for Computer Science February 9, 2005 Srini Devadas and Eric Lehman Notes for Recitation 3 1 Induction Recall the principle of induction: Principle of Induction. Let P(n) be a predicate. If • P(0) is true, and • for all n ∈ N, P(n) implies P(n + 1), then P(n) is true for all n ∈ N. As an example, let’s try to find a simple expression equal to the following sum and then use induction to prove our guess correct. 1 2 + 2 3 + 3 4 + · · · . . . + n · (n + 1) To help find an equivalent expression, we could try evaluating the sum for some small n and (with the help of a computer) some larger n: n 0 sum 0 3 × sum 0 1 2 6 2 8 24 3 20 60 4 40 120 5 70 210 . . . . . . . . . 10 440 1320 100 1000 343400 ≈ 106/3 334334000 ≈ 109/3 1030200 1003002000

Recitation 3 Unfortunately, the small sums are not too illuminating. However, the larger sums suggest we consider an expression similar to n/3. So in the third column weve multiplied each sum by 3 in hopes of spotting a sequence generated by an expression something like n3 From the first few terms, you might guess that these new numbers are equal to n(n+1)(n+ 2). Alternatively, you might notice that the last couple numbers are equal to n+3n2+2n, which factors to n(n+1)(n+2). So now we have a conjecture Conjecture. For all positive integers, n 1·2+23+3:4+…+m(m+1)n(mn+1)(m+2) Let's use induction to verify this conjecture. Remember that an induction proof has five parts, though the last one is often omitted 1. Say that the proof is by induction 2. Define the induction hypothesis, a predicate P defined on the natural numbers 3. Handle the base case: prove that P(O)is true. 4. Handle the inductive step: prove that P(n)implies P(n+1) for all integers n20 5. Conclude that P(n) is true for all n E n by the principle of induction We noted in Lecture that while the base case is usually n=0, it could be any non negative integer, k, in which case the conclusion would simply be that P(n) holds for all n > k Proof. We use induction. Let P(n) be the proposition that 1·2+2·3+3:4+…+n(m+1) n(n+1)(n+2) Base case n=1: P(1)is true, because the lefthand side of (? )is 1- 2=2, and the righthand deis(1·2·3)/3=2 Inductive step: We must show that P(n)implies P(n+1) for all n 2 1. So assume that P(n) is true, where n denotes a positive integer. Then we can reason as follows 1·2+2.3+…+(n+1)(n+2) [1·2 n(n+1)]+(m+1)(n+2) n(n+1)(n+2) +(m+1)(m+2) by ind. hypothesis(??) n(n+1)(n+2)+3(mn+1)(n+2) 3 +1)m+2)(m+3) This shows that P(n+1)is true, and so P(n)implies P(n+1) for all n>1 By the induction principle, P(n) is true for all n 2 1, which proves the claim

Recitation 3 2 Unfortunately, the small sums are not too illuminating. However, the larger sums suggest we consider an expression similar to n3/3. So in the third column we’ve multiplied each 3 sum by 3 in hopes of spotting a sequence generated by an expression something like n . From the first few terms, you might guess that these new numbers are equal to n(n+1)(n+ 2). Alternatively, you might notice that the last couple numbers are equal to n3 + 3n2 + 2n, which factors to n(n + 1)(n + 2). So now we have a conjecture: Conjecture. For all positive integers, n: n(n + 1)(n + 2) 1 2 + 2 3 + 3 4 + · · · . . . + n(n + 1) = 3 Let’s use induction to verify this conjecture. Remember that an induction proof has five parts, though the last one is often omitted: 1. Say that the proof is by induction. 2. Define the induction hypothesis, a predicate P defined on the natural numbers. 3. Handle the base case: prove that P(0) is true. 4. Handle the inductive step: prove that P(n) implies P(n + 1) for all integers n ≥ 0. 5. Conclude that P(n) is true for all n ∈ N by the principle of induction. We noted in Lecture that while the base case is usually n = 0, it could be any non￾negative integer, k, in which case the conclusion would simply be that P(n) holds for all n ≥ k. Proof. We use induction. Let P(n) be the proposition that: n(n + 1)(n + 2) 1 2 + 2 3 + 3 4 + · · · . . . + n(n + 1) = (1) 3 Base case n = 1: P(1) is true, because the lefthand side of (??) is 1 · 2 = 2, and the righthand side is (1 2 · · 3)/3 = 2. Inductive step: We must show that P(n) implies P(n+1) for all n ≥ 1. So assume that P(n) is true, where n denotes a positive integer. Then we can reason as follows: 1 2 + 2 3 + · · · · · + (n + 1)(n + 2) = [1 2 + 2 3 + + · · · · · n(n + 1)] + (n + 1)(n + 2) n(n + 1)(n + 2) = + (n + 1)(n + 2) by ind. hypothesis (??) 3 n(n + 1)(n + 2) + 3(n + 1)(n + 2) = 3 (n + 1)(n + 2)(n + 3) = 3 This shows that P(n + 1) is true, and so P(n) implies P(n + 1) for all n ≥ 1. By the induction principle, P(n) is true for all n ≥ 1, which proves the claim

Recitation 3 2 Problem: A geometric sum Perhaps you encountered this classic formula in school 1+r+r2+r3+.+rn Use induction to prove that it is correct for all real values r+1 Prepare a complete, careful solution. You'll be passing your proof to another group for " construc- tive criticism"! Solution Proof. We use induction. Let P(n) be the proposition that the following equation holds for allr≠1: 1+r+2+r3+..+=1-r Base case: P(O)is true, because both sides of the equation are equal to 1 P(n)is true, where n denotes an arbitrary natural number. We can reason as follows 9F Inductive step: We must show that P(n) implies P(n+1) for all n E N. So assume 1+r+r2+r3 +(1-r) - rn+2 1 The first equation follows from the assumption P(n), and the remaining steps are simpl fications. This proves that P(n+ 1) is also true. Therefore, P(n) implies P(n+ 1)for all mEN. By the principle of induction, P(n)is true for all nE N Note: You may have encountered a different proof of this formula. We'l write down a sequence of equations and then explain the reasoning S=1+r+r2+r3+ rS=r+r2+r3+..+rn+1 s-rS We define S on the first line, multiply by r to get the second equation, subtract the second equation from the first to get the third, and then solve for S. This gives the formula above This argument is great! It is a derivation of the formula rather than just a verification But, at some level, weve only hidden the use of induction, since the operations were doing on n-term sums are justified using you guessed it-induction

Recitation 3 3 2 Problem: A Geometric Sum Perhaps you encountered this classic formula in school: 3 1 + r + r 2 + r + . . . + r n = 1 − rn+1 1 − r Use induction to prove that it is correct for all real values r �= 1. Prepare a complete, careful solution. You’ll be passing your proof to another group for “construc￾tive criticism”!’ Solution. Proof. We use induction. Let P(n) be the proposition that the following equation holds for all r = 1 � : 1 − rn+1 3 1 + r + r 2 + r + . . . + r n = 1 − r Base case: P(0) is true, because both sides of the equation are equal to 1. Inductive step: We must show that P(n) implies P(n + 1) for all n ∈ N. So assume that P(n) is true, where n denotes an arbitrary natural number. We can reason as follows: 3 n+1 1 + r + r 2 + r + . . . + r n + r n+1 = 1 − rn+1 + r 1 − r 1 − rn+1 + (1 − r) · rn+1 = 1 − r 1 − rn+2 = 1 − r The first equation follows from the assumption P(n), and the remaining steps are simpli­ fications. This proves that P(n + 1) is also true. Therefore, P(n) implies P(n + 1) for all n ∈ N. By the principle of induction, P(n) is true for all n ∈ N. Note: You may have encountered a different proof of this formula. We’ll write down a sequence of equations and then explain the reasoning. 3 S = 1 + r + r 2 + r + . . . + r n 3 n+1 rS = r + r 2 + r + . . . + r S − rS = 1 − r n+1 1 − rn+1 S = 1 − r We define S on the first line, multiply by r to get the second equation, subtract the second equation from the first to get the third, and then solve for S. This gives the formula above! This argument is great! It is a derivation of the formula rather than just a verification. But, at some level, we’ve only hidden the use of induction, since the operations we’re doing on n­term sums are justified using— you guessed it— induction

Recitation 3 3 Problem: A False Proof In lecture, we proved that: 1+2+3+...+m But now were going to prove a contradictory theorem False Theorem 1. For all n >0 n(2+ 2+3+4 P induction. Let P(n)be the pi ion that2+3+4+…+n=n(n+1)/ Base case: P(O)is true, since both sides of the equation are equal to zero. (Recall that a sum with no terms is zero. Inductive step: N P(n) implies P(n+1) suppos that P(n)is true; that is, 2+3+4+..+n=n(n+1)/2. Then we can reason as follows 2+3+4+…+n+(n+1)=[2+3+4+…+n]+(n+1) n(n+1) +(n+1) (n+1)(n+2) Above, we group some terms, use the assumption P(n), and then simplify. This shows that P(n) implies P(n+1). By the principle of induction, P(n) is true for all nEN. D kactly is the error in this proof? Solution. The short answer is that we failed to prove P(0)= P(), just as in the colored horses problem in lecture. In fact, once again, the error is rooted in the misleading nature of the ". notation More precisely, in the inductive step we are required to prove that P(n)implies P(n+1) for all n >0. However, the argument given above breaks down when n =0. Let's look more closely at the first equation in the indutive step to see why 2+3+4+…+n+(n+1)=[2+3+4+…+n]+(m+1) This seems completely ous; after all, weve only grouped terms! However, the left side contains no terms when n =0. The"... is compeletely misleading in this case; 2, 3, 4, and n+l are actually not in the sum. This misimpression becomes an error when we"pull out"the(n+ 1) term on the right side, disregarding the fact that no such term actually existed on the left. Thus, for n=0, the equation weve just written down says 2+3+4+…+n+(n+1)=2+3+4+

� � � � � � Recitation 3 4 3 Problem: A False Proof In lecture, we proved that: n(n + 1) 1 + 2 + 3 + . . . + n = 2 But now we’re going to prove a contradictory theorem! False Theorem 1. For all n ≥ 0, n(n + 1) 2 + 3 + 4 + . . . + n = 2 Proof. We use induction. Let P(n) be the proposition that 2 + 3 + 4 + . . . + n = n(n + 1)/2. Base case: P(0) is true, since both sides of the equation are equal to zero. (Recall that a sum with no terms is zero.) Inductive step: Now we must show that P(n) implies P(n + 1) for all n ≥ 0. So suppose that P(n) is true; that is, 2 + 3 + 4 + . . . + n = n(n + 1)/2. Then we can reason as follows: 2 + 3 + 4 + . . . + n + (n + 1) = 2 + 3 + 4 + . . . + n + (n + 1) n(n + 1) = + (n + 1) 2 (n + 1)(n + 2) = 2 Above, we group some terms, use the assumption P(n), and then simplify. This shows that P(n) implies P(n + 1). By the principle of induction, P(n) is true for all n ∈ N. Where exactly is the error in this proof? Solution. The short answer is that we failed to prove P(0) ⇒ P(1), just as in the colored horses problem in lecture. In fact, once again, the error is rooted in the misleading nature of the “. . .” notation. More precisely, in the inductive step we are required to prove that P(n) implies P(n+1) for all n ≥ 0. However, the argument given above breaks down when n = 0. Let’s look more closely at the first equation in the indutive step to see why: 2 + 3 + 4 + . . . + n + (n + 1) = 2 + 3 + 4 + . . . + n + (n + 1) This seems completely innucuous; after all, we’ve only grouped terms! However, the left side contains no terms when n = 0. The “. . .” is compeletely misleading in this case; 2, 3, 4, and n + 1 are actually not in the sum. This misimpression becomes an error when we “pull out” the (n + 1) term on the right side, disregarding the fact that no such term actually existed on the left. Thus, for n = 0, the equation we’ve just written down says: 2 + 3 + 4 + . . . + n + (n + 1) = 2 + 3 + 4 + � . . . + n + (n + 1) � �� � �� � � �� � =0 =0 =1

Recitation 3 The assertion=0+I is false, and so we have not shown that P(O) implies P(1). There is no way to fix this problem and correctly prove that P(O)implies P(1), because actually P(O is true and P(1)is false Thus, we've only established P(O), P(1)=P(2), P(2)=P(3), and so forth. The induction argument falls apart because of the missing link P(0)+ P(1)

Recitation 3 5 The assertion 0 = 0 + 1 is false, and so we have not shown that P(0) implies P(1). There is no way to fix this problem and correctly prove that P(0) implies P(1), because actually P(0) is true and P(1) is false. Thus, we’ve only established P(0), P(1) ⇒ P(2), P(2) ⇒ P(3), and so forth. The induction argument falls apart because of the missing link P(0) �⇒ P(1)

Recitation 3 4 Problem: The volcanic island There is a village on a volcanic island with b> 1 blue-eyed people and g>0 green-eyed people. There are no mirrors and no one ever discusses eye color. Therefore, everyone knows the colors of everyone elses eyes, but not their own. Good thing, because an islander who learns that he or she has blue eyes must leap into the volcano at the end of the same day! The villagers live in happy ignorance for years. But one day an explorer arrives and loudly proclaims, I see that at least one person here has blue eyes. Assuming that all the villagers are master logicians, what happens?

Recitation 3 6 4 Problem: The Volcanic Island There is a village on a volcanic island with b ≥ 1 blue­eyed people and g ≥ 0 green­eyed people. There are no mirrors and no one ever discusses eye color. Therefore, everyone knows the colors of everyone elses’ eyes, but not their own. Good thing, because an islander who learns that he or she has blue eyes must leap into the volcano at the end of the same day! The villagers live in happy ignorance for years. But one day an explorer arrives and loudly proclaims, “I see that at least one person here has blue eyes.” Assuming that all the villagers are master logicians, what happens?

Recitation 3 What happens is that at the end of the bth day, all the blue-eyed villagers jump into the Use induction to prove that your conclusion is correct. We suggest the following hypoth esis P(n)that asserts all of the following are true on day n 1. If b>n, then all blue-eyed people survive the day. 2. Ifb=n, then all blue-eyed people jump into the volcano 3. If b n, then all blue-eyed people survive the day. 2. If b=n, then all blue-eyed people jump into the volcano 3. Ifb 1. Consider events on day 1 from the perspective of a blue-eyed vil lager. The explorer says that someone has blue eyes, and she can indeed see at least one other person with blue eyes. Therefore, the facts available to her are consistent with her having either blue or green eyes. So she survives the day. 2. Suppose b= 1. The single blue-eyed villager sees no one else with blue eyes, con cludes that he must have blue eyes, and jumps into the volcano. No one else jumps in because everyone else does see the blue-eyed villager and they have no reason at this point to think they too are blue-eyed 3. This statement is vacuously true, because the if-part(b 1)is false; the problem statement says thatb> 1 Therefore, P(1)is true Inductive step: Now suppose that P(n)is true where n 20. We must verify the three parts of P(n+1)

Recitation 3 7 What happens is that at the end of the bth day, all the blue­eyed villagers jump into the volcano. Use induction to prove that your conclusion is correct. We suggest the following hypoth￾esis P(n) that asserts all of the following are true on day n: 1. If b > n, then all blue­eyed people survive the day. 2. If b = n, then all blue­eyed people jump into the volcano. 3. If b n, then all blue­eyed people survive the day. 2. If b = n, then all blue­eyed people jump into the volcano. 3. If b 1. Consider events on day 1 from the perspective of a blue­eyed vil￾lager. The explorer says that someone has blue eyes, and she can indeed see at least one other person with blue eyes. Therefore, the facts available to her are consistent with her having either blue or green eyes. So she survives the day. 2. Suppose b = 1. The single blue­eyed villager sees no one else with blue eyes, con￾cludes that he must have blue eyes, and jumps into the volcano. No one else jumps in because everyone else does see the blue­eyed villager and they have no reason at this point to think they too are blue­eyed. 3. This statement is vacuously true, because the if­part (b < 1) is false; the problem statement says that b ≥ 1. Therefore, P(1) is true. Inductive step: Now suppose that P(n) is true where n ≥ 0. We must verify the three parts of P(n + 1)

Recitation 3 1. Suppose b>n+ 1. Then b> n so all the blue-eyed people survived the preceding day by part 1 of P(n). Furthermore, each blue-eyed villager can see at least n+1>n other blue-eyed people, so the observation that everyone survives is consistent with she herself having either blue or green eyes by P(n) as well. Thus, each blue-eyed villager survives the day. 2. Suppose b=n+ 1. Then b>n, so all the blue-eyed people survived the preceding day by part 1 of P(n). Thus, on day n+l each blue-eyed villager knows b>n, but sees only n other people with blue eyes. Thus, each blue-eyed villager realizes that she has blue eyes and jumps into the volcano 3. Suppose b n+ 1. Then either b= n(in which case all blue-eyed people jumped into the volcano on day n by part 2. of P(n))or else b< n(in which case all blue- eyed-people were already dead on day n by part 3 of P(m). In either case, all the blue-eyed people are already toast Therefore P(n)implies P(n+1)for all n20 By the principle of induction, P(n)is true for all n 20, and the theorem follows. D

Recitation 3 8 1. Suppose b > n + 1. Then b > n so all the blue­eyed people survived the preceding day by part 1. of P(n). Furthermore, each blue­eyed villager can see at least n+1 > n other blue­eyed people, so the observation that everyone survives is consistent with she herself having either blue or green eyes by P(n) as well. Thus, each blue­eyed villager survives the day. 2. Suppose b = n + 1. Then b > n, so all the blue­eyed people survived the preceding day by part 1. of P(n). Thus, on day n + 1 each blue­eyed villager knows b > n , but sees only n other people with blue eyes. Thus, each blue­eyed villager realizes that she has blue eyes and jumps into the volcano. 3. Suppose b < n + 1. Then either b = n (in which case all blue­eyed people jumped into the volcano on day n by part 2. of P(n)) or else b < n (in which case all blue￾eyed­people were already dead on day n by part 3. of P(n)). In either case, all the blue­eyed people are already toast. Therefore P(n) implies P(n + 1) for all n ≥ 0. By the principle of induction, P(n) is true for all n ≥ 0, and the theorem follows