Domino Tiling Recurrences

Quant finance screeners ask for tiling counts and, more importantly, the intuition behind the recurrence. The first-round version uses a `2 x N` rectangle with `1 x 2` / `2 x 1` dominoes; an onsite follow-up asks about `3 x N`. Requirements Explain how many ways a 2 x N rectangle can be tiled with dominoes of size 1 x 2 and 2 x 1. Derive the recurrence intuition rather than only guessing the sequence. Follow-up variant: discuss the harder 3 x N rectangle with the same dominoes. Notes For 2 x N, the recurrence is Fibonacci-like: the leftmost part is either one vertical domino plus a 2 x (N-1) remainder, or two horizontal dominoes stacked plus a 2 x (N-2) remainder. The 3 x N variant is not the same simple Fibonacci recurrence. Odd N has zero tilings, and even N requires tracking additional states or a known recurrence. Interviewers push on intuition. Saying "it is Fibonacci" without explaining the decomposition is not enough. Preparation Derive 2 x N from first principles until you can explain it verbally in under two minutes. Work out 3 x N for N = 1..6 by hand and identify why odd widths fail. Practice defining state variables for tiling DP instead of memorizing only sequence values.