Recurrence for filling a $2\times 2\times n$ box with $1\times 1\times 2$ blocks.

Question

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?

Answer 1

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.