1 (a)
Prove that 8

^{n}- 3^{n}is a multiple of 5 by mathematical induction, n ≥ 1
5 M

1 (b)
Show that if a relation on set A is transitive an irreflexive, then it is asymmetric.

5 M

1 (c)
Function f(x)=(4x+3)/(5x-2). Find f

^{-1}
5 M

1 (d)
What is the total number of vertices in a full binary tree with 20 leaves?

5 M

2 (a)
Let f(x)=x+2, g(x)=x-2 and h(x)=3x for all x ? R. (R is the set of real number). Find (i) f° g° h (ii)h° g° f (iii) f° f° f

8 M

2 (b)
Let R be a relation on the set of integers Z defined by a Rb if and only if a=m(mod 5). Prove that R is an equivalence relation. Find Z/R.

8 M

2 (c)
Show that A x (B ∩ C) = (A x B) ∩ (A x B)

4 M

3 (a)
Let A={1,2,3,4) and R={ (1,2), (2,3), (3,4), (2,1) }. Find the transitive closure using Warshall's algorithm.

6 M

3 (b)
Consider the lattices L1={1,2,4}, L2={1,3,9} under divisibility. Draw the lattice L1 x L2.

7 M

3 (c)
Solve the recurrence relation a

_{n}= -3(a_{n-1}+ a_{n-2}) - a_{n-3}with a_{0}=5, a_{1}= -9 and a_{2}=15
7 M

4 (a)
show that a group G is abelian if and only if (ab)

^{2}=a^{2}b^{2}for all a,b ∈ G
6 M

4 (b)
Prove that the set G={1,2,3,4,5,6} is an abellian group under multiplication modulo 7.

6 M

4 (c)
Find the generating function for the following series

(i) {0,1,2,3,4,??}

(ii) {1,2,3,4,5 . . . . . .}

(iii) {2,2,2,2,2 . . . . . . .}

(iv) {0,0,0,1,1,1,1, . . . . . . . .}

(i) {0,1,2,3,4,??}

(ii) {1,2,3,4,5 . . . . . .}

(iii) {2,2,2,2,2 . . . . . . .}

(iv) {0,0,0,1,1,1,1, . . . . . . . .}

8 M

5 (a)
Let \[H=\left[\begin{array}{cccccc}1 & 0 & 0 \\1 & 1 & 0 \\0 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1\end{array}\right]\] be parity check matrix.

Decode the following words relative to maximum likelyhood decoding function.

(i) 011001 (ii) 101011 (iii) 111010 (iv) 110110

Decode the following words relative to maximum likelyhood decoding function.

(i) 011001 (ii) 101011 (iii) 111010 (iv) 110110

8 M

5 (b)
Determine the Eulerian and Hamiltonian path, if exist, in the following graphs :-

6 M

5 (c)
Let G be the set of real numbers and let Let G be the set of real numbers and let a*b=ab/2. Showthat (G,*) is a abellian group

6 M

6 (a)

8 M

6 (b)
Use the laws of logic to determine the following expression as tautology or contradiction.

[p^ (p ⇒ q)] ⇒ q

[p^ (p ⇒ q)] ⇒ q

6 M

6 (c)
Draw the Hasse Diagram of the following:

(a) D

(a) D

_{105}(b) D_{72}
6 M

More question papers from Discrete Structures