Discrete Structures ADP Islamia University Bhawalpur (IUB) 2024

Discrete Structure Past Paper (ADP IUB 2024-2028) -

Detailed Solutions

Prepared for: Alia

Format: Two parts - Part 1: Short Questions, Part 2: Long Questions (detailed step-by-step

answers)

Part 1 - Short Questions (Solved in detail)

Question

(i): Let f(x) = 2x + 1 and g(x) = x^2 +

1. Find f o g and g o f (composition of

functions).

Answer (detailed):

We must compute (f o

g)(x) = f(g(x)) and (g o

f)(x) = g(f(x)).

Step 1: Compute g(x): g(x) = x^2 +

1.

Step 2: Substitute g(x) into f: f(u) = 2u + 1, where u = g(x).

So f(g(x)) = 2*(x^2 +

1) + 1 = 2*x^2 + 2 + 1 = 2*x^2 +

3.

Therefore (f o

g)(x) = 2*x^2 +

3.

Now compute g(f(x)).

Step 1: Compute f(x): f(x) = 2x +

1.

Step 2: Substitute into g: g(v) = v^2 + 1, where v = f(x) = 2x +

1.

So g(f(x)) = (2x + 1)^2 + 1 = (2x + 1)*(2x +

1) +

1.

Expand: (2x + 1)*(2x +

1) = 4x^2 + 4x +

1. Add 1 gives 4x^2 + 4x +

2.

Therefore (g o

f)(x) = 4*x^2 + 4*x +

2.

Summary:

(f o

g)(x) = 2*x^2 +

3.

(g o

f)(x) = 4*x^2 + 4*x +

2.

Question

(ii): Suppose f is defined recursively by f(0) = 3 and f(n+1) = 2*f(n) +

3. Find f(1),

f(2), f(3), f(4). Also give the closed-form expression and explain how it is derived.

Answer (detailed):

We will compute terms one by one using the recursion, then find a closed-form solution for

general n.

Step-by-step computation:

- f(0) = 3 (given).

- f(1) = 2*f(0) + 3 = 2*3 + 3 = 6 + 3 =

9.

- f(2) = 2*f(1) + 3 = 2*9 + 3 = 18 + 3 =

21.

- f(3) = 2*f(2) + 3 = 2*21 + 3 = 42 + 3 =

45.

- f(4) = 2*f(3) + 3 = 2*45 + 3 = 90 + 3 =

93.

So the computed terms: f(0)=3, f(1)=9, f(2)=21, f(3)=45, f(4)=93.

Closed-form derivation:

The recurrence is linear non-homogeneous: f_(n+1) = 2*f_n +

3. To solve: