Fibonacci

Inverse Fibonacci numbers

Posted on by John

As with the previous post, this post is a spinoff of a blog post by Brian Hayes. He considers the problem of determining whether a number n is a Fibonacci number and links to a paper by Gessel that gives a very simple solution: A positive integer n is a Fibonacci number if and only if either 5n2 − 4 or 5n2 + 4 is a perfect square.

If we know n is a Fibonacci number, how can we tell which one it is? That is, if n = Fm, how can we find m?

For large m, Fm is approximately φm / √ 5 and the error decreases exponentially with m. By taking logs, we can solve for m and round the result to the nearest integer.

We can illustrate this with SymPy. First, let’s get a Fibonacci number.

      >>> from sympy import *
      >>> F = fibonacci(100)
      >>> F
      354224848179261915075

Now let’s forget that we know F is a Fibonacci number and test whether it is one.

      >>> sqrt(5*F**2 - 4)
      sqrt(627376215338105766356982006981782561278121)

Apparently 5F2 – 4 is not a perfect square. Now let’s try 5F2 + 4.

      >>> sqrt(5*F**2 + 4)
      792070839848372253127

Bingo! Now that we know it’s a Fibonacci number, which one is it?

      >>> N((0.5*log(5) + log(F))/log(GoldenRatio), 10)
      100.0000000

So F must be the 100th Fibonacci number.

It looks like our approximation gave an exact result, but if we ask for more precision we see that it did not.

      >>> N((0.5*log(5) + log(F))/log(GoldenRatio), 50)
      99.999999999999999999999999999999999999999996687654

Related posts

Fibonacci number system

Posted on by John

Every positive integer can be written as the sum of distinct Fibonacci numbers. For example, 10 = 8 + 2, the sum of the fifth Fibonacci number and the second.

This decomposition is unique if you impose the extra requirement that consecutive Fibonacci numbers are not allowed. [1] It’s easy to see that the rule against consecutive Fibonacci numbers is necessary for uniqueness. It’s not as easy to see that the rule is sufficient.

Every Fibonacci number is itself the sum of two consecutive Fibonacci numbers—that’s how they’re defined—so clearly there are at least two ways to write a Fibonacci number as the sum of Fibonacci numbers, either just itself or its two predecessors. In the example above, 8 = 5 + 3 and so you could write 10 as 5 + 3 + 2.

The nth Fibonacci number is approximately φn/√5 where φ = 1.618… is the golden ratio. So you could think of a Fibonacci sum representation for x as roughly a base φ representation for √5x.

You can find the Fibonacci representation of a number x using a greedy algorithm: Subtract the largest Fibonacci number from x that you can, then subtract the largest Fibonacci number you can from the remainder, etc.

Programming exercise: How would you implement a function that finds the largest Fibonacci number less than or equal to its input? Once you have this it’s easy to write a program to find Fibonacci representations.

* * *

[1] This is known as Zeckendorf’s theorem, published by E. Zeckendorf in 1972. However, C. G. Lekkerkerker had published the same result 20 years earlier.

Connecting Fibonacci and geometric sequences

Posted on by John

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, …

More Fibonacci posts

Fibonacci numbers at work

Posted on by John

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) = x^a (1-x)^b y^c (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

\frac{1}{F_n} \sum_{j=0}^{F_n-1} f\left( \left\{ \frac{j}{F_k}\right\}, \left\{\frac{jF_{n-1}}{F_n}\right\} \right)

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.

Honeybee genealogy

Posted on by John

honeybee

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.