Recurrence relation for number of ways covering $3\times N$ rectangle with dominos

Question

Here is a problem:

Find a number of ways to cover $3\times N$ rectangle with $1\times 2$ and $2\times 1$ dominos.

For odd $N$, the answer is 0. For even $N$, I found the recurrence relation of $a_{n}$, the number of ways to cover $3\times n$ rectangle.

$$ a_{n} = 3a_{n-2} + \sum_{j=0}^{(n-4)/2} 2a_{2j} $$ This can be proved in the following way: consider the right-most vertical line formed by dominos.

Then we will divide case by the number of blocks on the right of the line. If there are only 3 dominos, then we have 3 possibilities for the right side

and $a_{n-2}$ possibilities for the left side. This contributes $3a_{n-2}$ for the sum. If there are more than 3 dominos, i.e. $3j$ dominos for $j\geq 2$, then we have two possibilities for the right side

and $a_{n-2j}$ possibilities for the left side. This contributes $2a_{n-2j}$ for the sum. Now replace $n$ by $n-2$ and $$ a_{n-2} = 3a_{n-4} + \sum_{j=0}^{(n-6)/2} 2a_{2j}. $$ If we subtract two equations, we get $$ a_{n} = 4a_{n-2} - a_{n-4} $$ and using this, we can find the general formula for $a_{n}$. However, I want to know if it is possible to show the above equation directly, by using simple arguments like above. (Find some bijections.) Is it possible to show $a_{n} + a_{n-4} = 4a_{n-2}$ directly? Thanks in advance.

Answer 1

Let $a_n$ be the number of ways to tile a $3\times n$ rectangle, let $b_n$ be the number of ways to tile a $3\times n$ rectangle minus its top left field (or equivalently: minus its bottom left field).

Then $$a_n=a_{n-2}+2b_{n-1}$$ because we either have three horizontal dominoes at the left edge (leaing a $3\times (n-2)$ rect), or in one of two different ways a vertical domino and then par force a horizontal domino (leavong a $3\times (n-1)$ rect minus one corner).

And $$b_n=a_{n-1}+b_{n-2}$$ because we either have a vertical domino at the left covering the lower left corner, or a horizontal domino and then par force two more horizontal dominoes.

Now $$ \begin{align}a_n&=a_{n-2}+2b_{n-1}\\ &=a_{n-2}+2a_{n-2}+2b_{n-3}\\ &=a_{n-2}+2a_{n-2}+a_{n-2}-a_{n-4}\end{align}$$