Assignment Sollution ( MCS-033 )

MCS-033
Advanced Discret Mathematics

Answer:1

(i) True, because an depends on all its previous term, therefore order is not defined and since, an is not like a polynomial, so the degree is also not defined.
(ii) False. The generating function for given R, R is 1/(1-x)
(iii) False
(iv) False, because it a tree has n verities then it has n-1 edges.
(v) False.


Answer: 2
(a) (i) The general form of the solution is
k10+(k20+k21 n) (-2)n + (k10+k31n+k32n2)(2)n ________________
(ii) k10+(k20+k21 n) (-2)n + (k30+k31n+k32n2)(2)n + (A0 + A1n)n32n+A2n2)(-2)n

(b) (i) an = 2an-1 + 10000n, n≥1
a0 = 40,000

(ii) an = 60,000 (2)n – 10000n – 20000)
= 10000 (6.2n-n-2)

(iii) Salary for fifth year a1 = 900000 (9 lakh)


Answer: 3

(a) The number of solution to the linear equation x1+x2+x3 where
1≤x1≤3, -1≤x2≤1 and x1≥3, is given by the coefficient of xn in the expansion of (x+x2+x3) (x4+1+x) (x3+x4+…+xn)
(b) We have
10an-1 + 3an-2 – 6an-1 + an = 3(-1)n +5(1/2)n, n≥0 ……….(1)

The characteristic equation is
ahn = C1(-1)n + C2(1/2)n + C3(1/5)n

For apn, Since –1& ½ are roots of characteristic equation with multiplicity one. Thus the particular solution is
apn = A0 n(-1)n + A1 n (1/2)n

From (1) ,we get
An [-18] (-1)n + A1 (9/4)(1/2)n = 3(-1)n+5(1/2)n

On comparing we have
A0 = -1/6, A1 = 20/9
apn = -1/6 n (-1)n –(20/9)n(1/2)n

The general solution is
an = an h + an p = C1 (-1)n + C2 (1/2)n + C3 (1/5)n -1n/6 (-1)n – 20n/9 (1/2)n

(c)
First note that by the bionomial theorem C (2n,n) is the coefficient of xn in (1+x)2n
However, we also have (1+x)2n = [(1+x)n]2 = [C(n,0) + C(n, 1)x + … + C(n,n)xn]2

The coefficient of xn in this expression is C(n,0) C(n,n) + C (n,1) C (n, n-1)+ C(n,2) C (n,n-2) + …. + C (n,n) C (n,0)
n
= S [C(n,k)]2
k=0


Answer:4

(a) we have
bn = bn-1+n2+n(n+1)/2

è bn-bn-1 = 3n2/2 + 1n/2

Using generating function
x x x x
Sbnzn - Sbn-1zn = 3/2Sn2zn + 1/2Snzn
n=1 n=1 n=1 n=1

G(z)-bn-ZG (Z) = 3/2 Z (1+z)/(1-z) + 1z/2(1-z)2

G(z) – b0/(1-z) + 3/2 Z (1+z)/(1-z)4 + 1z/2(1-z)3

è bn = b0 + 3/2n3 + ¼ n(n+1)

(b)
For this question we obtain a sequence like
1, 2, 3, 5, 13 ….

For this
an = an-2 + an-1, where a1 = 2, a0=1

(i) a1 = 2, a2 = 3, a3 = 6, a4 = 8
(ii) an = an-2 + an-1, a3 = 2, a0 =1

The characteristics equation is

r2 = r-1 = 0 è r1= 1+Ö5 /2, r2 = 1-Ö5 /2

an = C1[1+Ö5 /2]n + C2 [1-Ö5/2]n

To find C1 & C2, we use a0 = 1, a1=2

a0=1 è C1+C2 = 1

\a1=2 = C1 [1+Ö5 /2] + C2 [1-Ö5 /2 = 2]

è C1 = 1/Ö5, C2 = -1/Ö5

\ an = 1/Ö5 [1+Ö5 /2]n + 1/Ö5 [1+Ö5 /2]n



Answer:5

(a)
(i) {2, 2, 3, 3, 3, 3, 3, 3, 6}
(ii) v5 v4 v2 v1 v9 v8 v7 v6 v5
(iii) k3(iv) D(G) = Largest vertex degree of G = 6
d(G) = min. degree of vertex = 2

(b) (i) complement of the graph is shown below:


(ii) (a) A«a, g«C, d«H, b«B, f«D, E«C, G«e.
(b) e«A, g«B, C«D, d«C
(c) f«A, b«B, C«d, g«E, e«C

(c) (i) {V1, V3,V5,V7} & {V2, V4, V6, V8}

Complete matching: if every vertex in V1 is matched against some vertex in V2.

(ii) Not bipartite

Answer:6
(a) a b c a g c d f a d e a
(b) Not Hamiltonian

Since, S = {b, d} Î V (G) & S is a propersubset of V(G), by them we should have C (G-S) ≤ S, if G is Hamiltonian.
But S = 2 and C (G-S)= 3 which is a contradiction.
Therefore, G not Hamiltonian

(c) {v1, v2, v3, v4, v5, v1} weigh = 22 + 18 + 17 + 20 + 24 = 101
{a, b, d, c e, a} weight = 22 +15 + 17 + 17 + 24 = 95
{a, d, c, b, c, a} weight = 11 + 17 + 18 + 12+ 24 = 82




Answer:7
(a)
(i) Since D(G) = 6. Since there is triangle subgraph of G.
3≤x (a)≤6
(ii) X (G) = 4 colouring in Fig.
(iii) {(a, c, g)(b, d, f)(e, h), (i)}
(iv) No

(b) (i) Non-planar
(ii) Yes.

10an-3 + 3an-2 + 6an-1 + an = 3(-1)n + 5/2n, n≥ 0.