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