The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile.
Question 1) In the recursive formula for
g(n) = f(n-1) + h(n-1)
Why didn't we include the case that we can also put a 2x1 tile horizontally on the top row. Something like -
g(n) = f(n-1) + h(n-1) + x(n-3)
f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2) still holds.
Basically, are we not looking into the cases how we can start tiling from the state
g(n) ? ither we add an L-shaped tile, and look at
f(n-1), or we add a 2x1 tile in the bottom layer and look at
h(n-1), or add a 2x1 tile in the top layer and look at
Question 2) It seems like while writing the recursion, we should only deal with cases that we have already named, i.e. only moving from state g(n) to h(n-1) or moving from state g(n) to f(n-1) ? Is it true, that when once we have decided which states to deal with, we only consider those states?