Problem 1. (10 pts 3 = 30 points) Section 8.2, Exercise 4 b), c) and d) page
551. For each subproblem, nd the closed form solution for an by answering the following step by step:
1. (2 points) What is the characteristic equation of the recurrence relation?
2. (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.
3. (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.
a) List all the ordered pairs in the relation R = f(a; b) j a + b = 5g on A.
b) List all the ordered pairs in the relation R = f(a; b) j a < bg on A.
c) 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.
a) R1 = f(x; y) j x and y have the same parentsg
b) 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
