Question: The puzzle Trench consists of a board and a number of tiles. There is a long groove cut into the board, 1tall and quite long with lengths of 1" marked on it. The tiles are of two shapes, 1"×1" squares and 1"×2" right triangles. The goal of Trench is to find all possible ways of filling the groove with the tiles; a few examples are shown in Figure. Let us denote the number of ways of filling the first n inches of Trench as Tn.
(a) What are the first few Trench numbers T1, T2, T3, T4,... ?
(b) Construct a recurrence for Tn and explain why it is correct.
(c) Find a closed form for your recurrence.
