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.

studentDyana
5  stars image

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.

studying on laptopAsif Waheed
5  stars image

Desklib's study resources are best & unique. Their study database is easy to access and easy to use.
100 % recommended.

library and studentsMike Taylor
5  stars image