Number of different ways of filling $N \times 4$ rectangle with Dominoes Given a Nx4 (width = N and height = 4) rectangle. How many different ways are there to fill with Dominoes (2x1 or 1x2)?
I have found an OEIS sequence http://oeis.org/A005178  for this. 
The recurrence given in the link is a(n) = a(n-1)+5*a(n-2)+a(n-3)-a(n-4).   
Any combinatorial proof? or how to get the recurrence?
 A: I posted this as an answer to another question, but since there is still no answer, I thought I would 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)$.
