Tiling a 2 × n board with dominoes and squares

Idea. Condition on what covers the last column(s).

Recurrence. Put $a_0=1$ (empty tiling) and $a_1=1$ (one vertical domino). For $n\ge2$, look at the right end of the board:
- a vertical domino covers the last column: $a_{n-1}$ tilings of the rest;
- otherwise the top-right cell is covered by a horizontal domino, which then forces a second horizontal domino directly below it: this covers the last two columns, $a_{n-2}$ tilings of the rest;
- a $2\times2$ square covers the last two columns: $a_{n-2}$ tilings of the rest.

These three cases are exhaustive and disjoint, so
$$a_n=a_{n-1}+2a_{n-2}.$$

Solving. The characteristic equation $r^2=r+2$ has roots $2$ and $-1$, so $a_n=A\,2^n+B(-1)^n$. From $a_0=1$ and $a_1=1$: $A+B=1$ and $2A-B=1$, giving $A=\frac23$, $B=\frac13$. Hence $a_n=\frac{2^{n+1}+(-1)^n}3$.

Generating function check. With $F(x)=\sum a_nx^n$, the recurrence gives $F(x)(1-x-2x^2)=1$, that is $F(x)=\dfrac1{(1-2x)(1+x)}=\dfrac13\left(\dfrac2{1-2x}+\dfrac1{1+x}\right)$, the same formula.

Value. $a_{10}=\dfrac{2^{11}+1}3=683$.

Lesson. Condition on the last block, turn the count into a linear recurrence, solve it with the characteristic equation or a generating function.