Generalising the Fibonacci Series

This page takes a brief look at one of the ways that the Fibonacci series can been generalised. The Fibonacci series starts with 0 and 1 and the Lucas series with 2 and 1. On this page, the first we look at a generalisation that lets us choose any two starting values, called the G series (for Generalised Fibonacci series). We also find two particular ways that we can put every number into a collection of such series. In all aspects of the G series, it is the Fibonacci numbers themselves and the golden ratio Phi that again take the starring roles.

Contents of this page

The Things To Do icon means there is a Things To Do investigation at the end of the section.
The calculator icon means there is an interactive calculator in this section.

The G series

Two starting values

The first generalisation we shall look at is choosing two new starting numbers. The Fibonacci series, which here we will call the Fibonacci series, starts with 0 and 1 although 1 and 1 or even 1 and 2 will do just as well too. We have already looked in some detail at a series that chooses two different starting values - 2 and 1 - the Lucas series.
When we start with different values, we call the series a G series (for Generalised Fibonacci series). Once we have the first two values of a G series, the rest are formed using the Fibonacci Rule of adding the latest two to get the next one.

Here is a simple calculator to show you some terms of a General Fibonacci Series. Enter the values for a and b then click the Show button. Alter the number of terms the calculator produces if you like.

C A L C U L A T O R
the first terms of G(a,b) when a= b=

R E S U L T S
Infinity means the number has become too big for this calculator
We will use the letter G (for Generalised) for this series, which starts with values a and b, that is,
G(0) = a and G(1) = b
For all other values of n, that is n bigger than 1 or n negative, the Fibonacci Rule holds, that is:
G(n) = G(n – 1) + G(n – 2) ........ the Fibonacci Rule
When the starting values are just "a" and "b", we will use G for the series and G(i) for individual numbers in it.
If we are using several different G series, that is, with different starting values, then we will make clear which is which by writing G(a,b,i). We shall find a formula for G(a,b,i).

All G series are related to the Fibonacci series

All G series look like this:
i: 0123456...
G(a,b,i):a b a+b a+2b 2a+3b 3a+5b 5a+8b ... 
and, like the Fibonacci series itself, can be extended backwards too:
i: ...–3–2–1 0123456...
G(a,b,i): ...  –3a+2b  2a–b  –a+b   a  b  a+b  a+2b  2a+3b  3a+5b  5a+8b  ... 
We will now find a few simple rules that will help us understand the G series and show that they are all described by a simple relationship involving the Fibonacci series.

The Index Shift Rule

Here are some simple examples to see if you can spot some of the new series:
Seriesa=G(0)b=G(1)i=2i=3i=4i=5 i=6i=7i=8i=9
G(1,1,i)11235813 213455
G(1,2,i)1235813 21 345589
G(2,3,i)2358132134 5589144
G(1,0,i)101123581321
G(–1,1,i)–11011235813
OK, so those were easy! Each is the Fibonacci series but shifted along so that the starting point for the indices (when i=0) is not at the 0 Fibonacci number but somewhere else in the series:
G(1,1,i) is F(i+1)
G(1,2,i) is F(i+2)
G(2,3,i) is F(i+3)
G(1,0,i) is F(i–1)
G(–1,1,i) is F(i–2).

So starting with any two consecutive Fibonacci numbers as our choices for a and b, G(a,b,i) will be essentially the same as the Fibonacci series but with its indices changed. The general rule is:

G( F(k), F(k+1), i) = F(i+k) ........... (G1)
What we did with the Fibonacci series we can of course do to any G series.
i ...012...
G(a,b,i) ...aba+b...
which is the same series as G(b,a+b) but starting one place further along. So to make G(a,b) the same series as G(b,a+b) with the same index numbers we need to use i+1 instead of i:
G(b, a+b, i) = G(a,b,i+1)
If we had started the indices at the pair a+b, a+2b in the series G(a,b,i), we would have increased i by 2:
G(a+b, a+2b, i) = G( a, b, i+2)
The general result for altering the index numbers or shifting the series a few places along, making the index numbers start at a different place in the same series of numbers is as follows:
G( G(a,b,k), G(a,b,k+1), i) = G(a, b, i+k) .... the Index Shift Rule
Checking this, when we put a=0 and b=1 so that G(a,b,k) is F(k), we have
G(F(k), F(k+1), i) = F(i+k)
as we had already discovered above in (G1).

