Here's a sketch of a proof of the recurrence (S = square, D = domino):

We want to construct a tiling of length n.  Let's do it by making sure  
we get all possible end sequences for the tiling (..DS, ..DSS, ..DD,  
..DSD, ..SSD). We have two options:

(1) Start with any legal tiling of length n-1, then add a square: if  
there are then three squares at the end, fuse the last two into a  
domino.  This finds all tilings that end in DS and DSS, as well as  
ones that end in DSD (the last kind ended in two squares before the  
process).  Conversely, if we chop off the last square from a sequence  
of length n, chopping apart a domino if the sequence ends in DSD, then  
we get legal sequences of length n-1.

(2) So we need to find the tilings that end in DD and SSD.  Suppose we  
have a n-length tiling ending in one of these.  Note that if we chop  
off the DD we get a legal tiling of length n-4 ending in S, and if we  
chop off an SSD we get a legal tiling of length n-4 ending in D;  
conversely, we can add DD or SSD to each tiling of length n-4 (which  
one depending on what it ends with) to get tilings of length n with  
those endings.

Thus every tiling of length n is constructible in this way from a  
tiling of length n-1 (if it ends in DS, DSS, or DSD) or a tiling of  
length n-4 (if it ends in DD or SSD).  This is our bijection.

To get the other recursion, the cases are endings of (a) DSS or SD  
from n-2; (b) SDD and DSDS from n-4, and (c) DSSDS and SDDS from n-5.   
It's easy to see that this is all possible endings.  This proof  
requires no fusing tricks (just add the appropriate tiles to the end  
depending on the last tile of the shorter-length tiling).

-Brian Rice