Math 216 Exam 3 (150 points) Name _____________________

Homework points (max of 50) ________

 

REMOVE THE LAST PAGE OF THE EXAM FOR USE AS A REFERENCE SHEET

 

1.      Let A = {2, 4, 6} and B = {4, 6, 8} and define the binary relation R on A to B as follows:

 

 

a.       Is 2 R 8? (1 point)

 

 

b.      Is 4 R 4? (1 point)

 

 

c.       Is 2 R 10? (1 point)

 

 

d.      Write R as a set of ordered pairs. (3 points)

 

 

 

 

 

 

 

 

e.       Draw the arrow diagram for R. (3 points)

 

A B

 


2.      Complete the following definitions. (6 points)

 

Let R be a binary relation on a set A.

  R is reflexive if, and only if, for all x A, __________________________________

  R is symmetric if, and only if, for all x, y A, _______________________________ _____________________________________________________________________

  R is antisymmetric if, and only if, for all x, y A, ___________________________ _____________________________________________________________________

  R is transitive if, and only if, for all x, y, z A, ______________________________ _____________________________________________________________________

  R is an equivalence relation if, and only if, R is _____________________________ _____________________________________________________________________

  R is a partial order if, and only if, R is ____________________________________ _____________________________________________________________________

 

3.      Consider the following relations on the set {1, 2, 3, 4}. For each property, circle Y if that relation has that property, N otherwise. (8 points)

 

R1 = {(1,1), (1,2), (1,3), (2,1), (2,2), (3,1), (3,3)}

R2 = {(1,1), (2,2), (3,3), (4,4)}

 

 

relation

reflexive

symmetric

antisymmetric

transitive

R1

Y or N

Y or N

Y or N

Y or N

R2

Y or N

Y or N

Y or N

Y or N

 

 

4.      Consider the following infinite relations. For each property, circle Y if that relation has that property, N otherwise. (8 points)

 

L is the less than or equal to relation on the set of real numbers R as follows:

For all x,y R, x L y xy.

 

S is the binary relation defined on the set of integers Z as follows:

For all x,y Z, x S y x - y ≤ 0.

 

 

relation

reflexive

symmetric

antisymmetric

transitive

L

Y or N

Y or N

Y or N

Y or N

S

Y or N

Y or N

Y or N

Y or N


5.      Let F be the equivalence relation mod 6 (that is, the relation of congruence modulo 5). Which of the following equivalence classes are equal? (5 points)

 

[2] [21] [-2] [5] [-12] [-4] [-13] [14] [3] [12] [23]

 

 

 

 

 

 

 

 

6.      The divides relation on the set A = {2, 3, 4, 6, 8, 12, 24 } is a partial order:

 

a.       Draw the Hasse diagram. (6 points)

 

 

 

 

 

 

 

 

 

 

 

b.      Find all greatest, least, maximal, and minimal elements. If there is none, write none. (4 points)

 

greatest:

least:

maximal:

minimal:

 

7.      Consider the partition of the set A = {a, b, c, d, e, f, g, h} given by the diagram below. Give the equivalence relation R induced by this partition as a set of ordered pairs. (4 points)

 

R = {

 

 

 

 

 

}

 

How many equivalence classes does R have? (2 points)


8.      Questions on recursively defined sequences.

 

a.       Write the first four terms of the following sequence: (4 points)

 

 

 

 

 

 

 

 

b.      Show that the sequence 2, 3, 4, 5, , 2 + n, , defined for n ≥ 0, (that is tn = 2 + n) satisfies the recurrence relation below. (5 points)

 

 

 

 

 

 

 

 

 

 

9.      Recall the definition of the Fibonacci numbers. (5 points)

 

 

Using the definition, show that

 


10.  Suppose a certain amount of money is deposited into an account paying 4% annual interest compounded quarterly. For each positive integer n, let Rn = the amount on deposit at the end of the nth quarter, assuming no additional deposits or withdrawals, and let R0 be the initial amount deposited.

 

a.       Write the recurrence relation for Rn in terms of Rn-1. (4 points)

 

 

Rn =

 

 

 

 

 

b.      If R0 = $10,000, find the amount of money on deposit at the end of two years, that is R8. (4 points)

(may be done with or without reference sheet)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c.       What is the APR (annual percentage rate) for the account? (2 points)

 

 

 

 

 

 

 

 

 

 


11.  Suppose that gasoline prices have been rising at a rate of 4% per week. If the price of a gallon of regular unleaded is currently $3.00 per gallon and the price continues to rise at the rate of 4% per week, what will the price be 10 weeks from now? (5 points)

(reference sheet should be helpful)

 

 

 

 

 

 

12.  A worker is promised a bonus if he can increase his production by 2 units a day, every day for a period of 25 days. That is, every day he must produce 2 more units than he did the day before. If on day 0 he produces 100 units, how many units must he produce on day 25 to qualify for the bonus? (5 points)

(reference sheet should be helpful)

 


13.  Solve the following recurrence relation using the 3-step method of iteration, guessing and proof using mathematical induction. (14 points)

 

 

 

 

 

 

 

 

 


Reference Sheet