Description
Problem 1. (10 pts 3 = 30 points) Section 8.2, Exercise 4 b), c) and d) page
-
For each subproblem, nd the closed form solution for an by answering the following step by step:
-
-
(2 points) What is the characteristic equation of the recurrence relation?
-
-
-
(2 + 2 points) What are the roots of the characteristic equation? Express an in a generic form in terms of the roots you found. For (d), you will get only one root; refer Theorem 2 in page 544 for the generic form in this case.
-
-
-
(4 points) Find the closed form solution for an using the initial conditions. Show your work.
-
Problem 2. (5 points 3 = 15 points) Let A = f1; 2; 3; 4; 5g and B = f0; 1; 2; 3; 4g.
-
List all the ordered pairs in the relation R = f(a; b) j a + b = 5g on A.
-
List all the ordered pairs in the relation R = f(a; b) j a < bg on A.
-
-
List all the ordered pairs in the relation R = f(a; b) j a < bg from A to B.
-
Problem 3. (8 points 3 = 24 points) Section 9.1, Exercise 6 a), b) and d), page 608
Problem 4. (5 points 2 = 10 points) Let A be the set of all people and (x; y) 2 A A. Is each of the following an equivalence relation? For each subproblem, explain which of the three properties of an equivalence relation
{ re exivity, symmetry, and transitivity { are satis ed and which are not, by explaining why or why not. Then, answer whether it is an equivalence relation.
-
R1 = f(x; y) j x and y have the same parentsg
-
R2 = f(x; y) j x and y have a common grandparentg
Problem 5. (10 points) We de ne on the set N1 = f1; 2; 3; g of positive integers a relation such that two positive integers x and y satisfy x y if and only if x=y = 2k for some integer k. Show that is an equivalence relation.
Problem 6. (7 points 3 = 21 points) Section 9.6, Exercise 2 b), c) and e), page 662. For each subproblem, explain which of the three properties of a partial ordering { re exivity, antisymmetry, and transitivity { are satis ed and which are not, by explaining why or why not. Then, answer whether it is a partial ordering.
9
