Question

are trying to tile a 1 x n walkway with 5 different types of tiles: a 6. (15 points) Suppose you tile, a blue 2 × 1-tile, a white 1 x 1 tile, and a black 1 × 1 tile red 2 × 1 tile, a white 2 x 1 a. (5pts) Set up and explain a recurrence relation for n a recurrence relation for the number of different tilings for a sidewalk of length n. Include initial conditions. b. (5 pts) What is the solution of this recurrence relation? c. (5 pts) How long must the walkway be in order have more than 2500 different tiling possibil ities?

Answer 1

Suppose you have a tiling at length n + 2 This can be build from A tiling of length n + 1 followed by a single tile (or) A tiling of length n followed by a double tile Let T_n be the number of different ways of tiling a 1 times n space Then for n greaterthanorequalto 1 and 3 double tiles and 2 1 times 1 tiles T_n + 2 = T_n + 1 2 + T_n. 3 Therefore T_n + 2 = 2 T_n + 1 + 3T_n where T_1 = 2, T_2 = 7 {(2 times 2) + 3 = 7} b) we can write above relation as [T_n + 2 T_n + 1] = [2 1 3 0][T_n + 1 T_n] characteristic equation is (2 - lambda) (- lambda) - 1 times = 0 Rightarrow lambda^2 - 2 lambda - 3 = 0 Rightarrow (lambda - 3)(lambda + 1) = 0 Rightarrow lambda = 3, - 1 Rightarrow T_n = a(3)^n + b(- 1)^n putting T_1 = 2 T_2 = 7 3a - b = 2, 9a + b = 7 Rightarrow a = 3/4 b = -1/4 Rightarrow T_n = 3^n + 1/4 + (- 1)^n/4