# Question-   MATH1081 assignment - Discrete Mathematics

Solution-

## MATH1081 - DISCRETE MATHEMATICS ASSIGNMENT 2020

T1 1. Consider the following sets: S = {180n + 33 | n ∈ Z} , T = {18n − 3 | n ∈ Z} , and U = {20n + 13 | n ∈ Z} . (a) Show that S is a proper subset of T. Let s ∈ S. By the definition of S, there exists a k ∈ Z such that s = 180k + 33, = 180k + 36 − 3, = 18(10k + 2) − 3, where 10k + 36 is an integer. Hence, s ∈ T and so S ⊆ T. Now, observe that 15 ∈ T since 18(1) − 3 = 15 and 1 ∈ Z. However, if 180n + 33 = 15, 180n = −18, n = − 1 10 . Since n /∈ Z, 15 ∈/ S and hence T * S. Therefore, S is a proper subset of T. (b) Show that S is a proper subset of U. Let s ∈ S. By the definition of S, there exists a k ∈ Z such that s = 180k + 33, = 180k + 20 + 13, = 20(9k + 1) + 13, where 20k + 13 is an integer. Hence, s ∈ U and so S ⊆ U. Now, observe that 13 ∈ U since 20(0) + 13 = 13 and 0 ∈ Z. However, if 180n + 33 = 13, 180n = −20, n = − 1 9 . Since n /∈ Z, 13 ∈/ S and hence U * S. Therefore, S is a proper subset of U. 1 MATH1081 - DISCRETE MATHEMATICS ASSIGNMENT 2020 T1 2 (c) Show that there is no containment relation between T and U. Recall from (a) that 15 ∈ T. However, if 20n + 13 = 15, 20n = 2, n = 1 10 . Since n /∈ Z, 15 ∈/ U and hence U * T. Similarly, recall from (b) that 13 ∈ U. However, if 18n − 3 = 13, 18n = 16, n = 8 9 . Since n /∈ Z, 13 ∈/ T and hence T * U. Therefore, there is no containment relation between T and U. 2. A relation  is defined on N by x  y if and only if x = y + 4k for some non-negative integer k. Prove that  is a partial order. For reflexivity, observe that a = a + 4(0), where 0 is a non-negative integer. Hence, a  a for all a ∈ N and thus the relation  is reflexive. For antisymmetry, suppose that a  b and b  a where a, b ∈ N. By the definition of , there exists non-negative integers k and l such that a = b + 4k and b = a + 4l. By substituting b we have a = a + 4k + 4l, 0 = 4k + 4l. Since k and l are both non-negative integers, this can only be true if k = l = 0. Hence, a = b and so the relation  is antisymmetric. For transitivity, suppose that a  b and b  c where a, b, c ∈ N. By the definition of , there exists non-negative integers k and l such that a = b + 4k and b = c + 4l. By substituting b we have a = c + 4l + 4k = c + 4(l + k), where l + k is a non-negative integer. Hence, a  c and the relation  is transitive. Therefore,  is a partial order as required. MATH1081 - DISCRETE MATHEMATICS ASSIGNMENT 2020 T1 3 3. Prove that 17 | 134n+1 + 185n+1 + 3 for all n ∈ N. We will use a proof by induction on n for the statement above. For the base case where n = 0, we have 134(0)+1 + 185(0)+1 + 3 = 131 + 181 + 3 = 34 = 17(2), which is divisible by 2. Hence, the statement is true for n = 0. For the inductive hypothesis, assume the statement is true for n = k, where k ∈ N. Thus, 134k+1 + 185k+1 + 3 = 17A for some positive integer A. Rearranging this equation gives 134k+1 = 17A − 185k+1 − 3. For the inductive step, we need to prove the statement is true for n = k + 1, such that 134(k+1)+1 + 185(k+1)+1 + 3 = 17B, 134k+5 + 185k+6 + 3 = 17B for some positive integer B. Proof. Using index laws, we have 134k+5 + 185k+6 + 3 = 134 · 134k+1 + 185 · 185k+1 + 3. Now, using our assumption in the inductive hypothesis, 134k+5 + 185k+6 + 3 = 134 (17A − 185k+1 − 3) + 185 · 185k+1 + 3. Finally, by expanding and simplifying, 134k+5 + 185k+6 + 3 = 134 · 17A − 134 · 185k+1 − 134 · 3 + 185 · 185k+1 + 3 = 134 · 17A + 185 · 185k+1 − 134 · 185k+1 − 134 · 3 + 3 = 134 · 17A + (185 − 134 ) · 185k+1 − 134 · 3 + 3 = 134 · 17A + 1861007 · 185k+1 − 85680 = 17(134A + 109471 · 185k+1 − 5040) = 17B, where B = 134A + 109471 · 185k+1 − 5040, which is a positive integer. We have shown that the statement is true for the base case n = 0, and that the statement is true for n = k + 1 if it is true for a particular n = k. Therefore, the statement is true for all n ∈ N by the principle of mathematical induction.

# Our happy customers

They are fast in responding to homework questions. they have the best technical writers. Thanks for helping me with my programming doubts. Dyana
5 I contact to disklib for homework, they help me out, despite there was some technical issue they gone through extra mile for me and provide me good quality work in first priority. 100% recommended. Asif Waheed
5 Desklib's study resources are best & unique. Their study database is easy to access and easy to use.
100 % recommended. Mike Taylor
5 