Let = number of ways to tile columns to completely, with column having profile . The profile tells you which cells in column are already filled by vertical tiles from column . Base case: .
You start with no columns filled and an empty profile. All other are because you can't have a non-empty profile before placing any tiles. Goal: . After filling all columns, the final profile must be empty (no tiles sticking out). This counts all complete tilings.