GTU DM PAPER SOLUTION SUMMER 2025

Q.1 (a)

Prove that:

(A ∩ B) ∪ (A − B) = A

A ∪ (B − A) = A ∪ B

---

Solution:

(i) To prove: (A ∩ B) ∪ (A − B) = A

Let x ∈ (A ∩ B) ∪ (A − B).
Then either x ∈ A ∩ B or x ∈ A − B.

In both cases, x ∈ A.
Hence, (A ∩ B) ∪ (A − B) ⊆ A.

Now let x ∈ A.
Then either x ∈ B or x ∉ B.

If x ∈ B, then x ∈ A ∩ B.
If x ∉ B, then x ∈ A − B.

Hence, x ∈ (A ∩ B) ∪ (A − B).
Therefore, A ⊆ (A ∩ B) ∪ (A − B).

Thus, (A ∩ B) ∪ (A − B) = A.

---

(ii) To prove: A ∪ (B − A) = A ∪ B

Let x ∈ A ∪ (B − A).
Then x ∈ A or x ∈ B − A.

In both cases, x ∈ A ∪ B.
Hence, A ∪ (B − A) ⊆ A ∪ B.

Conversely, let x ∈ A ∪ B.
If x ∈ A, then x ∈ A ∪ (B − A).
If x ∈ B and x ∉ A, then x ∈ B − A.

Hence, A ∪ B ⊆ A ∪ (B − A).

Therefore, A ∪ (B − A) = A ∪ B.

✔ Proved

<

Q.1 (b)

Given:
Let A = {1, 2, 3, 4, 5, 6}.
Relation R is defined by

R = { (a, b) : b = a + 2 }

We check whether R is reflexive, symmetric, or transitive.

---

(i) Reflexive:

A relation R is reflexive if (a, a) ∈ R for all a ∈ A.

Here, b = a + 2.
For reflexivity, we need a = a + 2, which is not possible.

Therefore, R is not reflexive.

---

(ii) Symmetric:

A relation R is symmetric if (a, b) ∈ R ⇒ (b, a) ∈ R.

Given b = a + 2.
Then for symmetry, we must have a = b + 2, which is false.

Example:
If (1, 3) ∈ R, then (3, 1) should be in R, but 1 ≠ 3 + 2.

Hence, R is not symmetric.

---

(iii) Transitive:

