216 CHAPTER 6 COMBINATORICS
These values are precisely those of the Fibonacci numbers (see Problem l.3 .l8 on
page 10 ). Recall that the Fibonacci numbers In are defined by 10 = 0, Ii = I and
In = In-I + In- 2 for n > 1. The Fibonacci recurrence formula is the same as (9); only
the boundary values are different. But since h = I = tl and 13 = 2 = t 2 , we are guar
anteed that tn = In+ 1 for all n. So the problem is "solved," in that we have recognized
that the tiling numbers are just Fibonacci numbers. _Of course you may argue that the problem is not completely solved, as we do not
have a "simple" formula for tn (or In). In fact, Problem l.3.l8 did in fact state the
remarkable formula(10)which holds for all n 2 O.
Let's verify this formula, deferring for now the more important question of where
it came from. In other words, let 's figure out the how of it, ignoring for now the why
of it. All that we need to do is show that (10) satisfies both the Fibonacci recurrence
formula and agrees with the two boundary values 10 = 0, II = I. The last two are easy
to check. And verifying the recurrence formula is a fun algebra exercise: Define(^1) + v's
a:=
--2-'
Note that
1-v's
f3 :=-
2-'a+f3=I, af3=-I,
so both a and f3 are roots of the quadratic equation (see page 16 8)
(^2) -x- 1 =0.
In other words, both a and f3 satisfy
This means that if we define a sequence by gn := an, it will satisfy the Fibonacci
recurrence! For any n 20 , we have
gn+ 1 = a
n+ (^1) = an-la (^2) = an-I
(a+ I) = a
n + an-I =
gn + gn-I.
Likewise, if we define hn := f3n , this sequence will also satisfy the recurrence. Indeed,
if A and B are any constants, then the sequence
Un := A an +Bf3n
will satisfy the recurrence, since
Un+ 1 =Aan+^1 +BW+I =A(an +an-I) +B(W +W-I) = Un+Un-l·