You have a supply of three kinds of tiles: two kinds of 1 × 2 tiles and one kind of 1 × 1 tile, as shown in Figure 4.30.

Let t_n be the number of different ways to cover a 1 × n rectangle with these tiles. For example, Figure 4.31 shows that t₃ = 5.
(a) Find t₁, . . . , t₅.

(Does t₀ make any sense? If so, what is it?)
(b) Set up a second order recurrence relation for t_n.
(c) Using t₁ and t₂ as the initial conditions, solve the recurrence relation in part (b). Check your answer against the data in part (a).

The five ways to tile a 1 × 3 rectangle

Transcribed Image Text:

Figure 4.30 Figure 4.31