Section 7.6

2. We are given here three relations as matricies are being and asked to find whether the relations represent partial orders. A partial order is defined as a relation on a set that is reflexive, antisymmetric and transitive. We will map out the coordinates shown in the matricies, and analyze the relation's ordered pairs to determine its properties. If the relation is reflexive, antisymmetric and transitive, then we know we are dealing with a partial order.

a. {(1,1), (1,3), (2,1), (2,2), (3,3)} This relation is reflexive because for {1,2,3} (1,1), (2,2) & (3,3) exist. This relation is also antisymmetric, meaning that if (a,b) exists, then no (b,a) exists within the relation unless a = b. The relation is not transitive, because (2,1) and (1,3) exist, but (2,3) does not. Therefore this relation is not a partial order.

b. {(1,1), (2,2), (3,1), (3,3)} This relation is reflexive, (1,1), (2,2), & (3,3) all exist on the relation. This relation is also antisymmetric, because (3,1) exists, but (1,3) does not. Finally, this relation is transitive, where (a,b) and (b,c) exist, (a,c) also exists. We see this in the case of (3,1) and (1,1). Because the relation has these three properties, it is a partial order

c. {(1,1), (1,3), (2,2), (2,3), (3,3), (3,4), (4,1), (4,2), (4,4)} This relation is reflexive, since for {1,2,3,4} (1,1), (2,2), (3,3), & (4,4) exist. It is antisymmetric, since whenever (a,b) exists in the relation, (b,a) does not exist, unless a = b. This relation is not transitive, however, since (1,3) & (3,4) exist in the relation, but (1,4) does not. This is not a partial order.

4. To determine whether the relation on the given directed graph is a partial order, we will map out the coordinates and compare the ordered pairs of the relation for its properties. {(a,a), (a,b), (a,c), (a,d), (b,b), (c,c), (c,d), (d,b), (d,d)} This relation is reflexive, since for {1,2,3,4} (1,1), (2,2), (3,3), & (4,4) exist. It is antisymmetric, since whenever (a,b) exists in the relation, (b,a) does not exist, unless a = b. This relation is not transitive, however, since (c,d) and (d,b) exist, but (c,b) does not.

6. The ordering relation for the inverse of a partial order is reversed. So where {(b,a) | (a,b) \in R}. A partial order must be transitive, reflexive and antisymmetric. This means that if the relation is reflexive then for every element, suppose a, there will exist (a,a) in the set. A reverse ordering would not change these elements. It is antisymmetric whenever (a,b) exists in the relation, but (b,a) does not exist, unless a = b. A reversing of the ordering relation would change the order of the ordered pairs, but it would not change the property of antisymmetry. The relation is transitive if (a,b) and (b,c) exist, and subsequently (a,c) exists as well. Like antisymmetry, this property is unaffected by a reversed ordering relation on a set, but it does change the order of the pairs.

10. We are given a set S {1,2,3,4} and told to find its lexicographic order based on a "less than relation". We will do this according to the instructions given for each lexicographic order.

a. We are asked to find all pairs in S x S that are less than (2,3). We will do this by finding all (a,b) such that no a > 2, and if a = 2, then b must be b < 3. {(2,2), (2,1), (1,4), (1,3), (1,2), (1,1)} represents this relation.

b. We are asked to find all pairs in S x S that are greater than (3,1). We will do this by finding all (a,b) such that no a < 3, and if a = 3, then b must be b > 1. {(3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)} is the relation.

c. We will draw the Hasse diagram of S x S on {1,2,3,4}. The diagram of the poset with the usual "less than" relation would be a totally ordered set showing elements from 1 as the least element, to 4 as the greatest.

14. In this problem, we are asked to draw the Hasse diagram for a "greater than or equal to" relation on {0,1,2,3,4,5}. This is done by finding a partial order on the set S for a greater than relation. Since every progressing element is greater than the previous, the Hasse diagram would be a totally ordered set upside-down with the largest element being the least element.

20. This problem asks us to look at a Hasse diagram and list all the ordered pairs the the relation. This is done by showing that the relation is transitive, reflexive and antisymmetric. If this relation is reflexive then for every element, suppose a, there will exist (a,a) in the set. It is antisymmetric whenever (a,b) exists in the relation and (b,a) does not exist, unless a = b. This relation is transitive, if (c,d) and (d,b) exist, and subsequently (c,b) does not. We are shown elements {a,b,c,d,e} so we know (a,a), (b,b), (c,c), (d,d), & (e,e) must exist as ordered pairs in the set. a is the least element in the diagram, so we know that pairs (a,b), (a,c), (a,d), & (a,e) are in the set. b connects to e and d, so (b,d) & (b,e) are in the set. c connects d, so (c,d) is in the set. This gives us {(a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,d), (b,e), (c,c), (c,d), (d,d), (e,e)}

