The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 7: Fibonacci – Answers
Q1: (a) S1 = 1 and S2 = 2 .
(b) After a step of size 1, n� 1 steps remain which can be climbed in Sn�1 ways.
After a step of size 2, n� 2 steps remain which can be climbed in Sn�2 ways.
These are all the possibilities so
Sn = Sn�1 + Sn�2.
This is the Fibonacci recurrence. Taking into account the initial conditions we have
Sn = Fn+1.
Q2: (a) U1 = 1 and U2 = 1.
(b) Un = Fn+1.
Q3: Let Ln be any sequence of the required type with n letters. We can form sequences of n
letters according to the concatenations:
BLn�1 ABLn�2
All allowed sequences of n letters have this structure so ln = ln�1 + ln�2.
Now check initial conditions and verify.
Q4: (a) For each (n+ 1)-tiling of the board create the n-tuple (b0, b1, . . . , bn) where bi = 0 if
cell i is covered by the first cell from a domino and bi = 1 otherwise.
(b) For each arrangement of integers ai according to the rules a1a2 · · · an create the
n-tiling where cells i is covered by a monomer if and only if ai = i.
(c) Let T be a tiling of an n-board with tiles of odd length. Take each tile and break it
into a monomer followed by dimers. Remove the first square in this tiling to get an
tiling T 0 of an (n� 1)-board with monomers and dimers.
Q5: The Fibonacci sequence {Fn} (we adopt the convention that F0 = 0) has generating
function
F (x) =
1X
n=0
Fnx
n =
x
1� x� x2
.
(a) We observe that gn consists of the n
th partial sum of the Fibonacci sequence. So
G(x) =
F (x)
1� x
=
x
(1� x)(1� x� x2)
(b) Multiply each side by xn, sum over n and evaluate
(c) Simplify the expression for H(x). Equating coe�cients in the power series of gives
F0 + F1 + · · ·Fn = gn = hn = Fn+2 � 1,
as required.
Q6: (a) Fn1 is the largest Fibonacci number not exceeding p so
0 p� Fn1 p Fn1+1 � 1
The second inequality can be written as p� Fn1 Fn1+1 � Fn1 � 1.
But Fn1+1 � Fn1 = Fn1�1 so 0 p� Fn1 Fn1�1 � 1.
(b) Repeating the process, select the largest Fibonacci number p � Fn1 . According
to (a) the largest such Fibonacci number is no greater than Fn1�2. This means that
no two successive Fibonacci numbers occur. As F2 = 1, the process must always
terminate with a zero remainder, showing that all positive integers has the stated
decomposition.
(c)
1 = F2 4 = F4 + F2 7 = F5 + F3 10 = F6 + F3
2 = F3 5 = F5 8 = F6 11 = F6 + F4
3 = F4 6 = F5 + F2 9 = F6 + F2 12 = F6 + F4 + F2
Let Fn⇤ be the smallest Fibonacci number in the decomposition and if
n
⇤ even p $ A, n⇤ odd p $ a
This prescription gives for the first 12 integers the letter sequence
AaAAaAaAAaAA
After making the replacements A 7! Aa, a 7! A we get
AaAAaAaAAaAAaAaAAaAa
Note that the first 12 letters are unchanged. This is also a feature of the sequence of
the Fibonacci rabbit problem and indeed for n ! 1 the two sequences are identical.