Tri Tiling - Recurrence Discovery

Let $a_n$ = number of tilings of $3 \times n$. Using broken profile DP with $3$ rows, you find that $a_n = 4a_{n-2} - a_{n-4}$ for $n \geq 4$, with $a_0 = 1$ and $a_2 = 3$. Why this formula? The profile transitions for width $3$ have special symmetry.

When you work out all valid transitions, certain profiles combine predictably, collapsing into this clean formula. You can compute $a_n$ in $O(n)$ time with a simple loop. The lesson here is that broken profile DP reveals the structure behind the recurrence.