Finding formula using a recurrence relation

Question

I have a question:

A $2 \times n$ rectangle is to be paved using $1 \times 2$ tiles, (which can be placed either vertically or horizontally), and $2 \times 2$ tiles. The $1 \times 2$ tiles come in four colors and the $2 \times 2$ tiles come in nine colors. Finally, if two $1 \times 2$ tiles are placed horizontally to create a $2 \times 2$ square, they cannot be the same color.

If $A$ represents the number of ways to pave the rectangle, then how do I find an explicit formula for $A$? I believe that I need to find and solve a recurrence relation to get this formula, but am having trouble accomplishing that due to the restrictions (eg, the colors of the tiles).

All I have so far is that (if I ignore the colours), I get $a_n=a_{n−1}+2a_{n−2}$. However, I don't understand where to go from there or how to use the fact that there are four colours of $1 \times 2$ tiles and nine colours of $2\times 2$ tiles. Any advice?

Update: I have been trying to solve this question using Arnaud Mortier's hint, but I have still not been successful. Any other suggestions?

Answer 1

Hint: To build a tiling of size $n\times 2$ and which starts with a vertical tile you have to

• Choose that vertical tile ($4$ options)
• Choose how to tile the remaining $(n-1)\times 2$ rectangle ($A_{n-1}$ options).

These choices are independent, so the correct recurrence relation starts with $$A_n=4A_{n-1}+\ldots$$

Answer 2

The tiling can start in one of three ways: with

1. a $2 \times 2$ tile,
2. two horizontally placed tiles, or
3. a vertical tile.

Now taking the colors into account, there are nine ways to do the first, $3 \times 4 = 12$ ways to do the second (it would be 16 if the two colors could be the same), and 4 ways to do the last. And in each case, the remainder of the tiling is a rectangle that is 2 (case 1 and 2) or one 1 square narrower (case 3).

Taking all this together, we get:

$A_n = 9A_{n - 2} + 12 A_{n-2} + 4A_{n - 1} = 21A_{n-2} + 4A_{n-1}$

(The last term is that in Arnaud's hint.)

And it's easy to see** that $A_1 = 4$, and $A_2 = 16 + 12 + 9 = 37$. So the sequence starts $4, 37, ...$. You can now solve this recurrence using standard techniques. (You can see here for example: http://discretetext.oscarlevin.com/dmoi/sec_recurrence.html if you don't already know this part.)

Using the characteristic equation method, we find that

$A_n = a7^n + b(-3)^n$, where we use the first two terms to solve for $a$ and $b$.

You can fill in the details, but the answer comes down to:

$A_n = \frac{7}{10}7^n + \frac{3}{10}(-3)^n$.

** In an earlier version of this answer I made a mistake with the second term, so "easy to see" may not be the right wording.