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 < 3n/3 for every inte- >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<30 <3° 13<31→1<31/3 23<32 <32 3<33 < 4<3 Each implication follows by taking cube roots Inductive step. Now, we show that P(0),., P() imply P(n+1) for all n > 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 partProblem 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 inte￾ger 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 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