Problem Solving

The problem I was working on is from Professor Heap's email:



Suppose you have tiles that are 1*2 rectangles, and you have a walk that is 2*3 units long. There are three ways to tile your walk: three vertical tiles, on vertical tile followed by two horizontal tiles, or two horizontal tiles followed by one vertical tile.
How many different ways are there to tile a 2*4 walk, or (indeed) a 2*n walk(where n is some natural number)? Can you come up with a general procedure that works?
What happens if your tiles are 1*3, and you have a walk that is 3*n units long?

I think the best way to solve this problem is to draw every possible way.

Walk              # of ways

2*1                 1

2*2                 2

2*3                 3

2*4                 5   

2*5                 8

2*6                 13

...

From the list above, we can easily find that the number of ways are Fibonacci numbers.

i.e. when there is a 2*n walk, there will be 

(1/√5)*{[(1+√5)/2]^(n+1) - [(1-√5)/2]^(n+1)}

ways to tile the walk.

After answering the first question, I tried to work on the second question:

Walk                           # of ways

3*1                                   1

3*2                                   1

3*3                                   2

3*4                                   3

3*5                                   4

3*6                                   6

......

However, according to the list above, I was not able to figure out the rule  of the number sequence. Thus I still have to work on this problem.