6.042/18.062] Mathematics for Computer Science February 8, 2005 Srini devadas and Eric Lehman Problem set 2 Solutions Due: Monday, February 14 at 9 PM Problem 1. Use induction to prove that n/n for alln olution. The proof is by induction on n. Let P(n) be the proposition that the equation Base case. P(2 )is true because Inductive step. Assume P(n)is true. Then we can prove P(n +1)is also true as follows n+ The first step uses the assumption P(n) and the second is simplification Thus, P(2)is true and P(n)implies P(n+1)for all n 2 2. Therefore, P(n) is true for all n 2 by the principle of induction. Problem 2. DeMorgan's Law for sets says A∩(BUC)=(A∩B)U(A∩C) Assume this and prove this extension of DeMorgan's Law to n >2sets A∩(B1UB2U..UBn)=(A∩B1)U(A∩B2)U.U(A∩Bn) Extending formulas to an arbitrary number of terms is a common (if mundane) applica- tion of induction
6.042/18.062J Mathematics for Computer Science February 8, 2005 Srini Devadas and Eric Lehman Problem Set 2 Solutions Due: Monday, February 14 at 9 PM Problem 1. Use induction to prove that � � � � � � � � 1 1 1 1 1 1 − 1 − 1 − 1 − = 2 3 4 · · · n n for all n ≥ 2. Solution. The proof is by induction on n. Let P(n) be the proposition that the equation above holds. Base case. P(2) is true because � �1 1 1 − = 2 2 Inductive step. Assume P(n) is true. Then we can prove P(n + 1) is also true as follows: � � � � � � � � � � 1 1 1 1 1 1 1 − 1 − 1 − 1 − = 1 − 2 3 · · · n n + 1 n · n + 1 1 = n + 1 The first step uses the assumption P(n) and the second is simplification. Thus, P(2) is true and P(n) implies P(n + 1) for all n ≥ 2. Therefore, P(n) is true for all n ≥ 2 by the principle of induction. Problem 2. DeMorgan’s Law for sets says: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Assume this and prove this extension of DeMorgan’s Law to n ≥ 2 sets: A ∩ (B1 ∪ B2 ∪ . . . ∪ Bn) = (A ∩ B1) ∪ (A ∩ B2) ∪ . . . ∪ (A ∩ Bn) Extending formulas to an arbitrary number of terms is a common (if mundane) application of induction
Problem set 2 Solution. We use induction. Let P(n)be the proposition that A∩(B1UB2U..UBn)=(A∩B1)U(A∩B2)U.U(A∩Bn) for all sets A and Bl,..., Bn. Base case: P(2)follows from DeMorgan's original law with B= Bl andC= B2 Inductive step: Assuming P(n), we can deduce P(n+1)as follows A∩(B1∪B2UB3U.UBn)=A∩((B1∪B2)∪B3U.U∪B =(A∩(B1UB2))∪(A∩B3)∪.U(A∩Bn) (A∩B1)U(A∩B2)U(A∩B3)∪.U(A∩Bn) In the first step, we group B1 and B2. This allows us to apply the assumption P(n) in the second step. The last step uses DeMorgan's original law. Since P(2)is true and P(n)= P(n+1) for all n 22, the principle of induction implies that P(n) is true for all> 2 Problem 3. Let Hn denote the n-th harmonic sum, which is defined by k Harmonic sums come up often. Youll see them again later in 6.042 and also in 6.046 Claim.H2m≥1+m/2 for all m≥0. (a) The next problem part will ask you to prove this claim by induction. To make this easier, three steps that you may find useful in your proof are listed below. Provide a one sentence justification for each of these steps k k=1 m+1 1 Hom k=2m+1 ≥H2m+2 Solution. The first step uses the definition of H2m+1. The second step uses the fact that the first 2m terms of the sum are equal to all 2m terms of H2m. The third step uses the fact that a sum is lower bounded by the number of terms times the smalles term
2 Problem Set 2 Solution. We use induction. Let P(n) be the proposition that A ∩ (B1 ∪ B2 ∪ . . . ∪ Bn) = (A ∩ B1) ∪ (A ∩ B2) ∪ . . . ∪ (A ∩ Bn) for all sets A and B1, . . . , Bn. Base case: P(2) follows from DeMorgan’s original law with B = B1 and C = B2. Inductive step: Assuming P(n), we can deduce P(n + 1) as follows: A ∩ (B1 ∪ B2 ∪ B3 ∪ . . . ∪ Bn) = A ∩ ((B1 ∪ B2) ∪ B3 ∪ . . . ∪ Bn) = (A ∩ (B1 ∪ B2)) ∪ (A ∩ B3) ∪ . . . ∪ (A ∩ Bn) = (A ∩ B1) ∪ (A ∩ B2)) ∪ (A ∩ B3) ∪ . . . ∪ (A ∩ Bn) In the first step, we group B1 and B2. This allows us to apply the assumption P(n) in the second step. The last step uses DeMorgan’s original law. Since P(2) is true and P(n) ⇒ P(n + 1) for all n ≥ 2, the principle of induction implies that P(n) is true for all n ≥ 2. Problem 3. Let Hn denote the nth harmonic sum, which is defined by: �n 1 Hn = k k=1 Harmonic sums come up often. You’ll see them again later in 6.042 and also in 6.046. Claim. H2m ≥ 1 + m/2 for all m ≥ 0. (a) The next problem part will ask you to prove this claim by induction. To make this easier, three steps that you may find useful in your proof are listed below. Provide a one sentence justification for each of these steps. 2 �m+1 1 H2m+1 = k k=1 2 �m+1 1 = H2m + k k=2m+1 1 ≥ H2m + 2m 2m+1 · Solution. The first step uses the definition of H2m+1 . The second step uses the fact that the first 2m terms of the sum are equal to all 2m terms of H2m . The third step uses the fact that a sum is lower bounded by the number of terms times the smallest term
Problem Set 2 (b) Prove the claim by induction. (See? We told you this was going to happen .) Solution. We prove the claim by induction. Let P(m) be the proposition that H2m 1+m/2 Base case. Note that P(O)is true, because H20=H1=1≥1+0/2 Inductive step. We must show that P(m)implies P(m +1)for all m 20. We assume that P(m)is true and reason as follows 1 H k=1 2m+1 H2m ≥H2m+2m ≥(1+m/2)+1/2 1+(m+1)/ The first step uses the definition of H2m+l. The second step uses the fact that the first 2m terms of the sum are equal to all 2m terms of H2m. The third step uses the fact that a sum is lower bounded by the number of terms times the smallest term. The fourth step uses our assumption P(m)and simplification. The last step uses only algebra This shows that P(m+ 1)is true, and so P(m) is true for all m >0 by induction (c)Show that this implies Hn 21+2 log2 n when n is a power of 2 Solution. This inequality follows from substituting n= log2 m into the claim Problem 4. Suppose we want to divide a class of n students into groups each containing either 4 or 5 students (a) Let's try to use strong induction to prove that a class with n >8 students can be divided into groups of 4 or 5 Proof. The proof is by strong induction. Let P(n) be the proposition that a class with m students can be divided into teams of 4 or 5 Base case. We prove that P(n)is true for n=8, 9, or 10 by showing how to break classes of these sizes into groups of 4 or 5 students 8=4+4 4+5 10=5+5
Problem Set 2 3 (b) Prove the claim by induction. (See? We told you this was going to happen. . .) Solution. We prove the claim by induction. Let P(m) be the proposition that H2m ≥ 1 + m/2. Base case. Note that P(0) is true, because: H20 = H1 = 1 ≥ 1 + 0/2 Inductive step. We must show that P(m) implies P(m + 1) for all m ≥ 0. We assume that P(m) is true and reason as follows: 2 �m+1 1 H2m+1 = k k=1 2 �m+1 1 = H2m + k k=2m+1 1 H2m + 2m m+1 ≥ · 2 ≥ (1 + m/2) + 1/2 = 1 + (m + 1)/2 The first step uses the definition of H2m+1 . The second step uses the fact that the first 2m terms of the sum are equal to all 2m terms of H2m . The third step uses the fact that a sum is lower bounded by the number of terms times the smallest term. The fourth step uses our assumption P(m) and simplification. The last step uses only algebra. This shows that P(m + 1) is true, and so P(m) is true for all m ≥ 0 by induction. (c) Show that this implies Hn ≥ 1 + 1 2 log2 n when n is a power of 2. Solution. This inequality follows from substituting n = log2 m into the claim. Problem 4. Suppose we want to divide a class of n students into groups each containing either 4 or 5 students. (a) Let’s try to use strong induction to prove that a class with n ≥ 8 students can be divided into groups of 4 or 5. Proof. The proof is by strong induction. Let P(n) be the proposition that a class with n students can be divided into teams of 4 or 5. Base case. We prove that P(n) is true for n = 8, 9, or 10 by showing how to break classes of these sizes into groups of 4 or 5 students: 8 = 4 + 4 9 = 4 + 5 10 = 5 + 5
Problem set 2 Inductive step. We must show that P( 8),., P(n)imply P(n+1) for all n 2 10. Thus, we assume that P( 8),., P(n) are all true and show how to divide up a class of n+1 students into groups of 4 or 5. We first form one group of 4 students. Then we can divide the remaining n-3 students into groups of 4 or 5 by the assumption P(n-3) This proves P(n+1), and so the claim holds by induction This proof contains a critical logical error. Identify the first sentence in the proof that does not follow and explain what went wrong.(Pointing out that the claim is false is not sufficient; you must find the first logical error in the proof) Solution. The first error is in the sentence Then we can divide the remaining n-3 students into groups of 4 or 5 by the assumption P(n-3) If n= 10, then P(n-3)=P(7), which is not among our assumptions P( 8),., P(n) In this case, P(n+1)=P(1l) is actually false (b)Provide a correct strong induction proof that a class with n 12 students can be divided into groups of 4 or 5 Solution. The proof is by strong induction. Let P(n)be the proposition that a class with n students can be divided into teams of 4 or 5 Base case. We prove that P(n)is true for n= 12, 13, 14, and 15 by showing how to break classes of these sizes into groups of 4 or 5 student 4+4+4 13=4+4+5 4+5+5 Inductive step. We must show that P(12),., P(n)imply P(n+ 1) for all n 2 15 Thus, we assume that P( P(n)are all true and show how to divide up a class of n+ l students. We first form one group of 4 students. Then we can divide the remaining n -3 students into groups of 4 or 5 by the assumption P(n-3) (Note that n 2 15 and so n-32 12; thus, P(n-3)is among our assumptions P(12),., P(n). This proves P(n+1), and so the claim holds by induction Problem 5 Claim. If a collection of positive integers(not necessarily distinct)has sum n>l, then the collection has product at most 3 /8 For example, the collection 2, 2, 3, 4, 4, 7 has the sum
4 Problem Set 2 Inductive step. We must show that P(8), . . . , P(n) imply P(n+1) for all n ≥ 10. Thus, we assume that P(8), . . . , P(n) are all true and show how to divide up a class of n+1 students into groups of 4 or 5. We first form one group of 4 students. Then we can divide the remaining n−3 students into groups of 4 or 5 by the assumption P(n−3). This proves P(n + 1), and so the claim holds by induction. This proof contains a critical logical error. Identify the first sentence in the proof that does not follow and explain what went wrong. (Pointing out that the claim is false is not sufficient; you must find the first logical error in the proof.) Solution. The first error is in the sentence: Then we can divide the remaining n − 3 students into groups of 4 or 5 by the assumption P(n − 3). If n = 10, then P(n−3) = P(7), which is not among our assumptions P(8), . . . , P(n). In this case, P(n + 1) = P(11) is actually false. (b) Provide a correct strong induction proof that a class with n ≥ 12 students can be divided into groups of 4 or 5. Solution. The proof is by strong induction. Let P(n) be the proposition that a class with n students can be divided into teams of 4 or 5. Base case. We prove that P(n) is true for n = 12, 13, 14, and 15 by showing how to break classes of these sizes into groups of 4 or 5 students: 12 = 4 + 4 + 4 13 = 4 + 4 + 5 14 = 4 + 5 + 5 15 = 5 + 5 + 5 Inductive step. We must show that P(12), . . . , P(n) imply P(n + 1) for all n ≥ 15. Thus, we assume that P(12), . . . , P(n) are all true and show how to divide up a class of n + 1 students. We first form one group of 4 students. Then we can divide the remaining n − 3 students into groups of 4 or 5 by the assumption P(n − 3). (Note that n ≥ 15 and so n − 3 ≥ 12; thus, P(n − 3) is among our assumptions P(12), . . . , P(n).) This proves P(n + 1), and so the claim holds by induction. Problem 5. Claim. If a collection of positive integers (not necessarily distinct) has sum n ≥ 1, then the collection has product at most 3n/3 . For example, the collection 2, 2, 3, 4, 4, 7 has the sum:
Problem Set 2 2+2+3+4+4+7 On the other hand, the product is 2·2.3·4·4·7 ≈3154.2 (a)As a preliminary step, use strong induction to prove that n 0 Solution. The proof is by strong induction. Let P(n)be the proposition that n s Base case. We show that P(O), P(1), P(2), P(3), and P(4)are true 03 4. Thus, we assume that P(0),., P(n) are all true and reason as follows 3m+1)/3=3.3(n-2)/3 ( for all n≥7/2) The first step is algebra. The second step uses our assumption P(n-2). The third step is a linear inequality that holds for all n 27/2. (This forced us to deal individ- ually with the cases P(3)and P(4), above. Therefore, P(n+ 1)is true, and so P(n) is true for all n >0 by induction (b) Prove the claim using induction or strong induction You may find it easier to use induction on the number of positive integers in the collection rather than induction on the sum n) Solution. We use induction on the size of the collection. Let P(k)be the proposition that every collection of k positive integers with sum n has product at most 3n/3 First, note that P(1)is true by the preceding problem part
Problem Set 2 5 2 + 2 + 3 + 4 + 4 + 7 = 22 On the other hand, the product is: 2 2 3 4 4 7 = 1344 · · · · · ≤ 322/3 ≈ 3154.2 (a) As a preliminary step, use strong induction to prove that n ≤ 3n/3 for every integer n ≥ 0. Solution. The proof is by strong induction. Let P(n) be the proposition that n ≤ 3n/3 . Base case. We show that P(0), P(1), P(2), P(3), and P(4) are true: 03 ≤ 30 → 0 ≤ 30/3 13 ≤ 31 → 1 ≤ 31/3 23 ≤ 32 → 2 ≤ 32/3 33 ≤ 33 → 3 ≤ 33/3 43 ≤ 34 → 4 ≤ 34/3 Each implication follows by taking cube roots. Inductive step. Now, we show that P(0), . . . , P(n) imply P(n + 1) for all n ≥ 4. Thus, we assume that P(0), . . . , P(n) are all true and reason as follows: 3(n+1)/3 = 3 3(n−2)/3 · ≥ 3 · (n − 2) ≥ n + 1 (for all n ≥ 7/2) The first step is algebra. The second step uses our assumption P(n − 2). The third step is a linear inequality that holds for all n ≥ 7/2. (This forced us to deal individually with the cases P(3) and P(4), above.) Therefore, P(n + 1) is true, and so P(n) is true for all n ≥ 0 by induction. (b) Prove the claim using induction or strong induction. (You may find it easier to use induction on the number of positive integers in the collection rather than induction on the sum n.) Solution. We use induction on the size of the collection. Let P(k) be the proposition that every collection of k positive integers with sum n has product at most 3n/3 . First, note that P(1) is true by the preceding problem part
Problem set 2 Next, we must show that P(k) implies P(k+ 1) for all k > 1. So assume that P(k) is true, and let r1,..., Ck+1 be a collection of positive integers with sum n. Then we can reason as follows: 0 by induction Problem 7. Let's consider a variation of the Unstacking game demonstrated in lecture. As before, the player is presented with a stack of n> 1 bricks. Through a sequence of moves, she must reduce this to n single-brick stacks while scoring as many points as possible. A move consists of dividing a single stack of (a+b) bricks(where a, b>0)into two stacks with heights a and b. Suppose that this move is worth a+ b points. Find the best strategy and use induction to prove that there is no better strategy Solution. Some experimentation suggests that the best strategy is to remove one block
6 Problem Set 2 Next, we must show that P(k) implies P(k + 1) for all k ≥ 1. So assume that P(k) is true, and let x1, . . . , xk+1 be a collection of positive integers with sum n. Then we can reason as follows: x1 x2 · · · xk · xk+1 ≤ 3(n−xk+1)/3 · · xk+1 ≤ 3(n−xk+1)/3 3xk+1/3 · = 3n/3 The first step uses the assumption P(k), the second uses the preceding problem part, and the last step is algebra. This shows that P(k + 1) is true, and so the claim holds by induction. Problem 6. Suppose that you take a piece of paper and draw n straight lines, no one exactly on top of another, that completely cross the paper. This divides the paper into polygonal regions. Prove by induction that you can color each region either red or blue so that two regions that share a boundary are always colored differently. (Regions that share only a boundary point may have the same color.) Solution. The proof is by induction. Let P(n) be the proposition that the regions defined by n lines can be colored red or blue so that adjacent regions are different colors. Base case: If n = 0, then there are no lines and the whole paper is a single region. Color it red. Adjacent regions are different colors trivially since there are no adjacent regions. Thus, P(0) is true. Inductive step: Assume that P(n) is true. We prove that P(n + 1) is also true. Given a configuration of n + 1 lines, remove an arbitrary line l. By the assumption P(n), the polygonal regions defined by the remaining n lines can be colored red or blue so that adjacent regions are colored differently. Now add back the line l and invert the color of every region to one side of l. Adjacent regions on the same side of the line are different colors by the induction assumption P(n). Adjacent region on opposite sides of the line are different colors because the colors on one side were inverted. Therefore, P(n) implies P(n + 1), and so P(n) is true for all n ≥ 0 by induction. Problem 7. Let’s consider a variation of the Unstacking game demonstrated in lecture. As before, the player is presented with a stack of n ≥ 1 bricks. Through a sequence of moves, she must reduce this to n singlebrick stacks while scoring as many points as possible. A move consists of dividing a single stack of (a + b) bricks (where a, b > 0) into two stacks with heights a and b. Suppose that this move is worth a + b points. Find the best strategy and use induction to prove that there is no better strategy. Solution. Some experimentation suggests that the best strategy is to remove one block
Problem Set 2 at a time. This gives a score of: n+(n-1)+…+3+2≈m(m+1)∠1 (n+2)(7-1) Now we must prove that there is no better strategy Proof. We use strong induction. Let P(n)be the proposition that unstacking n bricks is th at most(n +2)(n-1)/2 points Base case: P(1)is true because the game ends immediately when there is only 1 brick Thus, the players score is 0, which is the value of (n+2)(n-1)/2 when n= 1 Inductive step: Now assume that P(1),., P(n-1)are all true in order to prove P(n), where n> 2. Suppose the stack of n bricks is split into stacks of height c and n-1, where 0<a<n. The player's best possible score for the game is then (n-x)+x)+(x+2)(x-1)/2+(n-x+2)(n-x-1)/2 for first move to unstack e bricks to unstack n- bricks Here we are using the assumptions P(a)and P(n-a), which specify the best possible scores for unstacking c and n-a bricks. Now we must choose a to maximize this expres- sion. The derivative with respect to is 2.c-n. Thus, the expression decreases as c grows from 1 to n/2 and then increases symmetrically as grows from n/2 to n-1. Therefore, the maximum is achieved when z =1 or a=n-1. In both cases, the expression above is equal to (n+2)(n-1) o we have shown that P(1),., P(n-1)imply P(n) Therefore, P(n)is true for all n 2 l by the strong induction principle
Problem Set 2 7 at a time. This gives a score of: n(n + 1) n + (n − 1) + . . . + 3 + 2 = − 1 2 (n + 2)(n − 1) = 2 Now we must prove that there is no better strategy. Proof. We use strong induction. Let P(n) be the proposition that unstacking n bricks is worth at most (n + 2)(n − 1)/2 points. Base case: P(1) is true because the game ends immediately when there is only 1 brick. Thus, the player’s score is 0, which is the value of (n + 2)(n − 1)/2 when n = 1. Inductive step: Now assume that P(1), . . . , P(n − 1) are all true in order to prove P(n), where n ≥ 2. Suppose the stack of n bricks is split into stacks of height x and n−x, where 0 < x < n. The player’s best possible score for the game is then: ((n − x) + x) + (x + 2)(x − 1)/2 + (n − x + 2)(n − x − 1)/2 � �� � � �� � � �� � for first move to unstack x bricks to unstack n − x bricks Here we are using the assumptions P(x) and P(n − x), which specify the best possible scores for unstacking x and n−x bricks. Now we must choose x to maximize this expression. The derivative with respect to x is 2x−n. Thus, the expression decreases as x grows from 1 to n/2 and then increases symmetrically as x grows from n/2 to n − 1. Therefore, the maximum is achieved when x = 1 or x = n − 1. In both cases, the expression above is equal to: (n + 2)(n − 1) 2 So we have shown that P(1), . . . , P(n − 1) imply P(n). Therefore, P(n) is true for all n ≥ 1 by the strong induction principle