A relation R is transitive if (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R.

Given:
b = a + 2 and c = b + 2.
⇒ c = a + 4.

For transitivity, we need c = a + 2, but c = a + 4.

Therefore, R is not transitive.

---

Conclusion:

The relation R is neither reflexive, nor symmetric, nor transitive.

Q.1 (c) (i)

Define the following:

---

1. Connected Graph:

A graph G is said to be a connected graph if there exists at least one path between every pair of vertices in the graph.

In other words, no vertex of the graph is isolated.

---

2. Boolean Matrix:

A Boolean matrix is a matrix in which each entry is either 0 or 1.

Boolean matrices are used to represent relations and graphs, where logical operations like AND, OR, and NOT are applied instead of ordinary arithmetic operations.

---

3. Euler Path:

An Euler path in a graph is a path that traverses each edge exactly once.

A connected graph has an Euler path if and only if it has exactly two vertices of odd degree.

Q.1 (c) (ii)

Given:

f(x) = (x + 1)/(x − 1)
g(x) = (x − 1)/(x + 1)

Find g ∘ f (x) and f ∘ g (x).

---

(i) To find g ∘ f (x):

By definition,

g ∘ f (x) = g(f(x))

Substitute f(x) into g(x):

g(f(x)) = g( (x + 1)/(x − 1) )

= [ (x + 1)/(x − 1) − 1 ] / [ (x + 1)/(x − 1) + 1 ]

Simplify numerator and denominator:

= [ (x + 1 − x + 1)/(x − 1) ] / [ (x + 1 + x − 1)/(x − 1) ]

= (2/(x − 1)) / (2x/(x − 1))

= 1/x

Therefore, g ∘ f (x) = 1/x.

---

(ii) To find f ∘ g (x):

By definition,

f ∘ g (x) = f(g(x))

Substitute g(x) into f(x):

f(g(x)) = f( (x − 1)/(x + 1) )

= [ (x − 1)/(x + 1) + 1 ] / [ (x − 1)/(x + 1) − 1 ]

Simplify numerator and denominator:

= [ (x − 1 + x + 1)/(x + 1) ] / [ (x − 1 − x − 1)/(x + 1) ]

= (2x/(x + 1)) / (−2/(x + 1))

= −x

Therefore, f ∘ g (x) = −x.

---

Final Answer:

g ∘ f (x) = 1/x
f ∘ g (x) = −x

Q.2 (a)

Question:
Find the total number of diagonals in a polygon with n sides.

---

Solution:

A polygon with n sides has n vertices.

From one vertex, diagonals can be drawn to all other vertices except itself and the two adjacent vertices.

Therefore, the number of diagonals from one vertex is:

n − 3

Since there are n vertices, total diagonals counted are:

n(n − 3)

Each diagonal is counted twice, so divide by 2.

Total number of diagonals = n(n − 3)/2

✔ Answer

Q.2 (b)

Given:
Let R be a relation defined on the set of rational numbers Q by

R = { (a/b , c/d) ∈ Q × Q : ad = bc }

Show that R is an equivalence relation.

---

(i) Reflexive:

A relation R is reflexive if (a/b , a/b) ∈ R for all a/b ∈ Q.

Here,

a·b = b·a

which is always true.

Hence, R is reflexive.

---

(ii) Symmetric:

A relation R is symmetric if (a/b , c/d) ∈ R ⇒ (c/d , a/b) ∈ R.

Given (a/b , c/d) ∈ R,
⇒ ad = bc.

Rearranging,

bc = ad

Hence, (c/d , a/b) ∈ R.

Therefore, R is symmetric.

---

(iii) Transitive:

A relation R is transitive if (a/b , c/d) ∈ R and (c/d , e/f) ∈ R ⇒ (a/b , e/f) ∈ R.

Given:

ad = bc  ...(1)
cf = de  ...(2)

Multiply equation (1) by f and equation (2) by b:

adf = bcf
bcf = bde

Hence,

adf = bde

Dividing both sides by d:

af = be

Thus, (a/b , e/f) ∈ R.

Hence, R is transitive.

---

Conclusion:

Since R is reflexive, symmetric, and transitive,
R is an equivalence relation.

Q.2 (c)

Given recurrence relation:

S_n+1 − 2S_n − 6S_n−1 = 9·3ⁿ

---

Step 1: Complementary (Homogeneous) Solution

Consider the associated homogeneous recurrence relation:

S_n+1 − 2S_n − 6S_n−1 = 0

Assume a solution of the form S_n = rⁿ.

r² − 2r − 6 = 0

Solving,

(r − 4)(r + 2) = 0

r = 4, −2

Hence, the complementary solution is:

S_n^(c) = A·4ⁿ + B·(−2)ⁿ

---

Step 2: Particular Solution

The non-homogeneous term is 9·3ⁿ.

Assume a particular solution of the form:

S_n^(p) = C·3ⁿ

Substitute into the recurrence relation:

C·3ⁿ⁺¹ − 2C·3ⁿ − 6C·3ⁿ⁻¹ = 9·3ⁿ

Divide throughout by 3ⁿ⁻¹:

9C − 6C − 6C = 27

−3C = 27

C = −9

Hence, the particular solution is:

S_n^(p) = −9·3ⁿ

---

Step 3: General Solution

The general solution is the sum of complementary and particular solutions:

S_n = A·4ⁿ + B·(−2)ⁿ − 9·3ⁿ

✔ Answer

Q.2 (c) (OR)

Given recurrence relation:

S_n+1 = 3S_n − n,    S₀ = 1

---

Step 1: Write the homogeneous part

The associated homogeneous recurrence relation is:

S_n+1 − 3S_n = 0

Assume a solution of the form S_n = rⁿ.

r − 3 = 0

r = 3

Hence, the complementary solution is:

S_n^(c) = A·3ⁿ

---

Step 2: Particular Solution

The non-homogeneous term is n, which is a polynomial of degree 1.

Assume a particular solution of the form:

S_n^(p) = an + b

Then,

S_n+1^(p) = a(n + 1) + b = an + a + b

Substitute into the recurrence relation:

an + a + b = 3(an + b) − n

Simplify:

an + a + b = 3an + 3b − n

Comparing coefficients:

a = 3a − 1
a + b = 3b

Solving:

a = 1/2
b = 1/4

Hence, the particular solution is:

S_n^(p) = (1/2)n + 1/4

---

Step 3: General Solution

The general solution is:

S_n = A·3ⁿ + (1/2)n + 1/4

---

Step 4: Use Initial Condition

Given S₀ = 1:

1 = A + 1/4

A = 3/4

---

Final Answer:

S_n = (3/4)·3ⁿ + (1/2)n + 1/4

✔ Answer

Continue with next questions:

👉 Q-3 and Q-4 Solutions – Graph Theory & Logic