MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > July-August 1999 > Article Detail

COMPUTING SCIENCE

The Vibonacci Numbers

Brian Hayes

The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, . . . are one of the royal families of mathematics. Like other royalty, they have an ancient pedigree, everybody knows all about them, and no one takes them very seriously anymore. The Fibonaccis and their relations have been thoroughly studied for centuries, so no one would expect much in the way of novelty or innovation to turn up among them. Nevertheless, a whole new branch of the family has just sprouted up. What's more, the new cousins are a highly erratic bunch—sports in the royal lineage.

The pattern in the sequence of Fibonacci numbers is easy to see: Each term (except for the first two) is the sum of the two preceding terms. Expressed as a formula: f(n)=f(n–2)+f(n–1). The new variation on the series changes this formula in only one detail. Instead of always adding two terms to produce the next term, you either add or subtract, depending on the flip of a coin at each stage in the calculation. If the coin comes up heads, say, you add as usual, but if the result is tails, you subtract f(n–1) from f(n–2). In other words, the formula becomes f(n)=f(n–2)±f(n–1), where the symbol "±" signifies that you choose either addition or subtraction randomly and with equal probability.

Here are a few short sequences generated by this random sum-or-difference algorithm:

1, 1, 0, 1, –1, 2, –3, –1, –2, 1, –3, 4, 1, 3, 4, 7, 11
1, 1, 2, –1, 3, 2, 1, 1, 0, 1, –1, 0, –1, 1, –2, –1, –1
1, 1, 2, –1, 3, 2, 1, 3, –2, 1, –3, –2, –5, 3, –8, –5, –13
1, 1, 0, 1, –1, 0, –1, 1, –2, 3, 1, 2, –1, 3, –4, 7, –11
1, 1, 0, 1, 1, 2, 3, 5, –2, 7, 5, 12, –7, 19, –26, 45, 19

Certain properties of the Fibonacci sequence continue to show through here, most notably the alternation of two odds and an even in all the series. But the steady growth of the Fibonacci numbers is replaced by fluctuations of increasing amplitude. The way the numbers seem to vibrate between negative and positive values leads me to suggest the name Vibonacci series; I shall designate them by the symbol v(n).

Looking at the fluctuations, you might conclude that the randomness in the formula has wiped out all traces of order. And it is certainly true that the Vibonacci sequence is nondeterministic. Unlike the conventional Fibonacci numbers, where the nth term has a single, definite value that needs to be calculated only once, the nth term of a Vibonacci series has a distribution of possible values; v(n) is likely to be different every time you compute it. Nevertheless, a great deal of order persists in the randomized sequences. In particular, the absolute value of v(n) grows exponentially as n increases. You can measure the growth rate in simple computer experiments. What's more remarkable, the value of the number that determines the growth rate has been pinned down in a mathematical proof.





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Letters to the Editors: Nautilus Biology

Technologue: The Quest for Randomness

Feature Article: Twisted Math and Beautiful Geometry

Subscribe to American Scientist