Fibonacci and Possible TilingsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/