Information on Fibonacci Sequences

In how many ways can you climb a flight of stairs if you can move either one or two steps forward at any point? If there are 4 steps to climb, you could take 4 single steps, or you might take a double step and two single steps. The diagram below shows all 5 ways in which this can be done. An X on a step indicates that it is stepped on.

There is a very simple way to answer this question in general if you break the problem into parts by considering the very last step taken. The last step is made by either taking a single step or a double step. The number of ways to climb a set of stairs when the last step taken is a single step is simply the number of ways to climb a set of stairs with one less step. In the example above, there are three cases where the last step is single because there are three ways to climb a set of stairs with 3 steps. Likewise, the number of ways to climb a set of stairs when the last step taken is a double step is just the number of ways to climb a set of stairs with two less steps. In the diagram above, there are two cases where the last step is double. We could break this diagram down as follows.

We are now left with 2 smaller versions of the same problem. In the same way that has been shown above, both of those can be split up into two problems. This way of breaking up a problem into smaller versions of itself is called recursion. More specifically, the problem of counting stair steps can be solved recursively by computing the Fibonacci sequence.

The Fibonacci sequence is a recursive sequence where the first two values are 1 and each successive term is obtained by adding together the two previous terms. Thus, the sequence begins 1, 1, 2, 3, 5, 8, ... That is, 1 + 1 = 2, then 1 + 2 = 3, then 2 + 3 = 5, etc.

If we denote the $n$th term of the Fibonacci sequence as $f$_n, then we can describe it by the recursive formula $f$₁ = 1, $f$₂ = 1, $f$_n = f_{n - 1} + f_{n - 2}. This is such a simple rule that Fibonacci numbers occur in a wide variety of situations. The problem they were originally used to solve was that of counting rabbit populations (see History section).

In AMOF, Fibonacci sequences are given in terms of 0-1 strings of numbers where two 1's cannot occur together. Any such string can be constructed from a smaller 0-1 string that has the same property by either placing a 01 at the end of a valid string two items shorter or by placing a 0 at the end of a valid string one item shorter. AMOF can also show the results in terms of single and double stair steps, displayed as strings of 1's and 2's.

Example

A few examples have been given above. Another problem modelled by Fibonacci sequences involves 2 panes of glass placed back-to-back and a ray of light. When a ray of light passes through the pair of panes, it will pass into the first pane, but then it might reflect at the point where the panes meet or pass through that point. After reflecting, it may reflect again at a different point. In how many ways can such a beam be reflected $n$ times? The following diagram produced by AMOF shows the reflections produced for the 0-1 string 001010.

Notice that each 0 corresponds to a reflection from an outer boundary of a pane, and each 1 corresponds to a reflection at the meeting of the panes.

As a second example, here is the output that AMOF produces for $n$ = 4 when all the ouput options are activated.

Bitstrings	Stair-steps	Pane Reflections
0 0 0 0	1 1 1 1 1
0 0 0 1	1 1 1 2
0 0 1 0	1 1 2 1
0 1 0 0	1 2 1 1
0 1 0 1	1 2 2
1 0 0 0	2 1 1 1
1 0 0 1	2 1 2
1 0 1 0	2 2 1

A Brief History

Applications to Mathematics and other Areas

The Fibonacci and Lucas numbers appear in numerous mathematical problems. In fact, there is an entire journal dedicated to such topics. Fibonacci Quarterly is a mathematical periodical devoted entirely to the subject of mathematics related to Fibonacci sequences. It covers topics involving many branches of mathematics, including linear algebra and probability.

In computer science, there is a data structure called a Fibonacci heap which is at the heart of many fast algorithms which manipulate graphs.

The Fibonacci numbers appear in nature as well. The study of Phyllotaxis, or leaf arrangements, has made this evident. The arrangements of structures like florets, leaves and flowers, seem to have two systems of spirals. The number of clockwise spirals is usually different from the number of counterclockwise spirals. In fact, these two numbers are usually two consecutive values of the Fibonacci sequence.

For example, the florets in the head of a sunflower appear to have two systems of spirals, both beginning from the center. Counting these spirals on one particular sunflower shows that there are 55 in the clockwise direction and 34 in the counterclockwise. Other plants which exhibit similar structure include pineapples, daisies, cauliflowers, pinecones, ocotilloes, Joshua trees and some cacti, such as the species Opuntia.