26. We are given a Hasse diagram, for which we must find certain elements or groups of elements to satisfy the conditions set forth by the sections of this problem.
a. Find the maximal elements. Since l and m rest at the top of the Hasse diagram, we can say that they are the maximal elements.
b. Find the minimal elements. Since a, b and c are elements with no lesser elements below them on the Hasse diagram, they must be the minimal elements.
c. There is no greatest element in this diagram because l is not greater than m, and m is not greater than l.
d. There is no least element here because a, b and c all exist at the bottom of the Hasse diagram. None are lesser than any of the others.
e. The upper bounds of {a,b,d} are k, l and m. a and b connect paths from b to d and from d to h. c connects up with a and b at k, through the path from g to k.
f. The least upper bound of {a,b,c} is k, because k is less than l and m.
g. There are no lower bounds for {f,g,h} since f and g share no similar lower bounds with h.
h. No greatest lower bound can exist for {f,g,h} because they share no common lower bounds in the first place.

Section 6.1

2) a. a_n = -2a_(n-1), a_0 = -1. So the the initial a is -1. If we are to find the first six terms of a sequence {a_1, a_2, a_3, a_4, a_5, a_6}. To find these terms we must use the recurrence relation to find the progressive terms. We will figure this out by plugging in values of a. a_1 = -2*a_0 or a_1 = -2*-1 = 2, a_2 = -2*2 = -4, a_3 = -2*-4 = 8, a_4 = -2*8 = -16, a_5 = -2*-16 = 32, a_6 = -2*32 = -64. So {a_1, a_2, a_3, a_4, a_5, a_6} = {2, -4, 8, -16, 32, -64}.

b. a_n = a_(n-1) - a_(n-2); a_0 = 2 & a_1 = -1. So a_2 = a_1 - a_0 or a_2 = -1 - 2 = -3. a_3 = a_2 - a_1 or a_3 = -3 -(-1) = -2. a_4 = a_3 - a_2 or a_4 = -2 - (-3) = 1. a_5 = a_4 - a_3 or a_5 = 1 -(-2) = 1. a_6 = a_5 - a_4 or a_6 = 1 - 1 = 0. So {a_1, a_2, a_3, a_4, a_5, a_6} = {-1, -3, -2, 1, 1, 0}.

c. a_n = 3(a_(n-1))^2, a_0 = 1. a_1 = 3 * a_0^2 or a_1 = 3 * 1^2 = 3. a_2 = 3 * a_1^2 or a_2 = 3 * 3^2 = 27. a_3 = 3 * a_2^2 or a_3 = 3 * 27^2 = 2187. a_4 = 3 * a_3^2 or a_4 = 3 * 2187^2 = 14348907. a_5 = 3 * a_4^2 or a_5 = 3 * 14348907^2 = 617673396283947. a_6 = 3 * a_5^2 or a_6 = 3 * 617673396283947^2 = 1144561273430837494885949696427. So {a_1, a_2, a_3, a_4, a_5, a_6} = {1, 3, 27, 2187, 617673396283947, 1144561273430837494885949696427}.

d. a_n = n*a_(n-1) + (a_(n-2))^2, a_0 = -1, a_1 = 0. a_2 = 2 * a_1 + a_0^2 or a_2 = 2 * 0 + (-1)^2 = 0 + 1 = 1. a_3 = 3 * a_2 + a_1^2 or a_3 = 3 * 1 + 0^2 = 3 + 0 = 3. a_4 = 4 * a_3 + a_2^2 or a_4 = 4 * 3 + 1^2 = 12 + 1 = 13. a_5 = 5 * a_4 + a_3^2 or a_5 = 5 * 13 + 3^2 = 65 + 9 = 74. a_6 = 6 * a_5 + a_4^2 or a_6 = 6 * 74 + 13^2 = 444 + 169 = 613. So {a_1, a_2, a_3, a_4, a_5, a_6} = {0, 1, 3, 13, 74, 613}.

e. a_n = a_(n-1) - a_(n-2) + a_(n-3), a_0 = 1, a_1 = 1, a_2 = 2. a_3 = a_2 - a_1 + a_0 or a_3 = 2 - 1 + 1 = 2. a_4 = a_3 - a_2 + a_1 or a_4 = 2 - 2 + 1 = 1. a_5 = a_4 - a_3 + a_2 or a_5 = 1 - 2 + 2 = 1. a_6 = a_5 - a_4 + a_3 or a_6 = 1 - 1 + 2 = 2. So {a_1, a_2, a_3, a_4, a_5, a_6} = {1, 1, 2, 1, 1, 2}.

4. We are asked to show that the sequence {a_n} is a solution of the recurrence relation a_n = -3a_(n-1) + 4a_(n-2) given different a_n. We will do this by using an iterative method: I will plug in values of a to find if the equation is true or not.

