MAT 243 ONLINE WRITTEN HW 5 NAME (1) (4 pts) Fill in the blank in the statements below: (a) In an inductive proof verifying the condition for n 1 (or the lowest possible value) is called the (b) (c) In the induction step first we assume P(n), called the and then we show that POn 1) is true as well using the for inductive hypothesis. (d) A recurrence relation is an (2) (10 pts) Prove that for any positive integer n, 4k-3 2n n using mathematical induction (3) (8 pts) Prove that for any integer n 7, 3" n! using mathematical induction. (4) (10 pts) Use induction to prove that 6 divides 9" 3" for all integer n 0 (5) (10 pts) (a) Given the recursive definition for the set S below. Describe the elements of S. 4 ES y E S if r e S and y E S. (b) Give a recursive definition for the set of positive integers that are powers of 4. (1,4,16, 64,.....) (c) Give a recursive definition for the set of positive integers that are not divisible by 3