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)
R_{1} = {(1,1), (1,2), (1,3),
(2,1), (2,2), (3,1), (3,3), (4,4)}
R_{2} = {(1,2), (2,1), (3,4), (4,3)}
relation |
reflexive |
symmetric |
antisymmetric |
transitive |
R_{1} |
Y or N |
Y or N |
Y or N |
Y or N |
R_{2} |
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, …, 2^{n} - 1, …,
defined for n ≥ 0, (that is c_{n} = 2^{n} - 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 R_{n} = the amount on deposit at the end of the n^{th} quarter,
assuming no additional deposits or withdrawals, and let R_{0} be the initial amount deposited.
a. Write the recurrence
relation for R_{n} in terms
of R_{n-1}. (5 points)
R_{n} =
b. If R_{0} = $20,000, find the amount of money on deposit at the
end of three years, that is R_{12}.
(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
_{}