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 nonnegative 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 “constructive 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 nterm 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)