Answer to Question #307682 in Discrete Mathematics for Ankit

Question

(a) Use Euclidean algorithm to find the gcd of 105 and 231.

(b) Use mathematical induction to show that

1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1

(c) Show that the relation ∼ defined on R as a ∼ b if b−a ∈ Q, is an equivalence relation.

Also, find the equivalence class of 1.

Answer 1

(a) GCD(105,231)

Set up a division problem where a is larger than b.

a ÷ b = c with remainder R. Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.

231 ÷ 105 = 2 R 21    (231 = 2 × 105 + 21)

105 ÷ 21 = 5 R 0    (105 = 5 × 21 + 0)

When remainder R = 0, the GCF is the divisor, b, in the last equation. GCD = 21 [Answer]

$\sum_{n=-\infty}^{+\infty} f(x) \\$

(b) Use mathematical induction to show that

1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1

S₁=1.1!=1

=(1+1)!-1=2!-1=2-1=1

S_k= 1.1! + 2 · 2! + · · · + k · k! = (k + 1)! − 1

S_k+1= 1.1! + 2 · 2! + · · · + k+1 · (k+1)! = (k+1 + 1)! − 1=(k+2)!-1

Therefore,

S_k+ A_k+1 =S_k+1, where A_k+1 = k+1 · (k+1)!

(k+1)!-1 +k+1 · (k+1)! = (k+1)![1+(k+1)]−1 = (k+1)![k+2]−1=(k+2)!−1 [Answer]

(c) Show that the relation ∼ defined on R as a ∼ b if b−a ∈ Q, is an equivalence relation.

Also, find the equivalence class of 1.

Let us show that a relation '$\sim$' on $\mathbb R$ by '$a \sim b$ if $a - b$  ∈ Q is an equivalence relation, that is reflexive, symmetric, and transitive.

For each $a\in\mathbb R$, $a-a=0\in Q$ , and thus $a\sim a$ each $a\in\mathbb R$, and the relation is reflexive.

If $a\sim b$, then $a-b\in Q$. It follows that $b-a=-(a-b)\in Q$, and thus $b\sim a.$ Consequently, the relation is symmetric.

Let $a\sim b$ and $b\sim c$. Then $a-b\in Q, \ b-c\in Q$. It follows that $a-c=(a-b)+(b-c)\in Q$, and thus $a\sim c$. Therefore, the relation is transitive.

By definition, the equivalence class of an element $a$ is $[a]=\{b\in\mathbb R\ |\ b-a\in Q\}$.

Let us give the equivalence classes of 1

$[1]=\{b\in\mathbb R\ |\ b-1\in Q\}\\ =\{b\in\mathbb R\ |\ b=1+n,\ n\in Q\}\\=1+Q$ [Answer]