VTRMC 2005 Problem 3

We wish to tile a strip of $n$ $1$ -inch by $1$ -inch squares. We can use dominos which are made up of two tiles that cover two adjacent squares, or $1$ -inch square tiles which cover one square. We may cover each square with one or two tiles and a tile can be above or below a domino on a square, but no part of a domino can be placed on any part of a different domino. We do not distinguish whether a domino is above or below a tile on a given square. Let $t(n)$ denote the number of ways the strip can be tiled according to the above rules. Thus for example, $t(1)=2$ and $t(2)=8$ . Find a recurrence relation for $t(n)$ , and use it to compute $t(6)$ .