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:
- fill it with 2 horizontal 2x1 blocks
- fill it with 2 vertical 2x1 blocks
- 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 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$.