You have a supply of 1 × 2 dominoes with which to cover a 2 × n rectangle. Let d_nbe the number of different ways to cover the rectangle. For example, Figure 4.32 shows that d₃= 3.

The three ways to cover a 2 × 3 rectangle with 1 × 2 dominoes
(a) Find d₁, . . . , d₅. (Does d₀ make any sense? If so, what is it?)
(b) Set up a second order recurrence relation for dn.
(c) Using d₁ and d₂ as the initial conditions, solve the recurrence relation in part (b). Check your answer against the data in part (a).

Transcribed Image Text:

Figure 4.32