Math 216  Exam 3  (150 points)                             Name _____________________

Plus homework points (max of 50) ________

 

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

 

1.      Let A = {10, 15, 20} and B = {5, 10, 15} and define the binary relation R on A to B as follows:

 

 

a.       Is 20 R 5?  (2 point)

 

 

b.      Is 10 R 10?  (2 point)

 

 

c.       Is 20 R 20?  (2 point)

 

 

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

 

 

 

 

 

 

 

 

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

 

                          A                           B

 

    


2.      Complete the following definitions.  (12 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), (4,4)}

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

 

 

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)

 

G is the binary relation defined on the set of real numbers R as follows: 

For all x,yÎ R,   x G y  Û  xy > 0.

 

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

G

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 4 (that is, the relation of congruence modulo 4).  Which of the following equivalence classes are equal?  (8 points)

 

[0]  [21]  [-1]  [5]  [17]  [-4]  [-13]  [14]  [3]  [12]  [23]

 

 

 

 

 

 

 

 

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

 

a.       Draw the Hasse diagram.  (8 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.  (8 points)

 

R = {

 

 

 

 

 

                                                                                                                                                  }

 

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

8.      Questions on recursively defined sequences.

 

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

 

   

 

 

 

 

 

 

 

b.      Show that the sequence 0, 1, 3, 7, …, 2n - 1, …, defined for n ≥ 0, (that is cn = 2n - 1) satisfies the recurrence relation below. (6 points)

 

 

 

 

 

 

 

 

 

 

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

 

 

Using the definition, show that

 

10.  Suppose a certain amount of money is deposited into an account paying 8% 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.  (5 points)

 

 

Rn =

 

 

 

 

 

b.      If R0 = $20,000, find the amount of money on deposit at the end of three years, that is R12. (5 points)

(may be done with or without reference sheet)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

11.  Suppose the population of a country increases at a steady rate of 3% per year.  If the population is 50 million at a certain time, what will it be 25 years later?  (8 points)

(reference sheet should be helpful)

 

 

 

 

 

 

12.  Suppose the population of a country increases at a steady rate of 1,500,000 per year.  If the population is 50 million at a certain time, what will it be 25 years later?  (8 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.  (15 points)

 

 

 

 

 

 

 

 

 

Reference Sheet