Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CC0675
There are three questions in this section, some with a number of parts. Write your answers in the space provided below each part. You must show your working and give reasons for your answers. If you need more space there are extra pages at the end of the examination paper. 1. (a) Let X, Y and Z be sets. Prove that (X \ Y ) \ (Z \ Y ) = (X \ Z) \ Y. (b) Let A, B, C and D be sets such that A ✓ C and B ✓ D, and let f : A ! B and g : C ! D be functions such that g(a) = f(a) for all a 2 A. (i) Suppose f is injective. Does g have to be injective? Either give a proof or a counterexample. (ii) Suppose g is injective. Does f have to be injective? Either give a proof or a counterexample. 2. (a) Let S(n) be the statement that n3 + 2n is divisible by 3. Prove by mathematical induction that S(n) is true for every integer n 1. (b) A deck of cards contains 52 cards divided into 4 suits : D (diamonds), H (hearts), S (spades) and C (clubs). Each suit contains 13 cards, of the following denominations : 2, 3, 4, 5, 6, 7, 8, 9, 10, J (jack), Q (queen), K (king) and A (ace). (i) How many cards must you pick to be sure that you have two cards of the same suit? Justify your answer. (ii) The poker hand two pairs is a hand of 5 cards containing 2 cards of one denom- ination, 2 cards of a second denomination, and 1 card of a third denomination. How many 5 card hands are two pairs? 3. Consider the sequence (an)n0 defined by the recurrence an+2 = 7an+1 10an with initial conditions a0 = a1 = 1. Let F (z) = 1X n=0 anz n = a0 + a1z + a2z 2 + · · · be the generating function for this sequence. (a) Compute the terms a2 and a3. (b) Write down and solve the characteristic equation of the recurrence. (c) Using part (b), or otherwise, find a closed formula for an. (d) Explain why F (z) 7zF (z) + 10z2F (z) = 1 6z CC0675 Semester 2 2016 Page 3 of 3 and deduce that F (z) = 1 6z 1 7z + 10z2 . (e) Use the method of partial fractions applied to part (d) and geometric series to recover the same closed formula that you found in part (c). (f) Consider a new sequence (bn)n0 that corresponds to a generating function G(z) with the following rational form: G(z) = 1 1 7z + 10z2 . Prove that for n 0, bn = nX k=0 6kank. End of Examination CC0675 Semester 2 2016 The University of Sydney School of Mathematics and Statistics MATH1004 Discrete Mathematics