# recurrence relation with tiles or blocks of $2\times{n}$

There's a problem in our combinatorics class:

As you can see above we have a number of blocks (either of size 2x1 or 2x2). We need to fill a big block of size $2$x$n$ with these "small" blocks. The 2x1 blocks can be arranged either vertically or horizontally. So for example if we had a block of size 2x2 we could:

1. fill it with 2 horizontal 2x1 blocks
1. fill it with 2 vertical 2x1 blocks
2. lastly we could fill it with one 2x2 block

In total 3 options. Below is another example of a possible block to be filled:

We need to find the recurrence relation for this. I came up with this: $$a_n=a_{n-1}+3a_{n-2}$$ because if we use a 2x1 block vertically we have $n-1$ space to fill. If we place 2 vertical or 2 horizontal blocks or one square block (3 possibilities) then we need to fill $n-2$ space.

I'm not sure this is correct though. Also does $a_0$ equal $1$ or $2$?

• Actually, the recurrence should be $a_n=a_{n-1}+2a_{n-2}$, with $a_0=1$.
– Hrhm
Commented Sep 24, 2016 at 13:39
• Thanks! But why don't we need to take into account 3 options but just 2 as in your case?
– Yos
Commented Sep 24, 2016 at 13:40
• I'll type out a detailed answer below, explaining comment.
– Hrhm
Commented Sep 24, 2016 at 13:42
• Your third case, where you fill in the remaining $2\times 2$ box with vertical bars is invalid, since those tilings have already been considered. You already counted these tilings when you considered the case in which the first $2\times (n-1)$ is filled.
– Hrhm
Commented Sep 24, 2016 at 14:05

Actually, the recurrence is $a_n=a_{n-1}+2a_{n-2}$. To understand why, let's consider a simple case. Say we already know that $a_1=1$ and $a_2=3$. Let's figure out $a_3$. Following your line of logic, we can fill in the the first $2\times 2$ box in 3 ways (since $a_2=3$). This forces us to fill in the remaining space with 1 vertical bar. So far, then, we have three possible tilings:
Next, consider the tilings in which we fill the first $2\times 1$ box. This can be done in 1 way (since $a_1=1$). Now, you might be tempted to say that, since the right $2\times 2$ box can be filled in 3 ways, we have three additional tilings:
But, as you can see, one of these tilings has already been counted (the one on the top). This means that we only have a total of 5 tilings. So, in summary: $$a_3=a_2+2a_1=3+2\cdot1=5$$
You can generalize this to get the following recurrence: $$a_n=a_{n-1}+2a_{n-2}$$
If you let $n=2$, you can see that $a_0$ must be $1$.