Fibonacci Findings

Whoever wants to understand much must play much. –Gottfried Benn

This post has been a long time coming. For almost a month, my spare time has been filled by the brainstorming and experimentation that would become this post. It is probably the least organized post I have composed, yet it is also the most mathematically rigorous. What follows are several interrelated proofs annotated with the motivations for them and the logic behind them. This is a log of my mathematical play, and as such it is the closest this site has yet come to being a blog proper. The mathematics in this post can become dense and requires a good knowledge of algebra for full appreciation, however I have endeavored to explain things fully and have included full derivations that would normally be left absent in mathematical papers due to triviality. Feel free to ask me for clarification or enhancement on anything in this post.

The impetus for this stems from a result I found surprising while preparing the post that became Zombi(Nacci). In that post I investigate the rate of growth of a zombie population and find that it follows the Fibonacci sequence. This was not a result I knew beforehand. When creating the thought experiment and meditating on it, I was surprised to find the Fibonacci sequence naturally emerge from it. There is a peculiar joy to arriving at such a famous and simple solution unexpectedly, and it fueled my curiosity about the Fibonacci sequence and its properties. As such, my free time has been spent in its investigation.

The sequence is widely known even outside of scientific and mathematical circles, for, as a friend put it, it is simple and easily understood. It is. For reference here is its definition (this post relies heavily on mathematical symbols, and rather than struggle with the html to format them correctly, I have instead prepared images whenever they are necessary):

The final line states symbolically that each term of the Fibonacci sequence is the sum of the preceding two terms. The first ten terms are: 0,1,1,2,3,5,8,13,21,34. As stated, the first two values, 0 and 1, are called seed values and govern all the terms to come. You can apply the recurrence equation to any pair of seed values and arrive at a variety of different sequences. For instance, if the seed values are 1 and 3, you arrive at the Lucas Numbers named after the French mathematician Édouard Lucas. The first ten Lucas Numbers are 1, 3, 4, 7, 11, 18, 29, 47, 76, 123.

Interestingly, you can also use the definition to extend the sequence backwards, that is to extend it to negative terms. To do this you begin with the second Fibonacci number, 1, and ask yourself the question: “What number would I add to the preceding Fibonacci number, 0, to obtain the current number, 1?” Of course, the answer is 1; 0+1=1. Then you repeat the question, this time with 0: “What number would I add to the preceding Fibonacci number, 1, to obtain the current number, 0?” This time the answer is -1. Once again you attempt to answer the question: “What number would I add to the preceding Fibonacci number, -1, to obtain the current number 1?” The answer is of course, 2. So far the extended sequence looks like this …2,-1,1,0,1,1,2… Notice that it appears that the sequence is identical with the positive sequence except that its terms have alternating signs. This is indeed the case.  These are often called the negaFibonacci numbers. The first ten negaFibonacci numbers are: 34,-21,13,-8,5,-3,2,-1,1,0.

For the remainder of this essay, we will be confined to the non-negative Fibonacci numbers, however the negaFibonaccis are an interesting extension of the sequence and I would be remiss not to mention them.

The next part of my investigation was to compare proceeding pairs of Fibonacci numbers. That is, to compare the current number to the previous number. I wanted to see if the numbers would eventually differ from one another by a common factor. To do this I divided each Fibonacci number by the previous number for fifty terms. Here are my results:

As you can see, the number 1.61803389 quickly emerges as the common quotient, but is it exact, and is it significant? What I’m attempting to do is find out if F(n)/F(n-1) is equal to some constant number for extremely large ns. Mathematically speaking this is known as looking for the “limit” of the sequence. If a mathematical statement has a limit, it means that as the terms become arbitrarily large the relationship tends towards a constant value. In the case of the Fibonacci numbers that value appears to be 1.61803389, but the evidence given by the preceding chart is insufficient to declare a mathematical truth. All evidence is circumstantial in mathematics and something is only true if it can be proven. To that end, I attempted to derive the limit of F(n)/F(n-1). To accomplish this, I first assumed that the limit did exist (sometimes they do not), and called it L. Note that limit is abbreviated lim, and that if the limit exists, then it is the same for F(n)/F(n-1) as it is for F(n-1)/F(n-2), that is limF(n)/F(n-1)=limF(n-1)/F(n-2)=L. Here then, is my derivation:

That final statement, (1±√5)/2, indicates two values. One value is (1+√5)/2, which is approximately the value we found before, 1.6180339… The other value is (1-√5)/2≈-0.6180339… Interestingly, (1-√5)/2=1-(1+√5)/2. However, more interesting is the fact that this is the answer to a well-known mathematical problem, that of the Golden Mean. The definition and derivation of the Golden Mean follow. Notice that the derivation is similar to the derivation of the Fibonacci limit:

The result obtained is often split into two ratios, the positive one being called the Golden Ratio, and often represented by the Greek letter phi(φ). Here are the explicit definitions and approximations for φ and 1- φ:

This establishes a relationship between the Fibonacci sequence and the Golden Ratio. It indicates that given any Fibonacci number, you can approximate the next Fibonacci number by multiplying the current one by (1+√5)/2, that is F(n+1)≈φF(n). Leonardo of Pisa discussed the  Fibonacci sequence in relation to rabbit populations, and the ancient Greeks found the Golden Ratio fascinating due to its frequent occurrence in geometry; it is amazing that two pursuits so different from each other can have such an intimate connection. Math is full of these connections, and their presence and meaning are constantly fascinating to me. In this case, the connection goes even deeper.

