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.
Let's assume the top left square is cut off. You can fill the rest of the top row with horizontal dominoes, and the rest of the left column with vertical dominoes. Divide what remains into $2\times 2$ squares. Since $n$ is odd you will have an even number of them...
Best Answer
Let $f(n)$ represent the number of ways to tile a $2\times n$ grid. If $n$ is sufficiently large, the right hand column can be filled in one of three ways.
Therefore, if $n\ge2$, we have $f(n)=f(n-1)+2f(n-2)$. Adding in that $f(0)=f(1)=1$, we can calculate out that $f(6)=43$.