I'm trying to find the number of ways $(a_n)$ of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes, where rotation is allowed. I want to find a recurrence relation for $(a_n)$ and an explicit formula for it.
For $n=1$, this cannot be done. For $n=2$, this can be done in two ways (three vertical dominoes or two horizontal and one vertical). Already for $n=4$ the complexity rises considerably. And I don't have nearly enough data to even guess at a general formula to prove by induction, for example.
You can try to build a recursion with more terms by considering how many options there are to tile the right part of a "shape", and hope that it doesn't get too messy:
Given $a,b\in [0,2]$ with $a \geq b $ let $f_n(a,b)$ be the number of ways to cover a $3\times n$ grid with $a$ extra squares in the right of the bottom row and $b$ extra squares in the right of the middle row. By classifying by the orientation of the domino covering the top-right square we obtain:
$f_n(0,0) = f_{n-1}(1,1) + f_{n-2}(2,2)$
$f_n(1,0) = f_{n-1}(1,1)$ ( here note the bottom right tile must be covered horizontally).
$f_n(1,1) = f_{n}(0,0) + f_{n-1}(1,0)$ ( by checking both cases the bottom right tile can be covered).
$f_n(2,0) = f_n(0,0)$ (by checking how the bottom right tile must be covered).
$f_n(2,1) = f_{n-2}(2,1) = 0$ (just check wherever the right-most vertical domino appears, the stuff to the right of it cant be covered proper in one of the rows).
$f_n(2,2) = f_n(1,1)+f_n(2,0)$ ( by checking how the middle right tile can be covered).
Hence we have three nice values: $f_n(0,0), f_n(1,1),f_n(2,2)$.
and recurrences:
$f_n(0,0) = f_{n-1}(1,1) + f_{n-2}(2,2)$
$f_n(1,1) = f_n(0,0) + f_{n-2}(1,1)$
$f_n(2,2) = f_n(1,1) + f_n(0,0)$
So it is already possible to get a nice $6\times 6$ matrix and just view this as a linear recurrence with that matrix.