The reason why this pattern occurs in nature has to do with what happens when buds initially appear on these structures. Each bud that appears repels others around it. As new buds form, they repel the most recent buds more strongly, while buds that have been formed longer are repelled less. This naturally gives rise to a spiral pattern. Whether the buds eventually become seeds, twigs, petals, or leaves, the principle is the same.

The Fibonacci sequence also arises in the ancestry of male bees. A male bee (known as a drone) hatches from an unfertilized egg, while a female bee (known as a queen) hatches from a fertilized one. The following tree depicts the ancestry of a male bee in terms of how many ancestors it had of each sex. The number of bees in each row is a number in the Fibonacci sequence.

In the above diagram, if you count the number of male bees or female bees in any row, they are also Fibonacci numbers.

The Fibonacci numbers have been found in many other areas as well. In the area of physics, there are indications that the golden ratio and Fibonacci numbers are related to the structure of atoms and also to the spacing of planets in the solar system. Also, the golden ratio is found in Greek and Minoan architecture.

Explanation of AMOF Implementation

AMOF accepts only one input, n. This represents the nth Fibonacci number.

For output, there are three options:

• 0-1 Strings
• Stair stepping
• Pane Reflections

Choosing 0-1 Strings will produce all the length n bitstrings that do not contain consecutive 1's.

Choosing Stair stepping will produce a series of 1's and 2's which represent the different ways to climb a set of $n\; +\; 1$ stairs. Each stair-stepping result corresponds to a 0-1 string.

Choosing Pane Reflections will produce a series of Reflection diagrams corresponding to the 0-1 strings as illustrated in the Example section above.

In the Classroom

Many activities can be used in the classroom to generate and investigate Fibonacci sequences. One is to have students place 1 and 2 cent stamps across the top of a postcard (facing with correct side up) in different arrangements to make up a certain postage amount. The number of different arrangements will be a Fibonacci number. Also, the example of climbing stairs by taking 1 or 2 steps at a time is a simple activity. Students can check their answers with AMOF.

An activity suggested for investigating number sequences is to have students draw out the difference between consecutive numbers in a sequence. They can then find patterns in these differences which allow them to determine how the sequence is constructed. If this activity is tried with the Fibonacci numbers, students will notice that the sequence of differences is the same as the original sequence itself. This can give them a clue to the recursive nature of the sequence.

Explain the rabbit problem to students and have them come up with the sequence up to a year. Then ask them to complete the sequence up to the second year. This comes to 161 392.

Bringing in pine or fir cones for students to inspect is a good way to demonstrate that Fibonacci sequences occur in nature. This should give students a sense that mathematics is part of their world and not just something they are made to learn in school.

For students who are familiar with Pascal's triangle, the following exercise will demonstrate the connection between Pascal's triangle and Fibonacci numbers. Write out Pascal's triangle so that the leftmost 1's of each row are lined up with each other. Draw diagonal lines through this triangle and add up the values on the diagonals. Notice that they are Fibonacci numbers.

The golden ratio can be investigated by having students calculate the ratio of consecutive Fibonacci numbers on a calculator. They will notice that this ratio tends to approximately 0.618.

For those in higher grades, discovery of functions and relations among Fibonacci and Lucas sequences might be useful. Items to explore include:

• $F$_nL_n = F_2n
• The sum of the squares of two consecutive Fibonacci numbers is a Fibonacci number. Specifically, $F$_n² + F_{n + 1}² = F_{2n + 1}
• $L$_n = F_{n + 1} + F_{n - 1}

By pursuing the following sequence of formulas, students may arrive at a formula for $F$_n² - F_{n + k}F _{n - k}

• $F$_n² - F_{n + 1}F_{n - 1} = (-1)^{n - 1}
• $F$_n² - F_{n + 2}F_{n - 2} = (-1)ⁿ
• $F$_n² - F_{n + 3}F_{n - 3} = 4(-1)^{n - 1}

There are several other ways to investigate Fibonacci sequences. One good reference for ideas is Readings for Enrichment in Secondary School Mathematics, a book produced by the NCTM.