The Art and Craft of Problem Solving

6.4 RECURRENCE 215

insight by focusing on the "local" situation, the transition from n = 1 to n = 2, and

then, more generally, the transition from n to n + I. Here is a very simple example.

Tiling and the Fibonacci Recurrence

Example 6.4. 1 Define a domino to be a I x 2 rectangle. In how many ways can an
n x 2 rectangle be tiled by dominos?

Solution: Let tn denote the number of tilings for an n x 2 rectangle. Obviously
tl = I, and it is easy to check that t 2 = 2, since there are only the two possibilities
below.

rna

Consider f 7. Let us partition all the tilings of the 7 x 2 rectangle into two classes:

• Class V contains all tilings with a single vertical domino at the right end.

l_u,u�

m;uu,u

TUI I

6

• Class H contains all other tilings. If the right end isn't a vertical domino, then
  it has to be two horizontal dominos.

1_ u"u u� m" u'mt-----ll

5

This is definitely a partition, since each and every tiling must be in one of these classes,
and they do not share any elements. Class V contains t6 members: Take any tiling of
a 6 x 2 rectangle, append a vertical domino on the right, and you get a class V tiling
of a 7 x 2 rectangle. Likewise, there are t 5 tilings in class H. In other words, we have
shown that t 7 = t6 + t 5. This argument certainly generalizes, so we have the recurrence
formula

tn+l =tn+tn-I, n=2,3, .... (9)

Have we solved the problem? Yes and no. Formula (9), plus the boundary values
tl = I, t 2 = 2, completely determine tn for any value of n, and we have a simple al­
gorithm for computing the values: just start at the beginning and apply the recurrence
formula! The first few values are contained in the following table.