If we display each of these general terms of the G series in a column with the multiples of a in the top row and the b multiples underneath, we have:
n 01234567 ...n
a 10112358 ...F(n–1)
b 011235813 ...F(n)
Sum aba+ba+2b2a+3b3a+5b5a+8b 8a+13b...F(n–1)a+F(n)b
It is now clear that since we are adding a's and b's and each a and b term is the sum of the previous 2 - and we start from 0 and 1 at some point then we have Fibonacci multiples of a and b. (This result is easy to prove by mathematical induction.) So our first main result is:

G(a, b, n) = a F(n–1) + b F(n) ........... the Reduction Rule
and so all G series are just simple multiples of two Fibonacci series. We will call it the Reduction Rule (for G series) since it shows how we can reduce any G series to a sum of (simple multiples of) two Fibonacci series.
Below, we will see how we can use this Rule to identify any G series automatically.

Two special cases are

G(0,1,n) is the Fibonacci series F(i)
G(2,1,n) is the Lucas series L(i)
Incidentally, putting this into (G1) gives us a more complex Fibonacci formula:
F(k)F(i–1) + F(k+1)F(i) = F(i+k)

The Zero Rules

Let's look at two simple cases of G series, where one of the starting values is zero.
We'll start with a few examples. Can you spot the relationship between the examples and either the Fibonacci series? For reference, we include the Fibonacci series as the first one:
i=012345 6789
G(0,1,i)011235 8132134
G(0,2,i)022461016 264268
G(0,3,i)033691524 3963102
Again, it is fairly easy to see that:
G(0, c, i) = c F(i) ..... the First Zero Rule
How about these with the b value zero?
i=012345 6789
G(1,0,i)1011235 81321
G(2,0,i)20224610 162642
G(3,0,i)3033691524 3963
Here we again have multiples of the Fibonacci series, but the indices are shifted by one place:
G(d, 0, i) = d F(i–1) ..... the Second Zero Rule

Adding two G series together

