School of Mathematics and Statistics
MAST30012 Discrete Mathematics 2021
Assignment 2
Due 23:59pm Monday 27 September 2021
Student Name Student Number
Tutor’s Name Practice Class Day/Time
Submit your assignment online in Canvas LMS.
Please attach this cover sheet to your assignment or use a blank sheet of
paper as the first page of your assignment with Student Name, Student
Number, Tutor’s Name, Practice Class Day/Time clearly stated. .
• Late submission will not be accepted unless accompanied by a medical certificate
(or a similar special consideration). If there are extenuating circumstances you
need to contact your lecturer, preferably prior to the submission deadline. Medical
certificates are usually required.
• Information on how to submit assignments can be found in the Canvas LMS.
• Full working must be shown in your solutions.
• Marks will be deducted for incomplete working, insufficient justification or incorrect
notation.
• Unless otherwise stated, proofs of identities etc. must use combinatorial arguments.
• There are 5 problems (on three pages) each worth 6 marks.
Q1: Choose n + 1 different integers from the set {1, 2, 3, . . . , 2n}. Are the following
statements true or false? For a true statement, give a rigorous proof of it; for a false
statement, give a counterexample to disprove it.
(a) At least two of the chosen integers have greatest common divisor 1.
(b) Among the chosen integers there must be a pair such that one is twice the
other.
(c) Among the chosen integers there must be a pair such that one divides the
other.
Q2: Consider the following variations on Sperner labelling problems.
(a) Suppose that an arbitrary number of distinct points are placed along the cir-
cumference of a circle, and each point is labelled by the symbol A or B in an
arbitrary manner.
Prove that the number of pairs of neighbouring points labelled AB or BA is
even.
(b) Consider a triangulated triangle. Let each vertex of all the triangles be labelled
A, B or C arbitrarily (including the vertices on the outside perimeter).
As in the proof of Sperner’s lemma place doors on each AB edge.
Show that the number of segments on the outside perimeter labelled AB has
the same parity as the number of triangles in the triangulation labelled ABC.
Note that the order of the labels is not relevant, so AB and BA are equivalent
labellings.
Q3: Using the generating function, (1 + x)n =
n∑
k=0
(
n
k
)
xk, show that
(a)
n∑
k=1
k
(
n
k
)
= n2n−1;
(b)
n∑
k=0
1
k + 1
(
n
k
)
=
2n+1 − 1
n + 1
;
(c)
n∑
k=1
(−1)k+1
k + 1
(
n
k
)
=
n
n + 1
.
Q4: Let Fn denote the nth Fibonacci number. Recall that Fn+1 counts the number of
pavings of an n-board using monomers and dimers. Hence give combinatorial proofs
of the following identities:
(a)
bn/2c∑
k=0
(
n− k
k
)
= Fn+1;
(b)
F 2n + F
2
n+1 = F2n+1.
Q5: Starting with the letter A, make sequences of symbols by the substitution rule
A 7→ B, B 7→ AAB.
(a) Write out a list of the five successive sequences which are resulted from appli-
cations of this rule (including the initial sequence A).
(b) Let An, Bn be, respectively, the number of letters A, B in the sequence after n
applications of the substitution rule. Let Sn denote the total number of letters
in the sequence after n applications of the substitution rule. Find recurrences
for An, Bn, and use these to show that
Sn = Sn−1 + 2Sn−2, (n ≥ 2)
with S0 = 1, S1 = 1.
(c) Introduce the generating function
S(x) =
∞∑
n=0
Snx
n
and show that
S(x) =
1
1− x− 2×2
.
(d) Use a partial fraction expansion of S(x) to find an exact expression for Sn.