A recursive relation for the number of ways to tile a 2 x n grid with 2x1, 1x2, 1x1 and 2x2 dominos I'm trying to solve this problem: In how many ways can you cover a 2xn grid with 1x1, 1x2, 2x1, 2x2 dominos? And here is my attempt: Let a(n) be the number of ways we can cover the grid. Then if we start by putting a 2xn domino first then we have a(n-1) ways to complete the rest of the grid. If we put a 2x2 domino first then we have a(n-2) ways to cover the rest of the grid. If we put a 1x1 domino first (up or down) than we can put either a 1x1 domino or 1x2 domino below (or above) it. If we put the 1x1 domino then we have a(n-1) ways to complete the rest of the grid. Now the problem is when we put the 1x2 domino. I tried to define and find a new recursive relation b(n) for this case of the problem but I am always neglecting some cases. Can anyone help me?
 A: Let $b_n$ be the number of tilings of a $2\times n$ board with one corner removed. We define $b_n$ this way because this is the shape that arises when you place a $1\times 1$ and a $1\times 2$ along the left edge of the board.
This gives the following recurrence for $a_{n}$:
$$
a_n=
\underbrace{a_{n-1}}_{2\times 1}+
\underbrace{a_{n-2}}_{2\times 2}+
\underbrace{a_{n-1}}_{1\times 1\text{ on } 1\times 1}+
\underbrace{b_{n-1}}_{1\times 1\text{ on } 1\times 2}+
\underbrace{b_{n-1}}_{1\times 2\text{ on }1\times 1}+
\underbrace{a_{n-2}}_{1\times 2\text{ on }1\times 2}\qquad (n\ge 2)
$$
Now, you just need a recurrence for $b_n$. This is easier, since there are only two cases; either you place a $1\times 1$ in the spot vertically next to the removed corner, or you place a $1\times 2$ there. That is,
$$
b_n = b_{n-1}+a_{n-1}\qquad (n\ge 2)
$$
Now you need to solve these two mutual recurrences. Note that the first recurrence can be solved for $b_{n-1}$, and then you can substitute that into the second expression to get a recurrence involving $a$ alone.