Now we come to another simple property of the G series. Suppose we add corresponding terms from two different G series. Let's take G(a,b,i) and G(A,B,i). Can we predict what the new series with ith term G(a,b,i)+G(A,B,i) is? Here is a closer look:
G(a,b) aba+ba+2b2a+3b3a+5b5a+8b ...F(n–1)a+F(n)b
G(A,B) ABA+BA+2B2A+3B3A+5B5A+8B ...F(n–1)A+F(n)B
G(a,b)+
G(A,B)		 a+Ab+B(a+A)+(b+B)(a+A)+2(b+B)2(a+A)+3(b+B)3(a+A)+5(b+B)5(a+A)+8(b+B) ...F(n–1)(a+A)+F(n)(b+B)
but the final row is identical to G(a+A, b+B)!
This is called the Addition Rule of the G series, that by adding two G series with the same index then we get the G series with the starting values separately added. To put this more precisely, in mathematical notation, we have:
G(a, b, i) + G(A, B, i) = G(a+A, b+B, i) ..... the Addition Rule for G series
Putting this Addition Rule together with the two Zero Rules (G(0,c,i)= cF(i) and G(d,0,i)=dF(i–1):
G(c,d,i) = G(0,c,i) + G(d,0,i) = c F(i) + d F(i–1)
which is just the Reduction Rule above.

Multiplying a G series by a number

The same simplification about adding two G series applies to multiplying all the terms of a G series by a constant number. Multiplying all the terms by k is the same series as the one with starting values ka and kb because
G(ka, kb, i) = (ka)F(i–1) + (kb)F(i) = k [aF(i–1) + bF(i)] = k G(a,b,i)
G(ka, kb, i) = k G(a, b, i) ..... the Multiple Rule for G series
The Addition Rule and the Multiple Rule for G series we will call the Linear Property of the G series.

G series as a sum of multiples of 2 Fibonacci numbers

First we show how, knowing the two starting values a and b of a G series we can find an equivalent in terms of two Fibonacci series. Then we will show how to express any Fibonacci-type series in such a form.

G(a,b,i) as a sum of two Fibonacci multiples

In the section above we found this convenient formula for G(a,b,n) in terms of the Fibonacci numbers and a and b:
G( a, b, n ) = F( n – 1 ) a + F( n ) b
The Addition Rule, the Multiple Rule and the Reduction Rule give us a method of finding a description of any G series in terms of two Fibonacci series.
We have already seen that if one of the starting values is zero, the G series is the Fibonacci series.
Now we tackle the more general case of any two starting values.
Can you spot how this G series, with starting values 3 and 2 is related to the Fibonacci series?
i=012345 6789
G(3,2,i)3257121931 5081131
This time, the connection is not straightforward. However, you might have noticed that 7, 12, 19 and 31 are not all that far away from the Fibonacci numbers 8, 13, 21 and 34. In fact the differences are -1, -1, -2 and -3. So this immediately suggests the following:
i=012345 6789
Fib(i+3)235 81321345589144
G(3,2,i)3257121931 5081131
difference-1101123 5813
The final row of differences is clearly the Fibonacci series. Since it starts with the 0 term when i=2 then it is F(i–2). So we have: 
             G(3,2,i) = F(i+3) – F(i–2)
The above process depended on spotting that the G series was close to the Fibonacci series at some point. But we could have got to this result directly using the Reduction rule as follows: 
             G(3,2,i) = 3 F(i–1) + 2 F(i)
Alternatively, we could have obtained this from the Addition and Multiplication rules as follows: 
             
             G(3,2,i) = G(3,0,i) + G(0,2,i)
then apply the Multiplication Rule 
   
             G(3,2,i) = G(3,0,i) + G(0,2,i) 
                      = 3 G(1,0,i) + 2 G(0,1,i)
and we can now write this directly in terms of the Fibonacci series using the Zero Index Rules: 
  
             G(3,2,i) = 3 G(1,0,i) + 2 G(0,1,i) 
                      = 3 F(i–1) + 2 F(i)
But this is not the formula we "spotted" above: G(3,2,i)=F(i+3)–F(i–2). We can however rearrange the Reduction Rule formula 3F(i–1) + 2 F(i) into this form and also find several other formula for G(3,2,i) along the way. All we need is the basic Fibonacci Rule F(k+1)+F(k) is F(k+2) which we could also use in an alternative form as F(k+1) is F(k+2)–F(k):-
First replace 2F(i–1)+2F(i) by 2F(i+1): 
             G(3,2,i) = 3 F(i–1)          + 2 F(i)
                      = F(i–1) + 2 F(i–1) + 2 F(i)    splitting up 3 F(i–1)
                      = F(i–1)     + 2 F(i+1)         replacing the final two terms
At this point, since F(i–1)+F(i+1) = L(i), we could introduce Lucas numbers too: 
             
             G(3,2,i) = F(i–1) + 2 F(i+1)
                      = F(i–1) + F(i+1) + F(i+1)     splitting up 2 F(i+1)
                      =       L(i)      + F(i+1)     using the L(i) replacement above
But instead of introducing the Lucas numbers, we will use the Fibonacci Rule, this time replacing F(i–1) by F(i)–F(i–2):– 
             G(3,2,i) =    F(i–1)     + 2 F(i+1)
                      = F(i) – F(i–2) + 2 F(i+1)
                      = F(i) + F(i+1) + F(i+1) – F(i–2)    by rearranging the terms
                      =     F(i+2)    + F(i+1) – F(i–2)    since F(i)+F(i+1) is F(i+2)
                      =            F(i+3)      – F(i–2)    since F(i+1)+F(i+2) is F(i+3)
and there we have it - our original formula for G(3,2,i) but we have found it by simple manipulation of the Reduction Rule formula for G(3,2,i).
So you can choose whichever formula you like for G(3,2,i) from those above!

What we have seen here is that it is easier to use the Reduction Rule on a G series and then perhaps to transform the resulting formula into many other Fibonacci forms using just the basic Fibonacci Rule.
Try these for yourself:

/ Things to do /

  1. What if a=b? e.g. G(1,1) or G(2,2)? Find a formula for G(a,a,i).
  2. Find a simpler form for G(1,3,i)
    1. solely in terms of Fibonacci numbers
    2. in terms of Lucas numbers
  3. Make a table of a values (rows) against b values (columns), each from 0 to 4, and fill in the entries in the table with a simple formula for G(a,b,i).
  4. What is special about G(0,0)?

Simplifying a description of a G series

The last section showed there are several ways to write a G series as a sum of two Fibonacci terms. How do we find the simplest?
For example,
What is a simpler description of G(18,28,i) than 18 F(i-1) + 28 F(i)?
First we notice that 18 and 28 are even numbers, so G(18,28)=2 G(9,14) by the Multiple Rule. 9 and 14 have no factors in common now, so G(9,14) is the simplest form we can get using that Rule.

So to start reducing the constants 9 and 14, we make a G series by applying the Fibonacci Rule backwards from 9, 14 and continue so long as the numbers are getting smaller:

3 ← 1 ← 4 ← 5 ← 9 14
The series G(9,14) is the same as G(3,1) but starts 4 places later - so G(3, 1, i+4) = G(9, 14, i).
We can now do with G(3,1,i) what we did with G(3,2) in the previous section:
         G(3,1,i) = 3 F(i–1) + 1 F(i)        by the Reduction Rule
                  = 2 F(i–1) + F(i+1)        since F(i–1)+F(i) is F(i+1)
So a simpler description of G(9, 14, i) is 
      G(9, 14, i) = G(3, 1, i+4)
                  = 2 F(i+3) + F(i+5).
Finally we have: 
     G(18, 28, i) = 2 G(9, 14, i) 
                  = 4 F(i+3) + 2 F(i+5) or, using the Lucas numbers:
                  = 2 F(i+3) + 2 L(i+4)
We have exchanged the simpler indices and larger multipliers of the original form: 18 F(i-1) + 28 F(i) for simpler multiples of the later forms: 2 F(i+3) + F(i+5) or F(i+3) + L(i+4).
What form is "the simplest form" is therefore really a matter of taste. Usually we choose the form "with the smaller numbers", be they indices or multipliers but this can be a trade-off of one against the other sometimes as we see here.

Here is a calculator to produce a formula for G(a,b,i) where you can input your own values for a and b. The formula found will be one of the simplified forms and a few terms of the series will be calculated too. Note that a and b need not be whole numbers for the methods above to apply!

C A L C U L A T O R
for G(, , i )

R E S U L T S
Infinity means the number has become too big for this calculator

A Formula for G(a,b,n)

An earlier page gives a formula for Fib(i), often called Binet's Formula:
Fib(n) = Phin – (–Phi)–n  =  Phin – (–phi)n

sqrt5
sqrt5
Phi=1.61803... and –phi=–0.618033... are, as usual on these pages, the two roots of the equation x2 = x + 1.
This equation is derived from the Recurrence Relation which we called the Fibonacci Rule:
F(n+2) = F(n+1) + F(n)
but we replace F(i) by xi and solve it for x:
xn+2 = xn+1 + xn but we can divide by xn:
x2 = x + 1

Without going into the theory, the roots of this equation are Phi = (1 + √5)/2 and –phi = (1 – √5)/2. Powers of these two numbers are involved in the formula for G(a,b,n), each being multiplied by a constant specific to each particular G series.
Every Fibonacci-type series (i.e. any G series since they all satisfy the Fibonacci Rule) has the same kind of formula for its elements:

G(a,b,n) = P Phin + Q (–phi)n ..... the G Formula

The constants P and Q are now chosen so that G(a,b,0) gives a and G(a,b,1) is b, called the starting (or boundary) conditions.
From the G formula we have, for n=0 and n=1:
G(a,b,0) = a = P + Q and
G(a,b,1) = b = P Phi – Q phi
When we are given a and b for a particular G series, we can then solve these two equations simultaneously to find the specific P and Q values for the G Formula for that series.
For example, the Fibonacci series itself has a=0 and b=1 so we have
P + Q = 0
P Phi – Q phi = 1
From the first equation, Q = –P which we substitute in the second to get:
P Phi – (–P) phi = 1 or P (Phi+phi)=1 but Phi+phi = √5 so P=1/√5 and Q is therefore –1/√5.
Putting these in the general formula we have
G(0,1,n) = F(n) = (Phin – (–phi)n))/√5
which is Binet's Formula that we saw at the start of this section.

