Recursively Defined Sequence #2: Tilings

Define the sequence Tn = Number of different ways that an nX2 rectangle can be tiled with 1X1 and 1X2 tiles. For example 2T2 = 7 (try out all the possible drawings)

Give a recursive definition for Tn. 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 Tn quite easily.