The Golden Ratio has an interesting property: Its square is only one more than itself. Symbolically, φ^2=φ+1.  This is a direct result of its derivation, however it can also be arrived at by squaring (1+√5)/2:

This property indicates that any power may be expressed in terms of an integer multiple of φ. Examining successively larger powers, a pattern emerges:

The numbers at the bottom of each column are the coefficient of (number in front of) φ and the number being added to it, respectively. I set them aside to draw attention to them. Notice the progression of φ’s coefficients, 2,3,5, and the second terms, 1,2,3. They are both Fibonacci numbers. The number being added to the multiple of φ is one Fibonacci number behind the number being multiplied by φ. In general it seems that the pattern is this: φ^n=F(n) φ+F(n-1). As with the limit of the Fibonacci numbers, the results found in these trials are not conclusive and our conjecture that φ^n=F(n) φ+F(n-1) requires a proof. Unfortunately, this proof requires methods that are more complex than the direct algebraic derivation of the previous proof. The proof I found relies on a proof strategy called mathematical induction, and to understand its success, you must first be introduced to this method.

Mathematical induction is a powerful proof strategy. Despite its name, it has no relationship to inductive reasoning, which is not considered rigorous in mathematics-mathematics striving to be a totally deductive discipline. Mathematical induction is often used to show that a given statement is true for all natural numbers (non-negative integers), and since we are dealing with the non-negative Fibonacci numbers it is perfect for our case. It can be intuitively understood like this: If it can be shown that a given statement is true for the simplest case and that if it is true for one number, it must be true for the following number, then you have proven it to be true for all natural numbers. Dominoes are often used as a metaphor for mathematical induction. You set up the first domino, and explain how if it topples, it will cause every successive domino to fall.

Mathematical induction can be split into three sections. The first section, The Basis Step, shows that the relation holds for the number. The next step, The Induction Hypothesis, is to assume that the relationship is true for an arbitrary number k. The final section, The Inductive Step, is to show that if the relationship holds for k, then it must hold for k+1. However, mathematical induction is probably best understood through example. Here is a simple proof using mathematical induction. The statement being proven is this: The square of an odd number is always odd. Notice that an odd number is always one more than an even number and therefor can be written as 2n+1. Using this notation, the conjecture is (2n+1)^2=2m+1. Here is the proof:

The Square of an Odd Number is Odd

The small square at the end is known as a mathematician’s tombstone, or, less romantically, a Halmos symbol named after the amazingly prolific mathematician Paul Halmos who popularized its usage. It is used to indicate the end of a proof as are the initials QED that stand for Quod Erat Demonstrandum, which is Latin for “what was to be demonstrated.”

Using induction, we can prove the conjecture made before, φ^n=F(n) φ+F(n-1):

Result 1

Notice that the final statement,  φ^(n+1)=F(n+1) φ+F(n) is exactly what we were looking for, because it is merely φ^n=F(n) φ+F(n-1) with 1 added to each n.  This proves another connection between the Golden Ratio and the Fibonacci numbers. However, we have neglected half of the Golden ration that is approximately, -0.6180339, 1- φ. Does this value have a connection to the Fibonacci numbers? Some experimentation reveals that it may:

Again, the coefficients of 1- φ and the numbers being added to it follow the Fibonacci sequence. The conjecture is this (1- φ)^n=F(n)(1- φ)+F(n-1). This relationship can also be proven by induction:

Result 2

I had previously seen a function relating the Fibonacci numbers to the Golden Ratio, and had not understood it. Upon proving these two relationships, however, I am now able to derive it. It is known as Binet’s Formula after the French mathematician, Jacques Philippe Marie Binet. What is remarkable about it is that it takes a discrete relationship, the Fibonacci sequence, and finds a continuous analogue. Informally, in mathematics discrete means that a mathematical structure has no “intermediary” values. For instance there is no one third Fibonacci number, or a 12.5 Fibonacci number etc. Continuous is the opposite. This entire post has been my derivation of Binet’s Formula, and what follows is the final piece. I’m certain that there are more efficient ways to do it, and that I’m probably not the first to derive it this way, but this was how I proved it and understood it:

It is extremely satisfying to finish a proof and write QED at the end. They rival fin for finality, and perhaps disenthrone it. With those letters I affirm that I have truly understood something, and I know that its truth will far outlive me. They are denouement.

As a final note, in the post, The Sum of All Fears, I included this graph:

Here I compare the growth rate of a zombie population to that of vampires and werewolves. I had found that zombies grew according to the Fibonacci numbers and that vampires grew exponentially. However, I faked the graph. At the time I didn’t know of a continuous way to represent the Fibonacci numbers and therefor couldn’t adequately compare their growth to that of an exponential function, so I merely drew a line at the time when zombies would surpass the human population. However with Binet’s formula this can be done. To illustrate the differences in growth, this comparison assumes that vampires feed at the same rate as zombies. That is, I compare Binet’s formula directly with 2^x. As you can see, 2^x increases much quicker than do the Fibonacci numbers.

Notice the slight undulation between the first and second Fibonacci numbers. I do not know what that means. Neither do I understand the significance of the intermediate values that Binet’s formula returns. Binet’s Formula also occasionally gives complex results because (1-√5)^x can be imaginary. This indicates a relationship between the Fibonacci numbers, the Golden Ratio and the imaginary number i. I don’t understand any of these things now, but I’m looking forward to finding them out. Thank you for joining me in these investigations. QED