Exploring the Fibonacci Sequence

(Using the spreadsheet in Mathematics Explorations)

by Hwa Young Lee

In this assignment, we are going to explore the following question using the spreadsheet.

There is a stairway and you can either take one step or two steps at a time.

In how many ways can you walk up the stairway if it had 5 steps? 10 steps?

More generally, in how many ways f(n) can you walk up the stairway if it had n steps?

Also, what is the value of ?

1) Find f(n)

When there are no steps, let's say there is only one way, to go nowhere. So, f(0)=1.

When there is one stair to go, there is only one way to go up the stairway. So, f(1)=1 :

With two stairs to go, we can go up two steps at once or we can go up one stair and be on stair number 1, which leaves us to walk up the remaining one step as in f(1).

So, f(2)=1+f(1)=2 :

When there are n stairs left to go, we can either go up one stair from the (n-1)th stair or we can go up two stairs at once from the (n-2)th stair.

So, f(n)=f(n-1)+f(n-2) :

Thus, f(n)=f(n-1)+f(n-2), with , f(0)=1, and f(1)=1.

Then f(3)=f(2)+f(1)=3, f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8.

So, there are 8 ways to walk up the stairway with 5 steps.

We can notice that f(n) forms the Fibonacci sequence, and find other values for n using a spreadsheet.

* A special note: Did I calculate for each term? No. For those who are wondering how I got the table, if you type in the first few terms in the sequence, then select the terms and drag down along the list, the spreadsheet will do the rest for you! Isn't that neat?! This shows us how the spreadsheet can be helpful.

From the spreadsheet, we can find that there are 89 ways to walk up the stairway with 10 steps.

2) Find the ratio of each pair of adjacent terms in the Fibonacci sequence. What happens as n increases? In other words, what is ?

Again, we use the spreadsheet to get an idea :

 

Hmm...It seems like it's getting close to a particular value.

Try opening the spreadsheet and increase the number of n.

(*If you click on the last cell of each column, there appears a small +. Drag down that + and you can easily increase the number of n's.) 

Actually, we can find this particular value by solving for :

Since f(n)=f(n-1)+f(n-2), f(n-1)=f(n)-f(n-2),

Then

Let and use the fact that .

Then we can rewrite (*) as

Multiplying both sides by x, we obtain

If we solve the quadratic equation, .

Since x>0, and thus

This shows us that the ratio of each pair of adjacent terms in the Fibonacci sequence converges to the golden ratio as n increases! 

3) Now let's play around with the numbers a little.

Explore sequences where f(0) and f(1) are some arbitrary integers other than 1. (Open spreadsheet)

When f(0)=1 and f(1)=3, we have the following spreadsheet:

The sequence is called a Lucas Sequence. 

You may notice that the ratio of successive terms did not change.

Actually, all such sequences with different starting terms have the same limit of the ratio of successive terms.

This is easily seen in the process shown above of how we found the value of .

The first terms of the sequence does not affect the result!