Tiling Problem

1. understand my problem.
in my understanding, I am suppose to come up with general procedure of this tiling problem. I am supposed to match the 1 x 2 tiles to 2 x n units.

2. Plan
My plan is i am going to draw the units with the actual size (my plan is to draw 2x1, 2x2, 2x3, 2x4, 2x5, 2x6, 2x7, and 2x8) and also draw several 1 x 2 tiles with different color to differentiate, also, some of them is horizontal, and some of them is vertical. Then i will try to match up the tiles to the unit in different ways to determine how many ways are there to tile each unit. then, I am going to record every different way and compare different size. After I have my data, I am going to try to determine the general formula to be able to know how many different way possible to tile 2 x n unit.

3. first, I am going to draw the unit and the tiles, here is the example on how i do it.

After I tried different way to tile the unit, I record it and here is the data I have got, I am using the 'v and h' code, v is vertical tile and h as horizontal tiles.

  

now, I compare the date in order to come up with the general formula.

It took me quite sometimes to figure out the formula, there is no much similarity between each other, I can see the pattern, it is quite obvious, for example, for 2 x n unit, there will be at least n number of way. But after that there is no obvious similarity. Until I see the total number of each different unit. 

unit 2 x 3 where the total is 3 is the sum of the previous 2 units which are 2 + 1. Another example, unit 2 x 5, with the total of 8 is the sum of the total for unit 2 x 3 and 2 x 4 which -> 5 = 3 + 5. And this pattern works for all the units I have drawn. Therefore, I conclude, the general pattern for 2 x n unit is 

Un = U(n-1) + U(n-2). 

4. The challenge I find doing this problem are, first, it is not quite easy to record the data as n grows larger, I had to repeat for more that 4 times in order to get right result because as the unit grows bigger, more and more tiles can fit into the unit, and this means more possibilities of patterns.

second, coming up with the formula is not easy, because as I mentioned before, there is no obvious pattern that I can see from the data, I even make the color difference in order to see the difference.