Fibonacci and Possible Tilings

Date: 09/24/2003 at 00:01:01
From: Ashley
Subject: Fibonacci's sequence

I'm supposed to solve the folowing problem using Fibonacci's 
sequence:

  You are going to pave a 15 ft by 2 ft walkway with 
  1 ft by 2 ft paving stones. How many possible ways 
  are there to pave the walkway?

However, I don't see how it relates to the problem. Can you help me
get started?  

I thought I just went to the 15th number in his sequence (because 
there are 15 stones) but I'm not quite sure why that would work, if 
it does.

Date: 09/24/2003 at 03:09:16
From: Doctor Floor
Subject: Re: Fibonacci's sequence

Hi, Ashley,

Thanks for your nice question.

To get started, you can try to find out how you can pave a walkway
that is N ft by 2 ft.

When N=1 it is easy, there is only one way.

When N=2 you can pave in two ways:
  _ _      ___
 | | |    |___|
 |_|_| or |___|

To find number of ways of longer walkways, you have to realize that 
the smallest "units" you can add are
    _          ___
1. | |     2. |___|
   |_|        |___|

By these units the pavement becomes 1 ft or 2 ft longer respectively.

To get a pavement of 3 ft by 2 ft you have to add to a 2 ft by 2 ft 
pavement unit (1), or to a 1 ft by 2 ft pavement unit (2). So the
number of ways to make a pavement for a N=3 is the sum of the numbers
of ways for N=1 and N=2. Similarly for N=4 the number of ways is the
sum of the numbers of ways for N=2 and N=3.

See the relation with Fibonacci's sequence?

If you have more questions, just write back.

Best regards,

- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/