CS计算机代考程序代写 discrete mathematics AI The University of Melbourne — School of Mathematics and Statistics

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.