undefined

Recursively Defined Sequence #2: Tilings Define the sequence Tn = Number of different ways that an nX2 rectangle can be tiled with 1X1 and 1/2 tiles. For example T2 = 7 (try out all the possible drawings) Give a recursive definition for Tr. Your definition must include: All the initial conditions of the sequence A recurrence relation for Tn as a function of some of the elements of the sequence that precede it The values of n for which this recurrence relation applies An explanation with drawings of how this recurrence relation was derived. Note that the explanation is the most important part of this question. The way to approach this question (and the previous one) is very much like we approached the Towers of Hanoi: we figured out a recursive algorithm to move the discs, then derived the recurrence relation for the cost, based on the algorithm. Here, you need to figure out a recursive algorithm to tile larger areas from valid tilings of smaller areas. Once you have that algorithm, then you can derive the entire recursive definition of In quite easily