COT 3100H Spring 2003Introduction toDiscrete StructuresFinal ExamApril 24, 2003Name : __________________1) (10 pts) Find a closed form solution for the following recurrence relation withoutusing generating functions:t(0) = 7, t(1) = 18, t(n) = 5t(n-1) – 6t(n-2), for all integers n>1.2) (10 pts) Use the method of generating functions to solve the following recurrencerelation:s(0) = 3, s(1) = 3, s(n) = 5s(n-1) + 14s(n-2), for all integers n>1.3) (10 pts) Let S be a set of five positive integers the maximum of which is at most 10.Prove that there exist two non-empty disjoint subsets of S that have the same sum ofelements. (Note: Two subsets can be disjoint even if the values of the elements in the twosets are equal. For example, two disjoint subsets of {1, 2, 3, 3, 4} are {1, 3} and {3, 4}since there are two copies of three in the set. We can think of the original set being {a, b,c, d, e} where a=1, b=2, c=3, d=3, e=4 and the two subsets as being {a,c} and {d, e}.)4) (8 pts) Let x be a positive integer greater than 1. Prove using induction on n that xn –1is divisible x – 1 for all positive integers n.5) (12 pts) Choose one of the two following questions:a) Prove )1)1((211ninifor all positive integers n.(Note: You may use either induction or another proof technique shown in class. Althoughthe induction works, a portion of it is tricky.) b) Prove 21 | (4n+1 + 52n-1) for all positive integers n, using induction.6) (8 pts) Use the laws of logic to show that the two following expressions are logicallyequivalent:a) p q b) ((p r) (p r)) (q (q r))7) (4 pts) a) Find gcd(705, 450) using Euclid's Algorithm. (6 pts) b) Find integers x and y such that 705x + 450y = gcd(705,450).8) (10 pts) For any arbitrary sets A, B and C from the same universe, prove that if andonly if A – (B – C) A – B – C, then A C = .9) (16 pts) A committee of 10 senators is to be chosen from the 100 U.S. senators. 45 ofthese senators are senior members while 60 of them are men. Of the women senators, 30of them are not senior members. Given the following restrictions, how many possiblecommittees can be picked? (Note: All four parts are independent of each other.)a) The committee is required to have at least two senior members. b) The committee must have exactly five members that are either men or senior members.c) The committee is entirely comprised of men that are not senior members and womenthat are senior members.d) The committee contains no men and contains no non-senior members.10) (10 pts) A gardener plants three maple trees, four oak trees and five birch trees in arow. He plants them in random order, each arrangement being equally likely. Find theprobability that no two birch trees are next to one another.11) (12 pts) In each of the following examples, R, S and T are all relations over the set ofintegers(Z). Find a counter-example to disprove each of the following claims:a) If RR is symmetric, then R is symmetric.b) If R RR is transitive, then R is transitive.c) If RS TS, then R T.d) R = {(x,y) | x = 2y y = 2x x=y}. R is an equivalence relation.12) (18 pts) Let f, g, and h be functions over finite sets A, B, C, and D with f:AB,g:BC, h:CD such that h(g(f(x))) is a bijection. a) Prove that h must be a surjection and f must be an injection.b) Show that it is possible for h to not be injective, f to not be surjective, and g to beneither. (Show this using one single example. Please specify the sets A, B, C, D and thefunctions f, g, and h in your example.)13) (10 pts) Find nkkk111. (Hint: rationalize the denominator before determining the sum.)14) (2 pts) In what country did the Spanish Civil War take place? ___________________15) (2 pts) In what city is the Washington monument? ____________________________16) (2 pts) What company produces the Honda Accord?
View Full Document