If we solve the general equations a = P + Q and b = P Phi – Q phi then we will have found a general formula for G(a,b,n). It is an easy exercise to show that:

Q = (a Phi – b) / √5
P = (a phi + b) / √5
so we then have:
G(a, b, n) = ( (a phi + b) Phin + (a Phi – b) ( –phi )n )/ √5
G(a, b, n) = ( (a(√5 – 1) + 2b) Phin + (a(√5 + 1) – 2b) ( –phi)n ) / (2√5)

/ Things to do /

  1. Verify the formula for the Lucas series L(n) = G(2,1,n) = Phin + phin.
  2. Earlier we noticed that G(0,0,i) = 0 for all i. Does the G formula work in this case?

C A L C U L A T O R
G(,, i ) for i from
i to

R E S U L T S

The ratio of two neighbouring G terms

Now that we have a formula for G(a,b,n) we can see what happens to the ratio of two consecutive terms in a G series and compare it to what happens in the Fibonacci series. For the Fibonacci series, the further along the series that we go, the ratio of two neighbouring numbers F(n+1)/F(n) gets closer and closer to Phi=1·61803 39887 49894 84820 ... . The larger the Fibonacci numbers, the closer the value gets to Phi whose exact value is (√5+1)/2. If we took the other ratio: F(n)/F(n+1) then this gets closer and closer to 1/Phi, that is, phi=0·61803 39887 49894 84820 ... . whose exact value is (√5-1)/2.
Since the Fibonacci series is two-sided, that is we can extend it "to the left" as well as "to the right", then with n getting more and more negative, the ratio of F(n) to the next in the series: F(n+1), gets closer and closer to -Phi = -1.618033... and the other ratio, F(n+1)/F(n) tends towards -phi:
n...-15-14 -13...-3-2-10123... 131415...
Fib(n)...610-377233... 2-110112... 233377610...
Fib(n+1)
/
Fib(n)
 ...-0.6180327..-0.6180371..-0.6180257..... -0.5-10?012... 1.6180257..1.6180371..1.6180327.....
