Why does this application of Jacobsthal numbers defined by the recurrence relation: $a_n$ = $a_{n-1}$ + 2$a_{n-2}$ work in 2D tiles / grids?

Question

Problem Statement: Find the Recurrence Relation for $a_n$, where $a_n$ is the number of ways to tile a (2xn) rectangular board with (1x2) or (2x2) pieces.

. .

Note: A (1x2) piece can be placed either vertically or horizontally

. .

The solution to this question goes like this:

Considering the last column(s) of the board: There are 3 cases.

• filled by (2x2) piece - i.e. there are $a_{n-2}$ ways remaining
• filled by (1x2) piece which is placed horizontally - i.e. there are $a_{n-2}$ ways remaining
• filled by (1x2) piece which is placed vertically - i.e. there are $a_{n-1}$ ways remaining

Therefore, $a_n$ = $a_{n-1}$ + 2$a_{n-2}$

. .

As much as this line of reasoning makes sense, when I sub n=3 into $a_n$ = $a_{n-1}$ + 2$a_{n-2}$, the number of grid squares for $a_n$ is 6 while the number of grid squares for $a_{n-1}$ + 2$a_{n-2}$ is 8? This makes me wonder whether there is a better visual intuition of the recurrence relation: $a_n$ = $a_{n-1}$ + 2$a_{n-2}$ since the Jacobsthal number sequence is originally for 1D number sequence?

Answer 1

For $n=3$, let's use your numbering

1 2 3
4 5 6

The first case corresponds to removing the $2\times 2$ 2356 tile, leaving

1
4

and there is only $a_{3-2}=a_1=1$ way to complete the tiling.

The second case corresponds to removing the horizontal 23 and 56 tiles, leaving

1
4

and there is only $a_{3-2}=a_1=1$ way to complete the tiling.

The third case corresponds to removing the vertical 36 tile, leaving

1 2
4 5

and there are $a_{3-1}=a_2=3$ ways to complete the tiling.

So $a_3 = 2a_{3-2}+a_{3-1} = 2 a_1 + a_2 = 2\cdot 1 + 3 = 5$.