I recently came across a fact about the Fibonacci sequence that I'd not encountered before. It goes something like:
If you do (something not quite trivial) to the Fibonacci sequence you get .
Now, I'm not the biggest fan of the Fibonacci sequence so my immediate reaction to this was to look for a more general picture to fit this into. I did see a proof of this fact, and it gave me the hint as to that wider story.
2 Geometric Series
The “something not quite trivial" was described as shifting each Fibonacci number down below the decimal point so that each one is one further down than the previous. Then adding them.
The result is .
A more mathematical description of this procedure is to sum the series . It makes the numbers work a little easier if we index our series starting at , and we start the Fibonacci sequence with and . With this convention, we're looking at the series:
Now the Fibonacci sequence is almost a geometric series with common ratio . More precisely, we have:
So we're summing:
Using the sum of a geometric series, we therefore get:
Now and so:
3 Generalising Fibonacci
The construction works with more sequences than just Fibonacci's. In this section we'll consider two variations. The first is to Lucas sequences. The second is to consider a sequence formed by adding three terms together.
First, let us consider Lucas sequences. These are defined by choosing integers and and applying the recursive relation:
We need to choose suitable starting terms, we'll take and .
Consider the quadratic and let and be its roots1. It turns out that the sequence can be written as:
1The analysis works fine if and are complex, but needs a little adjustment if there is a repeated root.
Now choose such that and . Consider the series
using the above expression for , this simplifies as follows:
Now and are the roots of the quadratic and so and . Thus:
Now let's take this up one level. Choose , , and and define the sequence by , , and
Let , , and be the roots of . Then there are , , and such that:
A bit of tedious simultaneous equation solving shows that:
Let be such that . Then:
Now the numerator of that horrendous-looking fraction simplifies considerably. When expanded out, all the terms with or cancel leaving only:
Multiplying out leads to exactly the same expression, resulting in:
We recognise the denominator as the polynomial , whence:
There seems to be a pattern emerging.
In the analysis of the cubic version we hid most of the algebra. So proving that the pattern continues looks like it might get quite tedious unless we can figure out a way to simplify it. Fortunately, there is a way to do so which involves making the series purely geometric rather than a sum of geometric series. We'll start back with the Fibonacci sequence.
The trick is to introduce matrices. Let:
so feeding in the Fibonacci sequence we get
thus putting we get .
Our sum is therefore closely related to the sum:
5 Spectral Theory
There was nothing particularly special about the particular matrix in the previous section. What we needed was for the sum to converge and that's to do with the relationship between and .
Let's generalise further. We have a matrix , a number , and a starting vector . We consider the sum:
The rule for this to converge is similar to the convergence of a geometric sum of numbers. We need the “size" of to be less than . 2
2Specifically, we need where is the operator norm.
For the Fibonacci matrix this is true providing so certainly qualifies.
When this is true, the same analysis as for ordinary geometric series gives:
The condition on means that is invertible and so
Putting in the extra factor of yields:
Looking at when the expression makes sense is the start of an area of Mathematics called Spectral Theory.
6 Back to Fibonacci
In the Fibonacci situation, the matrix is
which has inverse
The determinant is known as the characteristic polynomial of and is written . For the Fibonacci matrix, this is .
Putting in we get:
which is the source of the .
Applying this to the initial vector, we get
In terms of the summation, we have:
Equating terms gives
Putting in , we get:
This formula works providing . In particular, it works for any positive whole number at least . So if we did the same construction in a different base we could use the same analysis to figure out the sum.
In particular, we see that if we had worked in base we would have gotten the answer . That is,
The other slightly surprising thing is how many of these entries are prime. It does start dropping off after , though.
There is another way to look at the denominator which is to see that in base , we would write as:
where the subscript means that the representation is to be understood in base .
7 The General Case
The general case is to have a sequence defined by a rule:
and starting conditions , .
The associated matrix is
We're interested in , which is:
Although it appears that we want to invert , we actually only want to work out , where
which means that we want to solve the system
Normally we would solve this by Gaussian Elimination, but this system can be solved more directly since the first equations read:
and thus .
The final equation reads:
substituting in, we get:
Note that is the characteristic polynomial of .
Now the first component of is and so
Note that this is only valid if is bigger in magnitude than any of the roots of .
For a finale, let's try a triple Fibonacci where each term is the sum of the preceding three:
Starting at , , , the first terms of this sequence are:
The matrix in that case is:
and the characteristic polynomial of this is
Interestingly, this is valid for and for and we get: