Problem solving episode---WalkTilings(2)

I have shown the solution for the problem when n is small(from 1 to 5). Now I will find out the relationship between n and n + 1, beginning from small n. Suppose the solution for n is f(n).

How to get the solution for n = 3 from n = 2? My idea is that first put a tile in the leftmost 2*1 rectangle, then for the left 2*2 rectangle, I have 2 choices to put tiles, which is the solution for n = 2. Then I expand the leftmost 2*1 rectangle to the leftmost 2*2 rectangle. I have two choices to put tiles in this rectangle, but to avoid duplicates, I can only tile this one with two horizontal 2*1 tiles. So in total, there are 3 choices, 3 = 2 + 1 = f(2) + f(1).

Now consider n = 4. First, put a tile in the leftmost 2*1 rectangle, then for the left 2*3 rectangle, I have f(3) choices. Expand the leftmost 2*1 rectangle to the leftmost 2*2 rectangle. Still, to avoid duplicates, the 2*2 rectangle can only be tiled with two horizontal 2*1 tiles. For the left 2*2 rectangle, I have f(2) choices. Expand again the 2*2 rectangle to 2*3 rectangle. Though I have f(3) choices to tile this rectangle, each of them is identical to a way I put tiles before. So in total, f(4) = f(3) + f(2).

For n = 5, I still need to consider only two situations: when the leftmost rectangle is 2*1 and when the leftmost rectangle is 2*2. Then I get f(5) = f(4) + f(3).

But why is it true? I find out that when the leftmost rectangle is 2*2, the way I put two vertical tiles in it has occured in the previous step when the leftmost rectangle is 2*1. So I can only put two horizontal tiles in the 2*2 rectangle. When the leftmost rectangle is 2*3, all choices that I arrange tiles in it have occured in previous two steps. For rectangles of 2*4, 2*5,.., 2*(n-1), all choices that I arrange tiles in them have occured in the first two steps. So for any natural number n >=3, I just need to consider two situations: when the leftmost rectangle is 2*1, in which case the choices are f(n-1) and when the leftmost rectangle is 2*2, in which case the choices are f(n-2). So in total, f(n) = f(n-1) + f(n-2).