In how many ways $A_n$ can we cover a $2 \times n$ rectangle with $1 \times 2$ and $2 \times 2$ polyominoes?

Question

This is my answer:

(if rotations are allowed) Let An be the number of ways to completely cover a 2 times n checkerboard with 1x2 and 2x2 dominoes

There 3 conditions: The upper right corner can be covered with a vertical 1x2 domino, so there An-1 ways to completely cover the checkerboard. The upper right corner can be covered with two horizontal 1x2 domino, so there An-2 ways to completely cover the checkerboard. The upper right corner can be covered with a 2x2 domino, so there An-2 ways to completely cover the checkerboard.

Derived from the 3 conditions we have: An = A(n-1)+2A(n-2) for n>=2
with starting values A1 = 1 and A2 = 3

I want to ask if it is properly defined mathematically, especially for the conditions. Any advise will be appreciated.

Answer 1

Yes, the idea and recurrence are correct if rotations are allowed, but you should use MathJax to format. Also, only $1 \times 2$ or $2 \times 1$ polyominoes are called dominoes. You could instead use $A_0=1$ (the empty tiling) and $A_1=1$ as the initial conditions. Then $A_2=A_1+2 A_0=1+2\cdot 1=3$ follows from the recurrence. Now do you know how to solve this to find an explicit formula for $A(n)$?