Mcs 033 - assignment of mcs033 PDF

Preview

Summary

assignment of mcs033...

Description

MCS-033 Advanced Discrete Mathematics

1-Write generic formulae for a linear homogenous recurrence relation of order K with constant coefficient. Write all the steps for solving this type of a recurrence relation. Ans-A recursive definition of a sequence specifies  1) Initial conditions  2) Recurrence relation Example: a0=0 and a1=3 Initial conditions an = 2an-1 - an-2 Recurrence relation an = 3n Solution Linear recurrence: Each term of a sequence is a linear function of earlier terms in the sequence. For example: a0 = 1 a1 = 6 a2 = 10 an = an-1 + 2an-2 + 3an-3 a3 = a0 + 2a1 + 3a2 = 1 + 2(6) + 3(10) = 43 Linear recurrences 1. Linear homogeneous recurrences 2. Linear non-homogeneous recurrences A linear homogenous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an = c1an-1 + c2an-2 + … + ckan-k, where c1, c2, …, ck are real numbers, and ck0. an is expressed in terms of the previous k terms of the sequence, so its degree is k. This recurrence includes k initial conditions. a0 = C0 a1 = C1 … ak = Ck A linear non-homogenous recurrence relation with constant coefficients is a recurrence relation of the form an = c1an-1 + c2an-2 + … + ckan-k+ f(n), where c1, c2, …, ck are real numbers, and f(n) is a function depending only on n. The recurrence relation an = c1an-1 + c2an-2 + … + ckan-k, is called the associated homogeneous recurrence relation. This recurrence includes k initial conditions. a0 = C0 a1 = C1 … ak = Ck 2-Write whether or not each recurrence relation in the following problems is a linear homogeneous with constant coefficient.. Also

show the order of each linear homogeneous recurrence relation. Ans1-Homogeneous--- Order 1 and Degree1 2- Homogeneous---- Order 1 and Degree 0(No Degree) 3- Non-Homogeneous ----Order 2 and Degree 2 4- Non-Homogeneous---- Order 1 and Degree1 5-Homogeneous--- No order and 1 Degree

3-Solve the following recurrence relations using substitution Ans(i) an = an-1 +7 Solution:-- Here a1 = 3 is given When n = 2, A2 = a2-1 +7 A2 = a1+7 A2 = 10 (ii) an = 2n an-1 , n>0 Solution:-- Here a0 = 1 is given When n = 1, A1 = 2n a1-1 A2 =22 a0 A2 = 4*1 A2 = 4 (iii) an = 6 an-1 - 8 an-2 , n>0 Solution:-- Here a1 = 0 and a0 = 1 is given When n = 2, A2 = 6 a2-1 - 8 a2-2 A2 = 6 a1 - 8 a0 A2 = 6 *0 - 8 *1 A2 = -8 4-The population of tigers increases 4 percent per year. In 2000 the population was 15000. What was the population 30 years back i.e in year 1970? Ans-...