Recurrence for filling a $2\times 2\times n$ box with $1\times 1\times 2$ blocks. I am asking about how to derive a particular recurrence for this combinatorial problem:

In how many ways can a $2\times 2\times n$ box be filled with $1\times 1\times 2$ blocks?

Letting $F(n)$ be the number of ways, the OEIS entry for this sequence (http://oeis.org/A006253) gives the following recurrence, without proof:
$$
F(n) = 4F(n-1) - F(n-2) + 2 \cdot  (-1)^n\qquad \text{ for $n\ge 3$},
$$
with the base cases $F(1)=2$ and $F(2)=9$. Can anyone see how to derive this recurrence?
 A: We divide the $2\times 2\times n$ box into unit cubes. The cubes are labeled with ordered triples $(x,y,z)$, such that $x,y\in \{1,2\}$ and $z\in \{1,\dots,n\}$.
There are three possibilities for the orientation of the block which covers $(1,1,1)$: sticking up, or laying horizontally in one of two orientations. If this block lies horizontally, what remains is a shape I will called a "dog-eared box". I will let $G(n)$ be the number of ways to fill a dog-eared box with height $n$, with the goal of setting up a mutual recurrence between $F(n)$ and $G(n)$. So far, we have
$$
F(n) = G(n) + G(n) + \underline{\hspace{1.5cm}},
$$
where the _____ corresponds to the cases where the block covering $(1,1,1)$ is standing on end. In this case, we next consider the block covering $(2,1,1)$.

*

*If this block is also vertical, then there are two cases. If the block covering $(2,2,1)$ is horizontal, in which case there are $G(n-1)$ to cover what remains. Otherwise, the block covering $(2,2,2)$ is also vertical, which forces a vertical block at $(1,2,1)$, leaving $F(n-2)$ ways to do the rest.


*If this block is horizontal, then the block covering $(1,2,1)$ must be vertical, leaving $G(n-1)$.
We have proved
$$
F(n) = 2G(n) + 2G(n-1) + F(n-2) \qquad (n\ge 2)
$$
Similar analysis proves
$$
G(n) = F(n-1) + G(n-1) \qquad (n \ge 1)
$$
We get a recurrence for $F(n)$ alone as follows. For any $n\ge 3$,
$$
\begin{align}
&\hspace{-1cm}F(n) - \color{purple}{F(n-1)} 
\\&= [2G(n)+2G(n-1)+F(n-2)]-[\color{purple}{2G(n-1)+2G(n-2)+F(n-3)}]
\\&= 2[\color{blue}{G(n)-G(n-1)}] + 2[\color{green}{G(n-1)-G(n-2)}] + F(n-2)-F(n-3)
\\&= 2\color{blue}{F(n-1)} + 2\color{green}{F(n-2)} + F(n-2)-F(n-3)
\end{align}
$$
All in all, we get
$$
F(n) = 3F(n-1)+3F(n-2)-F(n-3)\qquad (n\ge 3)\tag{$*$}
$$
We can now use $(*)$ prove that $F(n)=4F(n-1)-F(n-2)+2(-1)^n$ by induction on $n$. I will show the inductive step, and leave the obvious base cases to you. For any $n\ge 5$, we have
\begin{align}
F(n) 
  &= 3F(n-1)+3F(n-2)-F(n-3)
\\\\&=     \phantom{{}+{}} 3\cdot [4F(n-2)-F(n-3)+2(-1)^{n-1}]
\\&\phantom{{}={}}+  3\cdot [4F(n-3)-F(n-4)+2(-1)^{n-2}]
\\&\phantom{{}={}}-  [4F(n-4)-F(n-5)+2(-1)^{n-3}]
\\\\&=     \phantom{{}+{}} 4\cdot [\color{blue}{3F(n-2)+3F(n-3)-F(n-4)}]
\\&\phantom{{}={}}-   [\color{purple}{3F(n-3)+3F(n-4)-F(n-5)}]
\\&\phantom{{}={}}+  [3\cdot 2\cdot (-1)^{n-2}+3\cdot 2\cdot (-1)^{n-3}-2\cdot (-1)^{n-3}]
\\\\&= 4\cdot \color{blue}{F(n-1)}-\color{purple}{F(n-2)}+2(-1)^n
\end{align}
Since this required $n\ge 5$, you need to check the base cases $F(0),F(1),\dots,F(4)$ to complete the proof.
