Answer to Question #174367 in Discrete Mathematics for Lam Zhi Onn

Question

Q1. a) Let 𝑈 = {𝑥: 𝑥 ∈ 𝑍, 1 ≤ 𝑥 ≤ 12},

𝐴 = {2𝑥: 𝑥 ∈ 𝑈 𝑎𝑛𝑑 𝑥 𝑖𝑠 𝑎 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑒 𝑜𝑓 4},

𝐵 = {𝑥: 𝑥 ∈ 𝑈, 𝑥 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 2} 𝑎𝑛𝑑 𝐶 = {𝑥: 𝑥 ∈ 𝑈, 𝑥2 ≤ 16}.

i) List the elements belong to the sets A, B and C respectively. (3 marks)

ii) Find 𝐶 − (𝐴̅ ∩ 𝐵) (3 marks)

iii) Find 𝐵⊕𝐶̅. (2 marks)

b) Prove by induction that 1 + 5 + 9 + … + (4n – 3) = n(2n – 1) for all n ≥ 1. (5 marks)

c) Let 𝑥 = 866 𝑎𝑛𝑑 𝑦 = 732.

(i) Find the greatest common divisor of x and y and then express it in the form of

ax + by, where 𝑎, 𝑏 ∈ 𝑍. (5 marks)

(ii) Find the least common multiple of x and y. (2 marks)

[Total: 20 marks]

Answer 1

Solution.

Q1.

a)

i)

$𝑈 = \{𝑥: 𝑥 ∈ 𝑍, 1 ≤ 𝑥 ≤ 12\}=\{1,2,3,4,5,6,7,8,9,10,11,12\},\newline 𝐴 = \{2𝑥: 𝑥 ∈ 𝑈 \text{𝑎𝑛𝑑 𝑥 𝑖𝑠 𝑎 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑒 𝑜𝑓 } 4\}=\{8,16,24\},\newline 𝐵 = \{𝑥: 𝑥 ∈ 𝑈, 𝑥 \text{𝑑𝑖𝑣𝑖𝑑𝑒𝑠 } 2\}=\{2,4,6,8,10,12\},\newline 𝐶 = \{𝑥: 𝑥 ∈ 𝑈, 𝑥^2 ≤ 16\}=\{1,2,3,4\}.$

ii)

$\overline{A}=\{1,2,3,4,5,6,7,9,10,11,12\},\newline \overline{A}\cap B=\{2,4,6,10,12\},\newline C-(\overline{A}\cap B)=\{1,3\}.$

iii)

$\overline{C}=\{5,6,7,8,9,10,11,12\}, \newline B\oplus \overline{C}=\{2,4,5,7,9,11\}.$

b)

$1 + 5 + 9 + … + (4n – 3) = n(2n – 1) \text{for all } n ≥ 1.$

Let

$P(n):1+5+9+ . . .+(4n-3)=n(2n-1), \text{for all } n ≥ 1.\newline P(1):1=1(2\cdot 1−1), 1=1, \text{which is true.} P(1) \text{is true.}\newline \text{Assume that } P(n) \text{ is true for } n=k.\newline P(k):1+5+9+ . . .+(4k-3) = k(2k-1) \text{ is true.}\newline \text{Prove } P(k+1) \text{ is true.}\newline P(k+1):1+5+9+. . . +(4k-3)+4(k+1)-3=\newline =k(2k-1)+4(k+1)-3=2k^2−k+4k+4−3=\newline =2k^2+3k+1=2k^2+2k+k+1=(k+1)(2k+1)=\newline =(k+1)(2k+1+1-1)=(k+1)(2(k+1)-1).\newline \text{So, } P(k+1) \text{ is true, whenever } P(k) \text{ is true, hence } P(n) \text{is true.}$

c)

$𝑥 = 866 \text{ and } 𝑦 = 732.$

i)

$866 = 2 · 433,\newline 732 = 2 · 2 · 3 · 61 = 2^2 · 3 · 61,\newline$

from here the greatest common divisor of $x$ and $y$ is $2.$

GCD$(866,732)=2.$

$ax+by=-71\cdot866+84\cdot732=2.$

ii)

$866 = 2 · 433,\newline 732 = 2 · 2 · 3 · 61 = 2^2 · 3 · 61,\newline$

from here LCM$(866,732)=2\cdot433\cdot2\cdot3\cdot61=361956.$