count the ways to fill a $4\times n$ board with dominoes After solving this problem from SPOJ (count the ways to fill a 4xn board with 2x1 dominoes) I found a different solution while searching on internet.
This solution uses the recurrence relation $f(n) = f(n-1)+5f(n-2)+f(n-3)-f(n-4)$ where $f(n)$ denotes the number of ways to fill the $4\times n$ board with $2 \times 1$ dominoes.
I don't fully understand how someone gets that kind of relation (I don't know almost anything of combinatorics or recurrence relations) but I think I understand something. The $f(n-1)$ term comes from observing that there is an unique way to fill the last column and the $5f(n-2)$ term comes from observing there are 5 different ways to fill the last two columns.

But i don't get where the terms $f(n-3)-f(n-4)$ come from. So I have two questions, the first one is where these terms come from and second I'd like to ask you for a reference to learn combinatorics and recurrence relations.
May you help me? Thanks in advance.
-edit-
For my solution I used a binary number to represent what configurations of the i-th column was valid. For example 1001 represent that rows 1 and 4 are blocked in the i-th row because in the (i-1)th there is an horizontal domino in that positions. I calculated all the valid transitions such binary numbers could go to (I did this by hand for all the binary numbers from 0000 to 1111). Then I got a function which I programmed using dynamic programming and a technique called bitmask to represent the binary numbers as integers. The function is:
$f(i,mask) = \begin{cases} 0 &\mbox{if } i = n, mask \neq 0 \\
1 & \mbox{if } i = n, mask = 0. \\
\sum f(i+1,mask') &\mbox{else} \end{cases}$
Where mask' is taken from the set of all valid masks from where mask could transition to, also i=n means the first column outside the board as I considered 0-indexing. The code for that is here (this is not actually mine, it's from a mate but it's the exactly same idea).
 A: I am not sure I can intuitively explain this recursive formula by itself (and don't think there is an easy explanation without going into numerous cases), but I wanted to give you a general approach that allows to derive such recursive expressions for any tiling problem $m\times n$.
First, I wanted to consider a slightly different problem: how many "connected" tilings on $m\times n$. By "connected" I mean the ones so that every two consecutive columns are connected by at least one tile. Let's call us this function $g(n)$.
We want to consider $g(n)$ mainly for two reasons:


*

*It should be much easier to derive, partly due to the fact that initial tiles will determine the rest of the tiling, and partly due to the second point.

*It is going to be periodic, i.e. there is some non-periodic part $g(1),\dots,g(N)$, and then there is a periodic "tail": for $k\ge 1$: $g(N+k)=g(N+k+T)$ for some fixed $T$.
The second property allows us to derive $f$ easily from $g$. Indeed, for every tiling let $k\ge 1$ be the maximum number so that the first $k$ columns are connected. Then, for every $k$ every possible tiling can be constructed as a connected tiling on the first $k$ columns, and then any tiling on the rest. In other words, for every $m,n$:
$$f(n)=g(1)f(n-1)+g(2)f(n-2)+\dots+g(n)f(0) \tag{1}$$
where $f(0)=1$.
Now, if $g$ has a non-zero periodic tail, then the expression (1) will grow with $n$, but we can consider (1) for two values $n$ and $n-T$, and by subtracting one from the other we will obtain an expression with fixed finite number of terms. We can even write down this expression explicitly, where $g()$ has $N$ non-periodic terms and period $T$:
$$f(n)=g(1)f(n-1)+\dots+g(T-1)f(n-T+1)+[g(T)+1]f(n-T)+[g(T+1)-g(1)]f(n-T-1)+\dots+[g(T+N)-g(N)]f(n-T-N) \tag{2}$$.
Let's look at how it works for different smaller values of $m$.
Tiles on $1\times n$: $m=1$. The number of connected tilings on $1\times n$ ($g(n)$) equals: $0,1,0,0,0,\dots$. Here $N=2$, $T=1$, but the tail is all zeros, so we do not need (2) to eliminate the tail. (1) gives us: $f(n)=f(n-2)$ with two initial terms $f(0)=1,f(1)=0$.
Tiles on $2\times n$: $m=2$. $g(n\ge 1)$ equals: $1,1,0,0,0,\dots$. Indeed, there are no connected tilings on $2\times n$ for $n\ge 3$. Once again, $N=2$ and $T=1$ with zero tail. (1) gives us $f(n)=f(n-1)+f(n-2)$ with initial terms $f(0)=1,f(1)=1$. This is just Fibonacci numbers. BTW, if we used (2), we would obtain another recursive sequence for Fibonacci numbers: $f(n)=2f(n-1)-f(n-3)$ with initial terms $f(0)=1,f(1)=1,f(2)=2$.
Tiles on $3\times n$: $m=3$. Here where it gets interesting, because it is the first time we will have a non-zero $g$-tail. $g(n)=0$ for odd $n$. $g(2)=3$: ⨅ ⨆ and ≡. $g(4)=g(6)=\dots=2$ (assume first that horizontal tile connecting the first two columns is top or bottom and construct the rest of connected tiling in unique way). So, $g(n)$ is $0,3,0,2,0,2,\dots$. Now, $N=2$ and $T=2$ and we have to use (2): $f(n)=4f(n-2)-f(n-4)$.
Finally, tiles on $4\times n$: $m=4$. First, we need to show that $g(n)$ for $n\ge 1$ equals $1,4,2,3,2,3,\dots$. The first two values (non-periodic part) is given (among 5 tilings of $4\times 2$ only one is disconnected). For $n>2$ consider three possible combinations of horizontal/vertical tiles covering the first column:
|    --   --
|    |    --
--   |    |
--   --   |

and show that each leads to a unique connected covering, and only two of them work for odd $n$. In this case (2) gives us: $f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)$.
A: 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!
A: The answer is here: A127864 or A077917.
The actual formula is: $f(n) = f(n-1) + 4 f(n-2) + 2 f(n-3)$. The sequence is: $1, 5, 11, 33, \dots$.
A: Let's split the tilings on N into 5 subtilings:

These are all possible board endings. Each tiling belongs to one and only one of these endings. 
Number of tilings with ending of 1 and 5 are trivial to write recursively. As 2 and 3 are symmetrical, number of tilings in both of these groups is equal, denoted by g(N). Let number of tilings with ending 4 be denoted with h(N). So we have:
f(N) = f(N-2) + f(N-1) + 2*g(N) + h(N)

For type 2 (and 3) the following recursive relation holds:
g(N) = f(N-2) + g(N-1)
First part if the hole is filled with vertical tile, second if it is filled with 2 horizontal tiles (giving the symmetrical tiling on N-1).

For type 4 the following recursive relation holds:
h(N) = f(N-2) + h(N-2) 
First part if the hole is filled with vertical tile, second if it is filled with 2 horizontal tiles (forcing horizontal tiles to be placed above and below the "bulge", giving repetition of the same structure on N-2).

Now we have a system of 3 equations of 3 recursive functions, which can be simplified as shown here: Simplify system of 3 equations of 3 recursive functions
Giving:
$$f(n) = f(n - 1)+ 5·f(n - 2)+ f(n - 3) - f(n - 4)  $$
P.S. Big thanks to @Sudix for simplifying the system of 3 equations on the referenced question. :)
