How do I approach deriving recurrence relations?

Question

So I am stuck on the following problem.

Derive a recurrence relation for tiling a 2 x n checkerboard with 
a) a 1 x 1 square
b) a 2 x 1 "L" figure formed by chopping a 1 x 1 square off 
from a 2 x 2 square which can be rotated.

I was able to derive the fact that:

T(1) = 1 (you can only tile a checkerboard with a 2, 1 x 1 squares
T(2) = 5 (you can rotate the "L" four times plus place a square in each)
T(3) = 11 (you have 2 places where you can place an L (8), 
2 places where you can tile using 2 squares (2) and the 
case where you use all squares (1)

How do I go about creating the relation for 2 x n?

Answer 1

HINT: Look at the end of the board. There are only a few possibilities:

• two $1\times 1$ tiles stacked vertically;
• an L tile and a $1\times 1$ tile in any of $4$ orientations; and
• two interlocking L tiles in either of $2$ orientations.

If you see the first of these, you know that the $2\times(n-1)$ board to the left of them has one of $T(n-1)$ possible tilings; that accounts for $T(n-1)$ of the $T(n)$ tilings of the $2\times n$ board.

If you see the second, you know that the $2\times(n-2)$ board to the left of them has one of $T(n-2)$ possible tilings; that accounts for $4T(n-2)$ of the $T(n)$ tilings of the $2\times n$ board. The factor of $4$ is because there are $4$ possible $2\times 2$ extensions with an L and a $1\times 1$ tile, depending on the orientation of the pair.

I’ll leave the last case to you. These three cases cover every possible tiling of the $2\times n$ board, so summing their contributions gives you your recurrence for $T(n)$.