The Generalised Fibonacci Sequence

Recently, when looking at means of approximating values for the Riemann zeta function, I discovered a remarkable connection between the function and the Fibonacci sequence.

To be more correct, the connection exists as between the zeta function and a generalised version of the Fibonacci sequence!

The famous constant phi (the golden ratio) - denoted as ϕ - arises as the real valued solution to the equation, x² – x – 1 = 0 with a value of 1.618033 (approx). 

Associated with this equation is the famed Fibonacci sequence which can be simply constructed through starting with the two digits 0 and 1 and then successively adding the last term in the sequence to the previous term (though 0 is then omitted from the subsequent sequence).

In more general terms, for the polynomial equation (of degree 2) i.e. x² + bx + c, to generate the unique sequence of numbers associated with that equation, we successively add – b to – c.
Therefore because  in the case of the Fibonacci equation b = – 1 and c =  – 1, we successively add
(– 1) *( – 1) times the last term in the sequence to ( – 1) * (– 1) times the previous term. In other words, one simply keeps adding the last term to the previous term in the sequence. 

So when we add 1 to 0 we get 1, which is the next term in the sequence. Then when we add this new last term to the preceding term we get 1 + 1 = 2 (which is the next term). Then when we add 2 to the previous term (i.e. 1) we get 3, then 3 to 2 we get 5 and so on!

So the Fibonacci sequence is given as:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….  

Then to approximate the real- valued solution i.e. phi (i.e. ϕ), we divide the last available term in the sequence by the preceding term (with the approximation steadily improving with higher terms).

Thus the 11th term here is 89 and the 12th term, 144. Then when we divide 144 by 89 we get 1.6179775 (which is already a good approximation to the true value i.e. 1.618033...).

However, the Fibonacci sequence can be then generalised for any number of terms.

Therefore the Fibonacci sequence (as popularly understood) relates to the 2-term case (i.e. where only two terms are added at a time).

In fact, the equation for this 2-term case can be written as

x² = x + 1 = 0.

The simpler 1-term case can then be written as

x = 1.

In other words if we start with 1 and consider just one term at a time we keep repeating the starting term.

So the unique numerical sequence associated with x = 1 (i.e. x – 1 = 0) is

1, 1, 1, 1, 1, 1, ......

And of course the ratio here remains unchanged as 1 (which represents the positive real-valued solution of the equation).

Then to generate the 3-term case (of the generalised Fibonacci equation) we obtain the positive real-valued solution of

x³  =  x² + x + 1  = 0 (i.e.  x³ –  x² – x  – 1 = 0).

In fact, the algebraic solutions for polynomial expressions of degree and 3 and 4 are quite difficult to obtain by formula.

However I attempted this some years ago and come up with the solution for x of:

 1/3 + {19/27 + (11/27)^1/2}^1/3 + {19/27 - (11/27)^1/2}^1/3

The 3-step generalisation of the Fibonacci numbers is generally referred to as the Tribonacci numbers.

To generate this sequence (as the unique number sequence of x³ –  x² – x  – 1 = 0), we start with

0, 0, 1 and then successively add the last term in the sequence to the two preceding terms.

In this way we generate the required sequence

1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, .....

Now again to approximate the positive real-valued solution (i.e. of x³ –  x² – x  – 1 = 0) we can divide the 12th (and last term provided here) by the 11th to get 504/274 = 1.839416....

This is already a very good approximation to the true value i.e. 1.839286...and again the value of the approximation will steadily improve when we use higher-order terms to compile the ratio.

The 4-step generalisation of the Fibonacci numbers is referred to as the Tetranacci numbers.

To generate this sequence (as the unique number sequence of x⁴ =  x³ +  x² + x  + 1 = 0 (i.e. x⁴ –  x³ –  x² – x – 1 = 0), we start with,

0, 0, 0, 1 and then successively add the last term in the sequence to the three preceding terms.

In this way we generate the required sequence,

 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773,....

Once again we can approximate the positive real valued solution to the equation through the ratio of the nth term divided by the previous term.

So 12th/11th term = 773/401 = 1.927680... (which approximates well to the true value 1.927561...)

In like manner we can go on to calculate 5-step (Pentanacci), 6-step (Hexanacci), 7-step (Heptanacci) 8-step (Octanacci), 9-step (Nonacci) and so on, without limit.

In general terms, these all represent the solutions of  xⁿ =  x^{n – 1} +  x^{n – 2} + .... + 1 = 0 for n = 1, 2, 3, 4, ....

The 5-step sequence is:

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, ... with the positive real-valued solution to the corresponding equation, 1.965948...

The 6-step sequence is:

 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976,..... with its positive real-valued solution, 1.983585...

The 7-step sequence is:

 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004,.... with its positive real-valued solution, 1.991966...

The 8-term sequence is:

0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028.... with its positive real-valued solution, 1.99603...

The 9-term sequence is:

0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021,... with its positive real-valued solution, 1.99803... 

We will show how these values can be used to closely approximate values of ζ(s) where s > 1 in the next blog entry.