PROCTOR’S STATEMENT This is to certify th a t________________________________________ wrote an examination in the course_____ Math 208______ under my personal supervision and received no outside aid from any source whatsoever. The student was verified through a picture ID prior to taking the examination. The completed examination is being sent to the Online and Distance Education Office by me. Signature of Examination Proctor Position Math 208 Correspondence Lesson 14: Exam 2 Name: .......... T IM E L IM IT : 2 hours; no books, no notes, no calculators, etc I: (2j points each) True or False (circle your answer): 1) True False: 2) True False: 3) True False: 4) True False: 5) True False: 6) True False: 7) True False: 8) True False: 9) True False: 10) True False: 11) True False: 12) True False: If |xj — j"x], then x is an integer, 100 99 i~ k 2 = yjk+i)2. k=1 k=0 If ao = 3, and for n > 1, an — 2 — an„ i, then aioo = —1 ■ The set described recursively by (a) 1 e S, and (b) if k € S, then 2k G S is the set of even positive integers. It may be possible to prove a theorem using the second form of induction when the first form of induction will not work. The well ordering property of the natural numbers is used to prove that induction is valid method of proof. The worst case scenario function for an algorithm gives approximately the maximum number of steps the algorithm will use for all problems of a given size. 2rt + 3n2 is 0 (u 2), VneZ, -Ijn. 1573 is a prime. The smallest positive integer that can be written as a linear combination of 231 and 195 is 1. If a, b, c are positive integers, and a < b, then gcd(a, c) < gcd(b, c). II: (5 points each) Multiple Choice (circle your answer): 1) The sum of the first 200 terms of the arithmetic sequence with initial term 2 and common difference 3 is (a) 599 (b) 601 (c) 604 (d) 60100 (e) 60400 2) According to the laws of exponents, ab * ac equals (a) abc (b) (a2)b+c (c) (a + a)bc (d) ab+c (e) None of the above. 3) A geometric sequence begins ao — 2, ai — 6. The value of 014 is (a) IS (b) 36 (c) 54 (d) 162 (e) There is not enough information to determine 04. 4) A set S of strings over the alphabet I — ( cqbjc} is described recursively be (1) q € S, and (2) if x G S, then bxc G S. Circle all the true statements in the list below. (a) Every string in S has exactly one a. (b) No string in S has b and c next to each other. (c) Every string in S has the same number of b’s and c’s, (d) Every string in S has odd length. (e) None of the above are true. 2 5) Circle each item in the list below that is a required property of an algorithm. (a) Data must be supplied to the algorithm. (b) The algorithm must have a worst case scenario function that is 0 (n ). (c) The algorithm must produce output. (d) The algorithm cannot require infinitely many steps. (e) The algorithm steps cannot be ambiguous. 6) The fact that for all ii (a) Distributive Law (b) Associative Law (c) Commutative Law (d) Inductive Law (e) Identity Law a, b, c, it is true that a(b + c) ab + ac is called the 7) Which one of the following is not true about the divides relation: represent integers) (a) 4|12 = 3 letters 0|0 (c ) (e) For all integers a and b, a|ab. If a|b and a|c then a|(b + c). For all integers a, a| — a. 8) If a, b, s, t are integers, and as + bt = 4, then (a) gcd(a, b) could be 1 (b) gcd(a, b) could be 2 (c) gcd(a, b) could be 3 (d) gcd(a, b) could be 4 (e) gcd(a, b) could be 5 all that are true in the list 3 III. (10 points each) Problems Do any three of the following four problems. If you do all four. I’ll count your best three. i) Use induction to prove that 1 + 2 + 3H------ hn — n {n + 1 ) 2 for every positive integer n. 2) A sequence of integers is defined recursively by the rules ho = 1, and for n > 1, hn = 2hn_i + 1. Compute the h i, h,2 , h.3 , h^hs. Guess the simple closed form formula for hn. Hint; It might help you guess the formula if you think about adding 1 to each of the terms ho through h.5 . 4 3) Write an algorithm, as a sequence of steps, that will take two positive integers, m^n, as input, and produce n m as output. 4) Compute gcd(1452,531), and write the gcd as a linear combination of 1452 and 531. 5