Posts tagged as:

Fibonacci

Connecting Fibonacci and geometric sequences

by John on May 11, 2009

Here’s a quick demonstration of a connection between the Fibonacci sequence and geometric sequences.

The famous Fibonacci sequence starts out 1, 1, 2, 3, 5, 8, 13 … The first two terms are both 1, then each subsequent terms is the sum of the two preceding terms.

A generalized Fibonacci sequence can start with any two numbers and then apply the rule that subsequent terms are defined as the sum of their two predecessors. For example, if we start with 3 and 4, we get the sequence 3, 4, 7, 11, 18, 29, …

Let φ be the golden ratio, the positive solution to the equation 1 + x = x2. Let φ’ be the conjugate golden ratio, the negative solution to the same quadratic equation. Then φ = (1 + √ 5)/2 and φ’ = (1 – √ 5)/2.

Now let’s look at a generalized Fibonacci sequence starting with 1 and φ. Then our terms are 1, φ, 1 + φ, 1 + 2φ, 2 + 3φ, 3 + 5φ, … Let’s see whether we can simplify this sequence.

Now 1 + φ = φ2 because of the quadratic equation φ satisfies. That tells us the third term equals φ2. So our series starts out 1, φ, φ2. This is looking like a geometric sequence. Could the fourth term be φ3? In fact, it is. Since the fourth term is the sum of the second and third terms, it equals φ +φ2 = φ(1 + φ) = φ(φ2) = φ3. You can continue this line of reasoning to prove that the generalized Fibonacci sequence starting with 1 and φ is in fact the geometric sequence 1, φ, φ2, φ3, …

Now start a generalized Fibonacci sequence with φ’. Because φ’ is also a solution to 1 + x = x2, it follows that the sequence 1, φ’, 1 + φ’, 1 + 2φ’, 2 + 3φ’, … equals the geometric sequence 1, φ’, (φ’)2, (φ’)3, …

Related posts:

Honey bee genealogy (elementary)
Fibonacci numbers at work (advanced)

{ 4 comments }

Fibonacci numbers at work

by John on April 23, 2008

Today I needed to use Fibonacci numbers to solve a problem at work. Fibonacci numbers are great fun, but I don’t recall needing them in an applied problem before.

I needed to compute a series of integrals of the form

f(x, y) = xa (1-x)b yc (1-y)d p(x, y)

over the unit square for a statistical application. The function p(x, y) is a little complicated but its specific form is not important here. If the constants a, b, c, and d are all positive, as they usually are in my application, the integrand can be extended to a continuous periodic function in the plane. Lattice rules are efficient for such integration problems, and the optimal lattice rules for two-variable integration are given by Fibonacci lattice rules.

If Fk is the kth Fibonacci number and {x} is the remainder when subtracting off the greatest integer less than x, the kth Fibonacci lattice rule approximates the integral of f by

Fibonacci lattice integration rule

This rule worked well. I compared the results to those using the two-variable trapezoid rule and the lattice rule always gave more accuracy for the same number of integration points. (Normally the trapezoid rule is not very efficient. However, it can be surprisingly efficient for periodic integrands. See point #2 here. But the Fibonacci lattice rule was even more efficient.)

To implement this integration rule, I first had to write a function to compute Fibonacci numbers. This is such a common academic exercise that it is almost a cliché. I was surprised to have a practical need for such a function. My implementation was

    int Fibonacci(int k)
    {
        double phi = 0.5*(1.0 + sqrt(5.0));
        return int( pow(phi, k)/sqrt(5.0) + 0.5 );
    }

The reason this works is that

equation for Fibonacci numbers

where

definition of phi, golden ratio

is the golden ratio. The second term in the formula for Fk is smaller than 1, and Fk is an integer, so by rounding the first term to the nearest integer we get the exact result. Adding 0.5 before casting the result to an integer causes the result to be rounded to the nearest integer.

If you’re interested in technical details of the numerical integration method, see Lattice Methods for Multiple Integration by I. H. Sloan and S. Joe.

{ 9 comments }

Honeybee genealogy

by John on February 15, 2008

Male honeybees are born from unfertilized eggs. Female honeybees are born from fertilized eggs. Therefore males have only a mother, but females have both a mother and a father.

Take a male honeybee and graph his ancestors. Let B(n) be the number of bees at the nth level of the family tree. At the first level of the tree is our male honeybee all by himself, so B(1) = 1. At the next level of our tree is his mother, all by herself, so B(2) = 1.

Pick one of the bees at level n of the tree. If this bee is male, he has a mother at level n+1, and a grandmother and grandfather at level n+2. If this bee is female, she has a mother and father at level n+1, and one grandfather and two grandmothers at level n+2. In either case, the number of grandparents is one more than the number of parents. Therefore B(n) + B(n+1) = B(n+2).

To summarize, B(1) = B(2) = 1, and B(n) + B(n+1) = B(n+2). These are the initial conditions and recurrence relation that define the Fibonacci numbers. Therefore the number of bees at level n of the tree equals F(n), the nth Fibonacci number.

This is a more realistic demonstration of Fibonacci numbers in nature than the oft-repeated rabbit problem.

{ 5 comments }