We can now show that the property of the Fibonacci series, that the ratio of neighbouring terms get closer to Phi is also true of any G series too in the following proof steps:
  1. G(a,b,n) is P Phin + Q (-phi)n for some numbers P and Q which will depend upon a and b.
    For this proof it does not matter what P and Q actually are since they are just constant numbers that do not change with n.
  2. (-phi)n will get smaller and smaller as n gets larger (since phi<1)
  3. so the Q (-phi)n term gets smaller and smaller as n gets larger
  4. Phin gets larger and larger as n gets larger (since Phi>1)
  5. so P Phin gets larger too
  6. For "large" n, G(a,b,n) becomes almost exactly P Phin because the -phi terms get so small that they are insignificant
  7. so the ratio of G(a,b,n+1) to G(a,b,n) becomes closer and closer to (P Phin+1)/(P Phin) which is just Phi.
No matter what two starting values we choose for a and b,
the ratio G(a,b,n+1)/G(a,b,n) gets closer and closer to Phi as n gets larger.

Actually, there is one exception to the above that we have ignored which makes the proof steps listed above wrong. One special G series is the exception where the ratio does not get closer and closer to Phi as n gets larger:
What is the exception (special starting values for a and b) and where have we overlooked it in the proof steps above?
If we go further along the (two-sided) list of numbers in a G series, going to the left, a similar argument to the one above will prove that G(a,b,n+1)/G(a,b,n) gets closer and closer to (-phi), again with the one exceptional G series excluded from this.

All numbers are in the Wythoff Array of G series

There is something rather special about the collection of G series G(n, floor( (n+1)Phi ) ) which, if we list them all in a table, is called The Wythoff Array.

Rounding, Floors and Ceilings

