Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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/
```
Associated Topics:
Elementary Golden Ratio/Fibonacci Sequence
Elementary Word Problems
Middle School Word Problems

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search