CC0675 Semester 2 2016 Page 2 of 3
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
November 2016 Lecturers: Jacqui Ramagge and Anne Thomas
Time Allowed: Writing - one and a half hours; Reading - 10 minutes
Exam Conditions: This is a closed-book examination — no material permitted. Writing
is not permitted at all during reading time.
Family Name: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SID: . . . . . . . . . . . . . . . . . . . . . . . . . . .
Other Names: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Seat Number: . . . . . . . . . . . . . . . . .
Please check that your examination paper is complete (3 pages) and indicate by signing below.
I have checked the examination paper and arm it is complete.
Signature: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Date: . . . . . . . . . . . . . . . . . . . . . . . . .
This examination consists of 3 pages, numbered from 1 to 3.
There are 3 questions, numbered from 1 to 3.
University-approved calculators may be used.
Marker’s use
only
Page 1 of 3

欢迎咨询51作业君