Problem 1 [48pts] (a) [10pts] Let P(n) be the statement that 12 n -n(n+1)/2, for every positive integer n. Answer the following (as part of a proof by (weak) mathematical induction): 1. [2pts] Define the statement P(1) 2. [2pts] Show that P(1) is True, completing the basis step. 3. [4pts] Show that if P(k) is True then P(k+1) is also True for k2l, completing the induction step [2pts] Explain why the basis step and induction step together show that P(n) is True for all n 4. (b) [15pts] Using (weak) mathematical induction, prove that n+n 1 is an odd positive integer, where n is a positive integer. Show all steps involved in the proof. (c) [15pts] Using weak mathematical induction, prove that if Ai, A2, ..., An, and Bi, B2-, B, are sets, and n is any positive integer, then Show all steps involved in the proof. (d) [8pts] Suppose that P(n) is a propositional function. For the following properties of P(n), determine for which positive integers n, P(n) must be True: 1. 2. 3. 4. [2pts] P(1) is True; and for all positive integers n, if P(n) is True then P(n+2) is True [2pts] P(1) and P(2) are True; and for all positive integers n, if P(n) and P(n+1) are True, then P(n+2) is True [2pts] P(1) is True; and for all positive integers n, if P(n) is True then P(2n) is True [2pts] P(1) is True; and for all positive integers n, if P(n) is True, then P(n+1) is True. Problem 1 [48pts] (a) [10pts] Let P(n) be the statement that 12 n -n(n+1)/2, for every positive integer n. Answer the following (as part of a proof by (weak) mathematical induction): 1. [2pts] Define the statement P(1) 2. [2pts] Show that P(1) is True, completing the basis step. 3. [4pts] Show that if P(k) is True then P(k+1) is also True for k2l, completing the induction step [2pts] Explain why the basis step and induction step together show that P(n) is True for all n 4. (b) [15pts] Using (weak) mathematical induction, prove that n+n 1 is an odd positive integer, where n is a positive integer. Show all steps involved in the proof. (c) [15pts] Using weak mathematical induction, prove that if Ai, A2, ..., An, and Bi, B2-, B, are sets, and n is any positive integer, then Show all steps involved in the proof. (d) [8pts] Suppose that P(n) is a propositional function. For the following properties of P(n), determine for which positive integers n, P(n) must be True: 1. 2. 3. 4. [2pts] P(1) is True; and for all positive integers n, if P(n) is True then P(n+2) is True [2pts] P(1) and P(2) are True; and for all positive integers n, if P(n) and P(n+1) are True, then P(n+2) is True [2pts] P(1) is True; and for all positive integers n, if P(n) is True then P(2n) is True [2pts] P(1) is True; and for all positive integers n, if P(n) is True, then P(n+1) is True