MathDB

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)

Problem Statement