# Ivars Peterson's MathTrek

September 30, 2002

## Stepping Beyond Fibonacci Numbers

Trying variants of a simple mathematical rule that yields interesting results can lead to additional discoveries and curiosities.

The numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55 belong to a famous sequence named for the Italian mathematician Fibonacci, who lived more than 700 years ago. Each consecutive number is the sum of the two numbers that precede it.

Suppose the first two numbers are instead 2 and 1. Applying the same addition rule produces a new sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, and so on. This string of numbers is the Lucas sequence, honoring the 19th-century French mathematician Édouard Lucas (1842–1891), who studied the Fibonacci sequence (and gave it its name). Lucas worked out what would happen if you started with any two whole numbers, then followed the Fibonacci rule.

Lucas discovered many interesting new sequences and patterns. For example, the ratio of any consecutive pair of numbers in the Fibonacci sequence is approximately the golden ratio (about 1.618. . .). As the numbers in the sequence get larger, the ratios of consecutive numbers get closer to the golden ratio. Remarkably, the ratio of successive Lucas numbers also converges to the golden ratio. Indeed, you can start such a Fibonacci-like sequence with any pair of numbers and still find that the golden ratio is the limiting value.

Another intriguing possibility is the sequence of numbers that arises when each consecutive number is the sum of the three numbers that precede it. Starting with 0, 0, and 1, the terms that follow are 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, and so on. As a generalization of the Fibonacci numbers, these are called tribonacci numbers.

Just as the Fibonacci sequence is connected with a constant (the golden ratio), the ratios of consecutive numbers in the tribonacci sequence tend to 1.83929. . . .This ratio is one of the roots of the equation x4 – 2x3 + 1 = 0.

You can easily generalize Fibonacci numbers to those that arise when each consecutive number is the sum of the four numbers that precede it. Ergo, tetranacci numbers: 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, and so on. In this case, the ratios of consecutive numbers tend to the constant 1.92756. . . .

Proceeding in a similar fashion, you can also generate sequences of pentanacci numbers, hexanacci numbers, and so on. Interestingly, as the number of added terms for generating a Fibonacci-like sequence increases, the constant that arises from taking the ratios of consecutive terms gets closer and closer to 2.

Fibonacci numbers come up in all sorts of contexts, both natural and mathematical. What about tribonacci numbers and their kin, sometimes called Fibonacci n-step numbers? One calculation that involves Fibonacci n-step numbers gives the probability that no runs of k consecutive tails will occur in N coin tosses. So tribonacci numbers come up when you're wondering about probabilities involving runs of three consecutive tails.

What about introducing an element of randomness into the rule for the Fibonacci sequence? In 1999, Divakar Viswanath studied what happens to Fibonacci numbers if, instead of always adding two terms, you can either add or subtract, as determined by the toss of a coin.

Here's one way to proceed: Start with the numbers 1 and 1, as in the original Fibonacci sequence. To get the next term, flip a coin to decide whether to add the last two terms or subtract the last term from the previous term.

Suppose that heads means add and tails means subtract. Tossing heads would result in adding 1 to 1 to get 2, and tossing tails would lead to subtracting 1 from 1 to get 0. According to this scheme, the successive coin tosses H H T T T H, for example, would generate the sequence 1, 1, 2, 3, –1, 4, –5, –1.

Infinitely many sequences result from Viswanath's rule. A few have special characteristics. If the coin always comes up heads, for instance, the result is the original Fibonacci sequence. Other strings of coin tosses can produce a repeating pattern, such as 1, 1, 0, 1, 1, 0, 1, 1, 0, and so on. Nonetheless, such special cases are sufficiently rare among all possible sequences that mathematicians ignore them.

By examining typical random Fibonacci sequences based on coin tosses, Viswanath uncovered a similar pattern. He ignored the minus signs, thereby taking the absolute value of the terms. He found that, roughly speaking, the ratio of consecutive terms tend to the constant 1.13198824. . . . In fact, the higher the terms, the closer the ratio gets to 1.13198824. . . .

Indeed, despite the element of chance and the resulting large fluctuations in value that characterize a random Fibonacci sequence, the absolute values of the numbers, on average, increase at a well-defined exponential rate. It's not obvious that this should happen. Random Fibonacci sequences might have leveled off to a constant absolute value because of the subtractions, for example, but they actually escalate exponentially.

Such unexpected discoveries help explain the mathematical allure of the Fibonacci numbers and their countless variants.

References:

Catalani, M. Preprint. On the roots of the cubic defining the tribonacci sequences. Available at http://xxx.lanl.gov/abs/math.CO/0209265.

______. Preprint. Identifies for tribonacci-related sequences. Available at http://xxx.lanl.gov/abs/math.CO/0209179.

Embree, M., and L.N. Trefethen. 1999. Growth and decay of random Fibonacci sequences. Proceedings of the Royal Society London A 455(July):2471-2485. Available at http://dx.doi.org/10.1098/rspa.1999.0412.

Hayes, B. 1999. The vibonacci numbers. American Scientist 87(July-August):296-301. Available at http://www.americanscientist.org/issues/comsci99/compsci1999-07.html.

Peterson, I. 2002. Golden blossoms, pi flowers. MAA Online (Sept. 2).

______. 1999. Fibonacci at random. Science News 155(June 12):376. Available at http://www.sciencenews.org/sn_arc99/6_12_99/bob1.htm.

Viswanath, D. 2000. Random Fibonacci sequences and the number 1.13198824. . . . Mathematics of Computation 69:1131-1155. Abstract available at http://www.ams.org/journal-getitem?pii=S0025-5718-99-01145-X.

Information about Fibonacci numbers and their kin can be found at http://mathworld.wolfram.com/FibonacciNumber.html, http://mathworld.wolfram.com/Fibonaccin-StepNumber.html, http://mathworld.wolfram.com/TribonacciNumber.html, http://mathworld.wolfram.com/TetranacciNumber.html, and http://mathworld.wolfram.com/RandomFibonacciSequence.html.