Problem 1012

Trivially there is 1 way to tile a $3 \times 0$ rectangle, and it is not hard to see there are 3 ways to tile a $3 \times 2$. Let $T_{n}$ be the number of tilings of a $3 \times n$ rectangle, where $n$ is even. From the diagram below we see the recursion $T_{n}=3 T_{n-2}+2\left(T_{n-4}+T_{n-6}+\ldots+T_{2}+T_{0}\right)$. Given that, we can just calculate $T_{4}=11, T_{6}=41$, and $T_{8}$ is 153.