COMPUTING SCIENCE

# The Vibonacci Numbers

# Breeding Like Rabbits

The Fibonacci numbers were introduced to the world 800 years ago by Leonardo of Pisa, who also made another major contribution to mathematics: It was he who brought Indo-Arabic numerals into European culture. "Fibonacci" was apparently Leonardo's nickname, a shortening of *Filius Bonacci*, or son of Bonacci. Of course Leonardo did not call his sequence the Fibonacci numbers; the name was popularized by the 19th-century French mathematician Edouard Lucas.

The whole matter began with a contrived problem about the breeding of rabbits. Suppose a pair of rabbits breeds once a month and always produces a single pair of offspring, which breeds the following month. Each pair breeds twice and then dies. Starting with a single pair of rabbits under these assumptions, how many pairs will be living after *n* months? The answer is *f(n)*.

Leonardo's fanciful problem is not of any great interest to population biologists, but the Fibonacci numbers are famous for turning up in many other contexts. Their patterns appear in seashells and sunflowers and pinecones; they count the ways of tiling a checkerboard with dominos; they are present in Pascal's Triangle if you know where to look for them. The Fibonacci numbers also played an essential role in the solution to Hilbert's Tenth Problem. They even have their own journal, the *Fibonacci Quarterly*, published since 1963.

One of the most important properties of the Fibonacci numbers was first noted in the 17th century by Johannes Kepler: The ratios of successive Fibonacci numbers, *f(n*–1)/*f(n*–2), form a new sequence, beginning 1, 2, 1.5, 1.666, . . . , 1.6, 1.625. This series converges on a value of 1.618033989 . . . , known as Φ, or the golden ratio. Over the years the golden ratio has acquired something of a cult following, which I would not want to encourage, and yet it truly is a remarkable number. It has the curious property that if you take its inverse (that is, 1/Φ) and then add 1, you recover the original number; in other words *f* is a solution to the equation 1/*x*=*x*–1. This equation can be rearranged as *x*^{2}–*x*–1=0, for which the quadratic formula gives the solutions (1+√5)/2 and (1–√5)/2. The first of these numbers is Φ; the second is 1–Φ, or –0.618033989....

Powers of Φ provide close approximations to the Fibonacci numbers. Since Φ is the limiting value of the ratio between successive Fibonacci numbers, multiplying any member of the series by Φ yields an approximation to the next member. Looking at the approximation process through the other end of the telescope, the *n*th root of the *n*th Fibonacci number approximates Φ. A more complex formula, (Φ^{n}–(1–Φ)^{n})/√5, gives the *exact* value of *f(n)*; this strange congeries of irrationals always reduces to an integer, as long as *n* itself is an integer.

The Fibonacci theme has many variations. Edouard Lucas, the mathematician who named the Fibonacci numbers, has a related series named after him: The Lucas numbers are defined by the same recurrence formula but start with the integers 2, 1 instead of 1, 1. The first few members of the Lucas series are 2, 1, 3, 4, 7, 11, 18, 29, 47, 76. Remarkably, the ratio of successive Lucas numbers also converges to Φ; indeed, it turns out that you can start a Fibonacci-like series with *any* pair of numbers, and the limit of the growth rate will always be Φ.

Another variation has come to be known as the Tribonacci series. Instead of adding the previous two terms at each step, you add the previous three. A convenient way to get such a sequence started is to pretend that the initial 1 is preceded by an indefinite list of 0s. With this convention, the Tribonacci sequence begins 1, 1, 2, 4, 7, 13, 24, 44, 81, 149. In this case the growth rate is not Φ; instead the ratio of successive terms approaches 1.83929 . . . . The analogous Tetrabonacci series, where each term is the sum of the previous four, begins 1, 1, 2, 4, 8, 15, 29, 108, and the ratio of terms converges to 1.92756 . . . . Clearly this process can be generalized to *k*-bonacci series. You might want to think about what happens in the limiting case where each term is the sum of *all* the previous terms. (The answer is given below.)

EMAIL TO A FRIEND :

**Of Possible Interest**

**Spotlight**: Briefings

**Technologue**: Quantum Randomness

**Letters to the Editors**: Nautilus Biology