Here's my best shot at the sort of explanation you're asking for, although it's not nearly as clear as the $2 \times n$ case. The negative sign makes combinatorial proofs difficult, so let's rearrange this as:
$$f(n) + f(n-2) = 4f(n-1)$$
Then you want to show that the number of $n$-tilings, plus the number of $(n-2)$-tilings, is four times the number of $(n-1)$-tilings. (An "n-tiling" is a tiling of a $3 \times 2n$ rectangle by dominoes.)
In bijective terms, then, we want a bijection between the set of $n$-tilings and $(n-2)$-tilings and the set of $(n-1)$-tilings, where the $(n-1)$-tilings are each tagged with the number $1, 2, 3,$ or $4$.
Given an $(n-1)$-tiling, there are three "obvious" ways to obtain an $n$-tiling from it, namely by adding one of the three $1$-tilings on the right end. These generate tilings which have a vertical line passing all the way through, two units from the right end; call these "faulted" tilings, and those which don't have a vertical line in that position "faultless".
So it suffices to show that the number of faultless $n$-tilings, plus the number of $(n-2)$-tilings, is the number of $(n-1)$-tilings. It's easy to see that the number of faultless $n$-tilings is $2g(n-2)$; a faultless tilings must have a horizontal domino covering the second and third squares from the right in some row, and this assumption forces the placement of some other dominoes. So we need $2g(n-2) + f(n-2) = f(n-1)$. Shifting the indices, we need $2g(n-1) + f(n-1) = f(n)$, which you have already said is true.
It actually should not be too bad (if a little tedious) to compute case-by-case with judicious use of symmetry.
I'll use a $4 \times 4$ matrix with entries $b$ (for blue), $r$ (for red) and $\cdot$, to denote the number of tilings of the $\cdot$ spaces given the colours of the $b$ and $r$ spaces. By symmetry,
the cases where the top left square is either $b$ or $r$ and either in a horizontal or vertical domino have equal tiling counts, thus
$$ \text{answer} = 4 \pmatrix{b & r & \cdot& \cdot\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr}$$
Now the other two elements in the top row could either be in one domino (which could be in either orientation, or two vertical dominos, of which the second must be the reverse of the first.
By symmetry, these cases with vertical dominos have the same counts.
Thus
$$ \pmatrix{b & r & \cdot& \cdot\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} = \pmatrix{b & r & b& r\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} + \pmatrix{b & r & r & b\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} + 2 \pmatrix{b & r & r & b\cr \cdot & \cdot & b& r\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} $$
Next, consider the first term on the right above. The (2,1)
entry could be $b$ in a horizontal domino (in which case there must be two $(r,b)$ horizontal dominos below it), or $r$ in a horizontal domino (related by symmetry to the last term above),
or $b$ or $r$ in a vertical domino (in either case with a $(r,b)$ horizontal domino below it). Thus
$$ \pmatrix{b & r & b& r\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} =
\pmatrix{b & r & b& r\cr b & r & \cdot& \cdot\cr r &b &\cdot &\cdot\cr r & b& \cdot&\cdot\cr} + \pmatrix{b & r & r & b\cr \cdot & \cdot & b& r\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} + \pmatrix{b & r & b& r\cr b & \cdot& \cdot& \cdot\cr r &\cdot &\cdot &\cdot\cr r & b & \cdot&\cdot\cr}
+ \pmatrix{b & r & b& r\cr r & \cdot& \cdot& \cdot\cr b &\cdot &\cdot &\cdot\cr r & b & \cdot&\cdot\cr} $$
I'll leave the rest to you...
Best Answer
For convenience, let's say that Rule 1 is that there are no 2 dominoes forming a 2x2 square and Rule 2 is that there are no two dominoes forming the upper right and lower left corners of a 2x3 square.
Let us consider an arbitrary acceptable arrangement of a $2\times n$ square with $t$ horizontal dominoes. As I see it, there are four distinct possibilities:
In all, our recursion formula is $$A(n,t)=A(n-1,t)+2A(n-2,t-1)+A(n-3,t-2)$$
As for the base cases, I think that all you would need are $A(0,0)=1$ and $A(0,t)=A(1,t)=0$ for all $t>0$, but I could be missing something.