Introduce an auxiliary variable: let $b_n$ be the number of ternary sequences of length $n$ that do not contain a $2$. If a sequence of length $n$ contains a $2$, you can append a $0$ or a $2$; if it does not contain a $2$, you can append a $0$, a $1$, or a $2$. In particular, you can always append a $0$ or a $2$, and if it does not contain a $2$, you can also append a $1$. Thus,
$$a_{n+1}=2a_n+b_n\;.$$
Clearly $b_{n+1}=2b_n$, and in fact it’s not hard to see that $b_n=2^n$: you’re just counting binary strings of length $n$. Thus, $$a_{n+1}=2a_n+2^n\;.$$
I’ll leave the solution to you for now.
There are eight ways in which a $4\times n$ tiling can begin, shown and named in the picture below. We'll count the number with each kind of beginning configuration and add the results up to get $f(n)$.
Types A through E are easy. Any $4\times (n-1)$ tiling can extend A to give a $4\times n$ tiling, and there are no other ways to get a "type A" $4\times n$ tiling. So there are $f(n-1)$ "type A" $4\times n$ tilings. Similarly, there are $f(n-2)$ type B $4\times n$ tilings, and $f(n-2)$ as well of each of the types C, D, and E. That's $f(n-1)+4f(n-2)$ so far.
Tilings with starting configurations F, G, and H are a little harder to count. First define some helpful notation.
Let $f_T(k)$ represent the number of $4\times k$ tilings of type T, where T is a set of starting configurations. That lets us say from what we have above that $$f(n)=f(n-1)+4f(n-2)+f_{\{F,G,H\}}(n)\textrm.$$ We just have to figure out $f_{\{F,G,H\}}(n)$ in terms of $f$.
Clearly $f_{\{F,G,H\}}(n)=f_{\{F\}}(n)+f_{\{G\}}(n)+f_{\{H\}}(n)$; we'll compute each term separately. Also take note of the fact that $f(k)=f_{\{A,B,C,D,E,F,G,H\}}(k)$.
Now on to the counting. We'll look at type F first.
A "type F" $4\times (n)$ tiling is always configuration F extended by a "type B" or "type F" $4\times (n-2)$ tiling that has its center left domino removed. So $f_F(n)$ is exactly the number of $4\times (n-2)$ "type B" or "type F" tilings, that is, $f_F(n)=f_{\{B,F\}}(n-2)$. (The type B and F tilings are exactly the ones that have a center left domino to remove.)
A "type G" tiling is G extended by a tiling of type A, C, or G, with the lower left domino removed, so $f_G(n)=f_{\{A,C,G\}}(n-2)$. (A, C, and G are the tiling types with a lower left domino.)
A "type H" tiling is H extended by a tiling of type A, D, or H, with the upper left domino removed. So $f_H(n)=f_{\{A,D,H\}}(n-2)$. (A, D, and H are the tiling with an upper left domino.)
Substituting these last three expressions into the previous displayed equation yields
$\begin{align*}
f(n)&=f(n-1)+4f(n-2)+f_{\{B,F\}}(n-2)+f_{\{A,D,H\}}(n-2)+f_{\{A,C,G\}}(n-2)\\
&=f(n-1)+4f(n-2)+f_{\{A,B,C,D,F,G,H\}}(n-2)+f_{\{A\}}(n-2)\\
&=f(n-1)+4f(n-2)+f(n-2)-f_{\{E\}}(n-2)+f_{\{A\}}(n-2)\\
&=f(n-1)+5f(n-2)+f_{\{A\}}(n-2)-f_{\{E\}}(n-2)
\end{align*}$
Fortunately, A and E are the simplest patterns, and we know from our initial calculations (which we did before adopting the subscript notation on $f$) that $f_{\{A\}}(n-2)= f(n-3)$ and $f_{\{E\}}(n-2)= f(n-4)$. These final calculations give the recurrence relation you asked about: $$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)\textrm.$$
I'll let someone else suggest good references for learning these techniques and just say experience helps. The hundredth one is a lot quicker to figure out than the first one!
Best Answer
Actually, the recurrence is $a_n=a_{n-1}+2a_{n-2}$. To understand why, let's consider a simple case. Say we already know that $a_1=1$ and $a_2=3$. Let's figure out $a_3$. Following your line of logic, we can fill in the the first $2\times 2$ box in 3 ways (since $a_2=3$). This forces us to fill in the remaining space with 1 vertical bar. So far, then, we have three possible tilings:
Next, consider the tilings in which we fill the first $2\times 1$ box. This can be done in 1 way (since $a_1=1$). Now, you might be tempted to say that, since the right $2\times 2$ box can be filled in 3 ways, we have three additional tilings:
But, as you can see, one of these tilings has already been counted (the one on the top). This means that we only have a total of 5 tilings. So, in summary: $$a_3=a_2+2a_1=3+2\cdot1=5$$
You can generalize this to get the following recurrence: $$a_n=a_{n-1}+2a_{n-2}$$
If you let $n=2$, you can see that $a_0$ must be $1$.