There two types of tiles, we need to construct a $2 \times n$ rectangle filled with them. How many ways are there to do that?

Question

Two types of tiles are defined:

• tile $B$: a simple $1 \times 1$ sqaure tile,
• tile $B$: we divide a $2×2$ square tile with segments connecting the centers of opposite sides into four $1 \times 1$ tiles, and then remove one of these four tiles.

In how many ways can a $2×n$ rectangle $(n \geq 1)$ be filled with tiles of those $2$ types? Write a suitable equation or system of recursive equations and give the general formula.

---

On the place n, we can put:

• $2$ tiles $A$, in one possible way and with assumption that the rectangle $2 \times n-1$ is correct - so we get $a_{n-1}$, those are the ways:

  

• $1$ tile $A$ with $1$ tile $B$, in one of $4$ ways and with assumption that the rectangle $2 \times n-2$ is correct - so we get $4a_{n-2}$, those are the ways:

  ; ; ;

• $2$ tiles $B$, in one of $2$ ways and with assumption that the rectangle $2 \times n-3$ is correct - so we get $2a_{n-3}$, those are the ways:

  ;

Therefore, my idea of recursive formula goes as follows:

• $a_n = a_{n-1} + 4a_{n-2} + 2a_{n-3}$

These are all the combinations of tiles I can come up with. Other seem to be obtained by combination of those.

From that I get: ${ \lambda}^{3}-{ \lambda}^{2}-4{ \lambda} -2 = ({ \lambda} +1) ({ \lambda}^2 - 2{ \lambda} - 2) = ({ \lambda} +1)({ \lambda} - (1- \sqrt{3}))({ \lambda} - (1 + \sqrt{3}))$

So I get: $$a_n = b(-1)^n + c(1- \sqrt{3})^n + d(1 + \sqrt{3})^n$$

Then I calculate first $3$ terms manually:

• $a_1 = 1$, because we can only choose:

  • $2$ tiles of type $A$ ($\{ A,A \}$)

• $a_2 = 5$, because we can choose:

  • $4$ tiles of type $A$ ($\{A,A \}$) OR
  • one of $4$ possible sets of tile $B$ combined with tile $A$ ($\{ B+A \}$),

• $a_3 = 1 + 4 \cdot 2 + 2 = 11$, because we can choose:

  • $6$ tiles of type $A$ ($ \{ A,A,A \}$) OR
  • one of $4$ possible sets of tile $B$ combined with tile $A$ together with $2$ tiles of type $A$ and then put them all together in one of $2$ ways ($\{B+A,A \}$ or $\{A,B+A \}$) OR
  • $2$ tiles of type $B$ combined in one of $2$ ways ($ \{B+B \} \times 2$)

• $a_4 = 1 + 4 \cdot 4 + 4 \cdot 3 + 2 \cdot 2 = 1 + 16 + 12 + 4 = 33$, because we can choose:

  • $8$ tiles of type $A$ ({ A,A,A,A }) OR
  • one of $4$ possible sets of tile $B$ combined with one of $4$ possible sets of tile $B$ ({ B+A,B+A }) OR
  • one of $4$ possible sets of tile $B$ combined with tile $A$ together with $4$ tiles of type $A$ and then put them all together in one of $3$ ways ( $\{B+A,A,A \}$ or $\{A,B+A,A \}$ or $\{ A,A,B+A \}$ ) OR
  • one of $2$ possible sets of $2$ tiles $B$ combined together with with $2$ tiles of type $A$ and then put them all together in one of $2$ ways ( $\{B+B,A \}$ or $\{A,B+B \}$)

• $a_5 = 1 + 4 \cdot 4 \cdot 3 + 4 \cdot 4 + 2 \cdot 3 + 2 \cdot 4 \cdot 2 = 1 + 48 + 16 + 6 + 16 = 87$, because we can choose:

  • $10$ tiles of type $A$ ({ A,A,A,A,A }) OR
  • one of $4$ possible sets of tile $B+A$ combined with one of $4$ possible sets of tile $B+A$ combined with tiles $A$ in one of $3$ ways ({ A, B+A,B+A } or { B+A, A, B+A } or { B+A, B+A, A } ) OR
  • one of $4$ possible sets of tile $B+A$ combined with tile $A$ together with $6$ tiles of type $A$ and then put them all together in one of $4$ ways ( $\{B+A,A,A,A \}$ or $\{A,B+A,A,A \}$ or $\{ A,A,B+A,A \}$ or $\{ A,A,A,B+A \}$ ) OR
  • one of $2$ possible sets of $2$ tiles $B$ combined together with with $4$ tiles of type $A$ and then put them all together in one of $3$ ways ( $\{A,A,B+B \}$ or $\{A,B+B,A \}$ or $\{A,A,B+B \}$)
  • one of $2$ possible sets of $2$ tiles $B$ combined together with with tile of type $B$ joined with tile of type $A$ and then put them all together in one of $2$ ways ( $\{B+B,B+A \}$ or $\{B+A,B+B \}$)

Now, to get the ultimate solution, I need to solve the system of equations:

• $a_1 = 1 = -b + c(1- \sqrt{3}) + d(1 + \sqrt{3})$
• $a_2 = 5 = b + c(1- \sqrt{3})^2 + d(1 + \sqrt{3})^2$
• $a_3 = 11 = -b + c(1- \sqrt{3})^3 + d(1 + \sqrt{3})^3$

After some attempts I did that using matrix calculator. The correct values should be:

• $b = 1$
• $c = \frac{-\sqrt{3}}{3}$
• $d = \frac{\sqrt{3}}{3}$

And from that I get:

$$a_n = (-1)^n + \frac{-\sqrt{3}}{3}(1- \sqrt{3})^n + \frac{\sqrt{3}}{3}(1 + \sqrt{3})^n$$

The formula works for values $a_4$ and $a_5$:

• $a_4 = (-1)^4 + \frac{-\sqrt{3}}{3}(1- \sqrt{3})^4 + \frac{\sqrt{3}}{3}(1 + \sqrt{3})^4 = 33$
• $a_5 = (-1)^5 + \frac{-\sqrt{3}}{3}(1- \sqrt{3})^5 + \frac{\sqrt{3}}{3}(1 + \sqrt{3})^5 = 87 $

Therefore I assume the solution is correct.