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)
R_{1} = {(1,1), (1,2), (1,3),
(2,1), (2,2), (3,1), (3,3)}
R_{2} = {(1,1), (2,2), (3,3),
(4,4)}
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)
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 Û x ≤ y.
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 t_{n} = 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 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}. (4 points)
R_{n} =
b. If R_{0} = $10,000, find the amount of money on deposit at the
end of two years, that is R_{8}.
(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
_{}