If you are asking "What's the floor function?", it is just the function that finds the nearest integer below any number. Of course, if the number is already a whole number, it doesn't change it. Think of holding a lead weight at height x in a building with floors at heights 0 (ground level), 1, 2, 3, etc. If you let the object go, which floor will it land on? If it is already on a floor, it doesn't move, otherwise it falls to the nearest integer below. Floors can be below ground level also, at heights -1, -2, -3, etc. If an object is -3.1 (the units don't matter) below the ground level, it will fall onto which floor? -3? No! It'll land on floor -4! 
 Examples are:
	  floor( 3.1) = 3;    floor( 3.9) = 3;    floor(3) = 3
	  floor(-3.1) =-4;    floor(-3.9) =-4;    floor(-4)=-4

This function is sometimes denoted trunc(x) on calculators or in programming languages but note that it is only the same as floor(x) if x is not a negative number! This is because trunc(x) truncates a number by erasing anything after its decimal point: trunc(3.1) is 3 which the same as floor(3.1) but trunc(-3.1) is just -3 whereas floor(-3.1) is -4.
Trunc(x) is also denoted by a variation of the brackets [x] where only the bottom horizontal parts are used for floor and only the top horizontal parts for the companion function ceiling:

floor(x) is written [ x ]

There is a similar function called ceiling and this time think of a (very tiny) balloon at height x floating up to a ceiling where the floors/ceilings are again at integer unit heights.

ceiling(x) is written [ x ]

but we do not use the ceiling function on this page.

You can think of floor(x) and ceiling(x) as other types of rounding function so that floor is the round-down function (take any non-integer value down to the next integer below) and ceiling as the round-up function whereas round itself rounds to the nearest integer so may take values up or down. This is reflected in the square bracket symbols used for each of these functions.

round(x) is written [ x ]

The Wythoff Array

Here is a table of the floor function applied to multiples of Phi =1.6180339... = (√5+1)/2:
n1234567
n Phi1.61803.23614.85416.47218.0902 9.708211.3262
[n Phi] 13468911
An interesting thing happens when we pair n with floor( (n+1)Phi ) as starting values for G series. The part in black is called The Wythoff Array in which each row is formed by the Fibonacci Rule from the two coloured starting values. We show the first few rows and columns here:
n[(n+1)Phi] G(n,[(n+1)Phi])
Wythoff Array
01123581321345589144
13471118294776123
2461016264268110
36915243963102
481220325284136
591423376097157
61117284573118191
71219315081131212
81422365894152246
916254166107173280
1017274471115186301
1119304979128207335
1221335487141296479
1322355792149241390
14243862100162262424
15254065105170275445
16274370113183296479

Interesting Wythoff Array facts

Some interesting facts and figures about the Wythoff Array (the black numbers) from Neil Sloane's Classic Sequences page and the work of John Conway are: The whole array is Sloane's A035513 and the first column (1, 4, 6, 9, 12,...) is A003622

The Zeckendorf Representations and the Wythoff Array

The Zeckendorf Representation of a number is one of the Fibonacci Representations of numbers. The Zeckendorf Representation is that unique set of non-consecutive Fibonacci numbers that add up to n. Strictly, the Zeckendorf Representation of a number n is when we write the number in Base Fibonacci, that is, label the columns from right to left not with powers of 10 as in the ordinary decimal number system but with the Fibonacci numbers (using 1 only once).
E.g. 12 is 8+3+1 as a sum of (non-consecutive) Fibonacci numbers so it is written as 10101 (since the column headings are ...8 5 3 2 1). Some further Wythoff Array facts: To illustrate the Zeckendorf properties, here is part of the array (the black numbers only) in their Zeckendorf representation form:
0110 1001000...
11011010 10100101000...
2100110010 1001001001000...
310001100010 100010010001000...
410101101010 101010010101000...
51000011000010 10000100100001000...
61001011001010 10010100100101000...

In which row is number n in the Wythoff Array?

Here is a table of the row numbers of the Wythoff Array where numbers 1 to 40 occur:
n1234567 8910111213141516 17181920
row000102103 2140532617 4
n212223242526 2728293031323334 353637383940
row085392106 111741201385 14315
0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, ...
John H Conway calls this sequence the Vertical Para-Fibonacci Sequence .
It is "vertical" because it relates each integer 1,2,3,... to its row (vertically)in Wythoff's array.
(A019586 in Sloane's Encyclopaedia of Integer Sequences).
You'll have noticed that the Fibonacci numbers occur on row 0.
What do you notice about the numbers between the zeroes?
They each contain all the numbers from 1 upwards, each set containing one more number in order. Each set between the zeroes is a permutation of the first k numbers each permutation containing one more number than the previous one.
This means that
the k numbers between two Fibonacci numbers each occur on a different row of the first k rows of the Wythoff array

The sequence 0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, 8, 5, ... has a further self-reproducing property. Delete from the sequence the first occurrence of 1, 2, 3, 4, ... as shown in green here:

0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, 8, 5, ...
and we get:
0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5,
exactly the same sequence! Looking at the permutations themselves reveals some further interesting patterns. Here is the same sequence with the permutations shown individually: 
0
0
0 1
0 2 1
0 3 2 1 4
0 5 3 2 6 1 7 4
0 8 5 3 9 2 10 6 1 11 7 4 12
0 13 8 5 14 3 15 9 2 16 10 6 17 1 18 11 7 19 4 20 12
0 21 13 8 22 5 23 14 3 24 15 9 25 2 26 16 10 27 6 28 17 1 29 18 11 30 7 31 19 4 32 20 12 33 
0 ...
The third one: 3 2 1 4, if we delete 3 and 4 gives the second one:2 1. We can delete numbers bigger than 2 from any permutation and we will always get 2 1.
Similarly, if we delete any numbers bigger than 4 we will always obtain the permutation 3 2 1 4.
This applies to each and every between-zeroes permutation in the sequence.

We can show this by vertically aligning each of the numbers in the permutations as follows: 

0
0
0                                                       1
0                                 2                     1
0                    3            2                     1                     4
0            5       3            2             6       1             7       4
0       8    5       3       9    2       10    6       1       11    7       4       12
0    13 8    5    14 3    15 9    2    16 10    6    17 1    18 11    7    19 4    20 12
0 21 13 8 22 5 23 14 3 24 15 9 25 2 26 16 10 27 6 28 17 1 29 18 11 30 7 31 19 4 32 20 12 33
Later permutations insert the extra numbers in between the earlier permutations numbers. Which numbers are inserted? The next set between two Fibonacci numbers.
Where are they inserted? Row n+1 is made by inserting F(n-1) to up F(n)-1 into row n after each number that appeared in row n-1. For example:

So this enables us to quickly build a table of the row number that n appears in Wythoff's Array.

What about the column number where n appears?

In which column is number n in the Wythoff Array?

Because the first number in each row has a Zeckendorf representation that ends in 1 and each subsequent number in the row has one extra zero appended to it, the number of trailing zeroes in the Zeckendorf representation of n tells us the column number of n in Wythoff's Array.
n1234567 8910111213141516 17181920
col01203014 012050120 301
n212223242526 2728293031323334 353637383940
col6012030 14012070 12030
This sequence also has a self-reproducing property:
if we remove all (green) zeroes and decrease all non-zero numbers by 1 we obtain the original sequence:
01203014012050120301...
012030140120...
In Sloane's A035612 the columns start at 1 instead of 0 so his numbers are one more than that we show here.
This series is called the horizontal para-Fibonacci sequence; "horizontal" because it relates each number 1,2,3... to its horizontal position (its column) in Wythoff's array.
Sloane's Integer Sequence reference gives another fractal (self-reproducing) property of this series:
0 1 2 0 3 0 1 4 0 1 2 0 5 0 1 2 0 3 0 1 6
The first occurrence of each number marks out sections of the series. The first occurrences are shown here in red:
0 1 2 0 3 0 1 4 0 1 2 0 5 0 1 2 0 3 0 1 6
Did you notice that the section between n and n+1 is a repeat of the section from the start up to n-1. E.g. the section between 4 and 5 is 0 1 2 0 which is the starting section of the whole sequence up to 3.
This gives a constructive way to write the sequence:
Here is the sequence being constructed by this method:
C A L C U L A T O R
the Zeckendorf representation of up to
the number with Fibonacci representation:

Fibonacci representations allow two consecutive 1's but Zeck. reps do not.
the Wythoff array entries for row to
column to

of entries up to in the Wythoff array

R E S U L T S:
Infinity means the number has become too big for this calculator

The Stolarsky Array is similar

You might suppose that the Wythoff array has so many special properties that it is unique, but you'd be wrong! D Morrison (see References below) has shown that there are an infinite number of arrays where each row is a Fibonacci-type series and the array contain all the positive numbers once and once only as. However, the Stolarsky array here does not contain every positive (general) Fibonacci sequence.
Let's look at another example - the Stolarsky Array - which was the first array to be discovered (in 1977) with all these properties. In fact, all such arrays are still referred to as Stolarsky arrays.

The Stolarsky Array

In the Wythoff array, we used the floor (round-down) of multiples of Phi.
In Stolarsky's array we round the multiples of Phi, that is, use the nearest integer to each multiple of Phi. The round function is written as round(x) and also [x] to contrast with the "round-down" or floor function |_ x _|:
n1234567
n Phi1.61803.23614.85416.47218.0902 9.708211.3262
|_ n Phi _| 13468911
[ n Phi ]235681011
C A L C U L A T O R
Floor:
Fractional:
Round:
Ceiling:
of multiples  from
up to

R E S U L T S:
Stolarsky Array entries up to 100
0123456789
0123581321345589
1461016264268
271118294776
3915243963
41219315081
51423376097
617284573
720325284
822365894
9254065
10274471
11304979
12335386
13355792
14386199
154166
164370
174674
184878
195183
205487
215691
225995
2362100
2464
2567
2669
2772
2875
2977
3080
3182
3285
3388
3490
3593
3696
3798
Since the Fibonacci numbers are 1,2,3,5,8,... then row 2 begins with 4, the smallest number missing from the Fibonacci series. Using our table of rounded multiples of Phi above, 4 is followed by [ 4 Phi ] = 6 and 6 by [ 6 Phi ] = 10. The first two rows are now:
123581321...
461016264268...
The smallest number missing from these two rows is 7 so 7 starts row 3. The Stolarsky array begins as follows:

This whole table (read by diagonals) is sequence A035506 in Sloane's Encyclopaedia.
The article by Morrison (see References below) proves that each row uses the Fibonacci Rule so that each row is a G series.

There is also a formula for the number in row r in the first column: r + 1 + |_ (r+0.5) Phi _| where r is the row number.
So the Stolarsky array entry in row r and column c is gc+1( [r+0.5]Phi] )where g(x) is [ x Phi ] and gp means "g is applied p times" e.g. the first entry in row numbered 3 is 3+1+|_ 3.5 Phi _| or 9 and the 4th entry on that row (in column 3) will contain g(g(g(g(9)))) = 63.

We now ask the same two questions of the Stolarsky array that we asked of the Wythoff array:

In which row is number n in the Stolarsky Array?

Here is a table of the row numbers of the Stolarsky Array where numbers 1 to 40 occur:
n1234567 8910111213141516 17181920
row000101203 1240531624 7
n212223242526 2728293031323334 353637383940
row085391106 211471201385 1439
n41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
row15 1 16 10 6 17 2 18 11 4 19 7 12 20 0 21 13 8 22 5
Again we can lay these out with the 0s starting each new section as follows: 
 0
 0
 0                       1
 0                       1              2
 0              3        1              2        4
 0        5     3        1        6     2        4     7
 0     8  5     3  9     1    10  6     2    11  4     7 12
 0 13  8  5 14  3  9 15  1 16 10  6 17  2 18 11  4 19  7 12 20
 ...
What rule governs the placing of the new number in the section now?

In which column is number n in the Stolarsky Array?

Here is the sequence of column numbers for each i from 1 to 40:
n1234567 8910111213141516 17181920
col01203104 021050130 210
n212223242526 2728293031323334 353637383940
col60120401 302107012 031
n41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
col0 5 0 1 2 0 4 0 1 3 0 2 1 0 8 0 1 2 0 3
You can check that this sequence also has the same self-reproducing property of column numbers for the Wythoff array.
Can you find the rule that governs the section-copying rule here of the same kind that we discovered for Wythoff columns?
C A L C U L A T O R
the Stolarsky array of row to
column to

in the Stolarsky array of up to

R E S U L T S

Links and Bibliography

Prof. Clark Kimberling of Evansville University (USA) has added much to our knowledge of the Wythoff Array and its recursive properties. Neil Sloane calls the Wythoff Array a Classic Sequence and much on this page expands on the properties he mentions on his page.

Previous Topic Fibonacci - the man and His Times Fibonacci HOME Fibonacci Home Page
Previous page The Fibonomials

WHERE TO NOW???

Next page on this Topic The Golden Section In Art, Architecture and Music

NEXT TOPIC Fibonacci, Phi and Lucas numbers Formulae
NEXT TOPIC Links and References

Valid HTML 4.01! © 2003-2013 Dr Ron Knott email
created 14 August 2003; updated 8 January 2013