Simplified Recurrence - Walkthrough

For small width, Broken Profile DP often reduces to a simple recurrence. Hand-find or compute numerically. Method $1$: compute first $10$ values with DP, then guess the recurrence and verify.

Method $2$: the transition matrix has constant size. Its eigenvalues determine the recurrence's characteristic polynomial. Example: $2 \times n$ domino tiling has $f[n] = f[n-1] + f[n-2]$ (Fibonacci). The transition matrix is $[[1,1],[1,0]]$.