Ministry of Higher Education Kingdom of Saudi Arabia CSTS SEU, KSA Discrete Mathematics (Math 150) Level III, Assignment 3 (2015) 1. State whether the following statements are true or false: [9] (a) If a mathematical statement P (n) is true for all n Z+ {0}, then P (1) will be the basis step in the principle of mathematical induction. (a) (b) In the principle of mathematical induction, the inductive step is equivalent to the conditional statement k (P (k) P (k + 1)). (b) (c) The recursive denition of the set A = {1, 6, 11, 16, 21, . . . } is 1 A; x A x + 5 A.. (c) (d) There are 24 ways by which three digits number can be formed with the digits 7, 4, 1 and 2. (d) (e) C(n, r) = C(n, n r). (e) (f) The value of P (5, 3) is 120. (f) (g) The recurrence relation an = 2an1 + 3an4 6an3 + 4 is homogeneous. (g) (h) The characteristic root of the recurrence relation an = 2an1 is real. (h) (i) The recurrence relation an = an1 + 3an4 8 is not linear. (i) Page 1 of 4 Please go on to the next page. . . Math 150 Department of Mathematics 2. Select one of the alternatives from the following questions as your answer. (a) The sums of the rst n positive odd integers are A. 2n + 1 B. n2 (n 1) C. n2 D. (n 1)(n + 1) (b) Let P (n) be a mathematical statement and let P (n) P (n + 1) for all natural numbers, then P (n) is true A. for all n > 1. B. for all n > m, m being a xed positive integer. C. for all n. D. Nothing can be said. (c) Let P (n) : 2n < n!, where n is a natural number, then P (n) is true A. for all n. B. for all n > 2. C. for all n > 3. D. None of the above. (d) Which of the following is equivalent to 9 C6 ? 9! A. 6!3! B. 9 C6 C. P (9,6) 6! D. All of the above. (e) The number of arrangements that can be made with the letters of the word MISSISSIPPI are 11! A. 4!4!2! 11! B. 4!4! 4!4!2! C. 11! 11! D. 4!2! (f) The coecient of x8 y 7 in the expansion of (7x 4y)15 is 15 A. 78 47 8 Page 2 of 4 Please go on to the next page. . . [9] Math 150 Department of Mathematics B. 15 7 78 47 C. 15 8 78 47 15 7 D. (g) Which of A. B. C. D. the following recurrence relation have degree 3? an = 3an1 + an3 13an4 + 3 an = 6an1 + an4 4an3 an = 2an2 + 5an3 3an1 + 9 B and C both. (h) The characteristic roots of the recurrence relation an = 4an1 4an2 are A. 2, -2 B. -2, -2 C. 1, 2 D. 2, 3 (i) The characteristic equation of the recurrence relation an = 3an2 + 4an3 is A. r3 3r 4 = 0 B. r3 + 3r + 4 = 0 C. r3 + 3r 4 = 0 D. r3 3r + 4 = 0 3. Prove by principle of mathematical induction, for all positive integers n, that 1 + 3 + 32 + + 3n1 = [2] 3n 1 2 4. Find the value of f (5), if f is dened recursively by f (0) = f (1) = 1 and for n = 1, 2, 3, . . . f (n f (n + 1) = . f (n 1) [2] 5. If n Cr represents the number of combinations of n items taken r at a time, what is the [2] 3 value of n Cr when n = 4? r=1 6. Find the number of subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} having 5 elements. Page 3 of 4 Please go on to the next page. . . Math 150 Department of Mathematics 7. Solve the recurrence relation an = 7an1 10an2 . [2] 8. Determine which of these are linear homogeneous recurrence relation with constant coecient. Also, nd the degree of those that are. [2] 1. an = 3an1 + 4an2 + 5an3 2. an = an2 + 5a2 n3 1/2 3. an = 2an3 + 4an4 + 6 4. an = 9an5 + 3an2 + an1 Page 4 of 4 End of Assignment