Suppose you have three types of tile: red tiles, which are 1x1, bluetiles which are 1 x1, and green tiles which are 1 x 2. Let tn be the number of ways to lineup these tiles to form a 1 x n line. Such a con guration is called atiling of a 1 x n board. Determine (and justify) a recurrence relation for tn, and use yourrecurrence to compute t9.
to build a line of length n, andd a green tile to the right of a line of length n-2 or add either a red or blue tile to the rihgt of a line of length n-1 f(n) = f(n-2) + 2f(n-1) f(0) = 1 (there is 1 way to make a line of length 0: use no tiles) f(1)=2 f(2) = 5 f(3) = 12 f(4) = 29 f(6) = 70 f*6( = 169 f(7) = 409 f(8) = 985 f(9) = 2379
