In how many ways can you tile a $3×n$ rectangle by $2×1$ dominoes?
We claim that, for $n \in \mathbb{N}$, the number of ways to tile a $3 \times n$ rectangle using $2 \times 1$ dominoes is given by the recurrence $f(n)$ such that:
$$ f(n) = \begin{cases} 0, & \text{if } n\text{ is odd},\\ 1, & \text{if } n = 0,\\ 4f(n-2) - f(n-4) & \text{otherwise.} \end{cases} $$
Here is the proof. First, notice that for odd choices of $n$, it is impossible to tile the rectangular grid since the placement of a tile reduces the remaining squares in the grid by $2$. A successful tiling reduces the remaining squares to $0$, but repeated subtraction of $2$ grid squares (i.e., dividing $n$ by $2$) never results in a remainder of $0$. Secondly, there is trivially only $1$ way to tile the (nonexistent) grid when $n = 0$: use $0$ dominoes.
After establishing an additional base case, we will proceed by strong induction (on $n$) to prove the more general case (i.e., when $n > 0$ and $n$ is even). Namely, we will show that the number of tilings of a $3 \times n$ rectangle using $2 \times 1$ dominoes (referred to as simply ``dominoes'' in the remainder of this document) is given by:
$$ f(n) = 3f(n-2) + 2\sum_{i = 4}^{n}f(n-i), $$
assuming all $f(n - i)$ correctly counts the number of tilings on a grid sized $3 \times (n - i)$, for all integers $i$ where $0 < i \leq n$.
For the purposes of the discussion below, we zero-index columns from the left when the grid has $3$ rows and $n$ columns.
In addition to the establishment of the base cases above, the following figures are sufficient to show that $f(2) = 3$:
It can also be explicitly shown that $f(4) = 11$.
Our inductive hypothesis is that $f(n) = 3f(n-2) + 2\sum_{i = 4}^{n}f(n-i)$ correctly counts the number of tilings on an $3 \times n$ grid. We will show that (by assuming $f(n-i)$ correctly counts the number of tilings on a $3 \times (n-i)$ grid for all $i \in \mathbb{N}$ and $n \geq i \geq 4$) there are $3f(n-2) + 2\sum_{i = 4}^{n}f(n-i)$ unique tilings of a $3 \times n$ grid.
As shown above, $f(2) = 3$. For a $3 \times n$ grid, columns $0$ and $1$ can be tiled $3$ unique ways, leaving an untiled $3 \times (n-2)$ grid. Assuming there are $f(n-2)$ unique ways to tile a $3 \times (n-2)$ grid, there are $3\cdot f(n-2)$ unique ways to tile a $3 \times n$ grid when the first two columns are tiled independently of the other columns. This accounts for the first term of $f(n)$.
We claim that the next term, $2\sum_{i = 4}^{n}f(n-i)$, counts the tilings where there exists an offset shape. An offset shape exists in a tiling whenever the tiling contains one of the $2$ following orientations:
Notice that an offset shape exists whenever exactly two horizontal dominoes in consecutive rows (the gray tiles above) span columns $1$ and $2$. It can be shown that these dominoes force the subsequent placement of tiles up to (but not including) some column $m$ (for even $m$ and $n > m \geq 4$).