Best writers. Best papers. Let professionals take care of your academic papers

Order a similar paper and get 15% discount on your first order with us
Use the following coupon "FIRST15"
ORDER NOW

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 for , and then we show that P(n + 1) is true as

/in /by

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 for , and then we show that P(n + 1) is true as well using the inductive hypothesis. (d) A recurrence relation is an (2) (10 pts) Prove that for any positive integer n, Xn k=1 (4k −3) = 2n 2 −n using mathematical induction. (3) (8 pts) Prove that for any integer n ≥ 7, 3n < n! using mathematical induction. (4) (10 pts) Use induction to prove that 6 divides 9n − 3 n for all integer n ≥ 0. (5) (10 pts) (a) Given the recursive definition for the set S below. Describe the elements of S. 4 ∈ S x − y ∈ S if x ∈ S and y ∈ 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. (6) (10 pts) Let S be the set of binary strings defined recursively as follows: Basis step: 1 ∈ S Recursive step: If x ∈ S then xx ∈ S and 0x0 ∈ S (If x and y are binary strings then xy is the concatenation of x and y. For instance, if x = 0111 and y = 101 then xy = 0111101.) (a) (3 pts) List the elements of S produced by the first 2 applications of the recursive definition. Find S0, S1 and S2. 1 2 MAT 243 ONLINE WRITTEN HW 5 (b) (7 pts) Use Structural induction to prove that every element of S has even number of 0’s in it. (7) (8 pts) Find a closed-form representation of the following recurrence relations: (a) an = 6an−1 − 9an−2 for n ≥ 2 with initial conditions a0 = 4 and a1 = 6 (b) an = 4an−1 + 5an−2 for n ≥ 2 with initial conditions a0 = 2 and a1 = 8 Show all you steps for full credit.

 
Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"