1. Weak Induction in Steps (6 points) Let P(n) be the following statement TI ion+1 The following sub-problems guide you through a proof by weak induction that P(n) holds for all n E N. (1) (1 points) What is the statement P(0)? Show that P(0) is true, which completes the base case. (2) (1 points) What is the inductive hypothesis? (3) (1 points) What do you need to prove in the inductive step? (4) (3 points) Complete the inductive step. 2. Weak Induction (15 points) (1) (5 points) Using weak induction, prove that 3"6. (2) (5 points) Prove that log(n!) S nlog(n) for all integers n2 1. Reminder 1: log(1) = 0. Reminder 2: log(ab) log(a) log(b) Reminder 3: If a b then log(a) log(b). Note: The base of the logarithms doesn't matter for any of the above. 3) (5 points)ove for all integers n 2 1 that if Ai,A|..., An and B are sets, then: Hint: Use the fact that (X n Y) u Z = (X U Z) n (Y UZ) where X, Y and Z are sets