a. a_n = 0, so this will be true if it can apply for all n. So we plug zero into the value of a regardless of its n value. So in this case, a_n = -3a_n + 4a_n, or 0 = -3(0) + 4(0) or 0 = 0. Since this statement is always true, a_n = 0 is a solution of the recurrence relation.

b. a_n = 1, so this will be true if it can apply for all n. So we plug one into the value of a regardless of the value of n. In this case, a_n = -3a_n + 4a_n, or 1 = -3(1) + 4(1) or 1 = 1. Since this statement is always true, a_n = 1 is a solution of the recurrence relation.

c. a_n = (-4)^n, for this section of the problem we are forced to identify individual elements of a by plugging in corresponding values of n which will change the value of a_n accordingly. Suppose a_0, a_1 and a_2. In this case, a_0 = (-4)^0 = 1, a_1 = (-4)^1 = -4 and a_2 = (-4)^2 or 16. So we have {a_0, a_1, a_2} = {1, -4, 16}. When we apply these values to a_n = -3a_(n-1) + 4a_(n-2), we get a_2 = -3a_1 + 4a_0 or 16 = -3(-4) + 4(1) or 16 = 12 + 4 or 16 = 16. Since this is always true, a_n = (-4)^n is a solution to the recurrence relation.

d. a_n = 2(-4)^n + 3, like the previous section of this problem, we are forced to identify individual elements of a by plugging in corresponding values of n which will change the value of a_n according to the given sequence. We'll take a_0, a_1 and a_2. So a_0 = 2(-4)^0 + 3 = 2 + 3 = 5. a_1 = 2(-4)^1 + 3 = -8 + 3 = -5. a_2 = 2(-4)^2 + 3 = 32 + 3 = 35. When we apply these values to a_n = -3a_(n-1) + 4a_(n-2), we get a_2 = -3(a_1) + 4(a_0) or 35 = -3(-5) + 4(5) or 35 = 15 +20 or 35 = 35. Since this is always true, a_n = 2(-4)^n + 3 is a sequence representing a solution to the recurrence relation.

8. We are told to find the solution to each of the recurrence relations with the given initial conditions using iterative methods, which I have been using so far to figure out the different recurrence relation solutions. I will do the same thing here that I have been doing. I will plug in different values of a to find the solution to the recurrence relation.

a. a_n = -a_(n-1), a_0 = 5. So a_1 would be -(a_0) = -5 and a_2 would be -(a_1) = 5. We see that every a_n produces 5 or -5 depending on whether n is even or not. We can say that this relation on a could be defined as a_n = (-1)^n * 5.

b. a_n = a_(n-1) + 3, a_0 = 1. So a_1 would be a_0 + 3 = 1 + 3 = 4, and a_2 would be a_1 + 3 = 4 + 3 = 7. We see that every subsequent a_n produces a number which is greater than the previous element in the sequence by 3. Since initially a_0 = 1, we can say that a_n = 1 + 3n.

c. a_n = a_(n-1) - n, a_0 = 4. So a_1 would be a_0 - n = 4 - 1 = 3 and a_2 would be a_1 - n = 3 - 2 = 1. a_3 would be a_2 - n = 1 - 3 = -2 and a_4 would be a_3 - n = -2 - 4 = -6. So {a_1, a_2, a_3, a_4} reads {3,1,-2,-6}. We can see a relation of a becoming smaller by 1,2,3,4,etc... This pattern shows us that a_n = -n

d. a_n = 2a_(n-1) - 3, a_0 = -1. a_1 = 2(a_0) - 3, or a_1 = 2(-1) - 3 = -5. a_2 = 2(a_1) - 3 or 2(-5) - 3 = -13. a_3 = 2(a_2) - 3 or 2(-13) - 3 = -29. a_4 = 2(1_3) - 3 or 2(-29) - 3 = -61. So {a_1, a_2, a_3, a_4} is {-5, -13, -29, -61}.

10. We are given information that a person deposits $1000 in an account that yields 9% interest compounded yearly.

a. We are to set up a recurrence relation for the amount in the account at the end of n years. This means we must use the indecies of a_n to set up a relation. Since every year, a gain of 9% is recorded on the account, we can create a recursive formula a_n = a_(n-1) + a_(n-1) * .09

b. Now we are to find an explicit formula for the amount in the account at the end of n years. We can do this if we take the number of years n and figure that with the amount in account a, a_n = (1.09)^n*(1000) or a_n = (1.09)^n*(a_0).

c. We have to use one of the formulas generated above to find the amount of money the account will contain at the end of 100 years. I will test out the iterative method. So a_100 = (1.09)^100 * 1000. a_100 = 5529.04 * 1000 = $5,529,040.79 after 100 years.