MATH 211 Final, Spring 2013

MATH 211 Spring 2013 FINAL EXAM AAA NAME: (1) TRUE FALSE QUESTIONS (1 point each): T F The characteristic equation of the recurrence relation an = an−1 − an−3 + an−4 is r4 + r3 − r − 1 = 0 T F While some relations are functions, not every function is a relation. T F there is a set A such that |P(A)| = 24. T F if A ∪ C = B ∪ C then A = B. T F For any set B, B � B = ∅. T F The number an of bit strings of length n that contain two ones in a row satisfies the following recurrence relation, for n > 1: an = an−1 + an−2 + 2n−2 T F there is no inverse of 12 modulo 55 T F The function f(n) = (n3 + n2 log n)(n2 + 2n) is not O(n!) T F Given that A ⊆ B, it follows that A − B = ∅ T F {φ} ⊂ {{φ}}, where φ is the empty set. T F The set defined recursively by 1 ∈ S and s + t ∈ S whenever s ∈ S and t ∈ S is the set of all integers T F The sequence defined by an = 2n + 5 · 3n is a solution for the recursive equation an = 5an−1 − 6an−2 for n ≥ 2. 1 2 SHORT ANSWER QUESTIONS:(2 points each) (2) The number of bit strings that have length 10 and start OR end with zeroes is: (3) The coefficient of x9y8 in the expansion of (2x − y)17 is: (4) The number of strings of four decimal digits that contain exactly one digit repeated twice (like XXYZ) is: (5) The number of subsets, of a set with 10 elements, that contain at least one element is: (6) The numeric value of the sum n � k=0 �n k � (−1)k is: 3 FREE RESPONSE QUESTIONS: (7) Show that the sum n � k=1 k2 is Θ(n3). (4 points) 4 (8) Consider the relations, on the set {1, 2, 3, 4}, R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)} R2 = {(1, 1), (1, 2), (3, 4)} (a) represent each relation both using a digraph and a ma- trix.(2 points) (b) Write the matrices of the relations R1 ∩ R2, R1 ∪ R2, R1 ◦ R2.(2 points) (c) Which of these relations is antisymmetric?(1 point) 5 (9) Show that the relation R, consisting of all pairs (x, y) where x and y are binary strings of length two or more that agree in their first two bits, is an equivalent relation on the set of all binary strings of length two or more. State explicitly the equivalence classes of this relation.(2 points) (10) Give a recursive definition for the set of positive integers not divisible by 2 nor by 3.(2 points) 6 (11) Find a function from N to Z that is a bijection. You will need to verify that your function is one to one and onto.(2 points) (12) Provide a combinatorial proof that n � k=1 k �n k � = n2n−1. (Hint: count in two ways the number of ways to select a committee and then a leader of the committee.)(2 points) 7 (13) Apply the Euclidean Algorithm to find gcd(765, 102), then use it to calculate lcm(765, 102).(2 points) (14) Prove by induction that f 2 1 + f 2 2 + · · · + f 2 n = fnfn+1 where fn is the nth Fibonacci number.(2 points) 8 (15) A communication channel can transmit five types of signals. Each of the first two signals takes one microsecond to be trans- mitted, while each of the remaining three takes two microsec- onds. (a) Write a recurrence relation for for the number of distinct messages that can be transmitted in n microseconds if a message can only include some or all of the five signals described above.(2 points) (b) Write the initial conditions needed to get the number of messages.(1 point) 9 (16) Find the general solution of the recurrence equation an = 3an−1+ 4an−2.(2 points) (17) Solve the linear system: x ≡ 3(modulo 9) and x ≡ 4(modulo 10).(2 points)