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 induction6.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) applica￾tion of induction