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 icon means
there is a Things To Do investigation at the end of the section.
The 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.
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: 
0  1  2  3  4  5  6  ... 
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 
0  1  2  3  4  5  6  ... 
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:
Series  a=G(0)  b=G(1)  i=2  i=3  i=4  i=5 
i=6  i=7  i=8  i=9 
G(1,1,i)  1  1  2  3  5  8  13 
21  34  55 
G(1,2,i)  1  2  3  5  8  13  21 
34  55  89 
G(2,3,i)  2  3  5  8  13  21  34 
55  89  144 
G(1,0,i)  1  0  1  1  2  3  5  8  13  21 
G(–1,1,i)  –1  1  0  1  1  2  3  5  8  13 
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 
...  0  1  2  ... 
G(a,b,i)  ...  a  b  a+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 
0  1  2  3  4  5  6  7 
...  n 
a 
1  0  1  1  2  3  5  8 
...  F(n–1) 
b 
0  1  1  2  3  5  8  13 
...  F(n) 
Sum 
a  b  a+b  a+2b  2a+3b  3a+5b  5a+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=  0  1  2  3  4  5 
6  7  8  9 
G(0,1,i)  0  1  1  2  3  5 
8  13  21  34 
G(0,2,i)  0  2  2  4  6  10  16 
26  42  68 
G(0,3,i)  0  3  3  6  9  15  24 
39  63  102 
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=  0  1  2  3  4  5 
6  7  8  9 
G(1,0,i)  1  0  1  1  2  3  5 
8  13  21 
G(2,0,i)  2  0  2  2  4  6  10 
16  26  42 
G(3,0,i)  3  0  3  3  6  9  15  24 
39  63 
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 i^{th} term G(a,b,i)+G(A,B,i) is?
Here is a closer look:
G(a,b) 
a  b  a+b  a+2b  2a+3b  3a+5b  5a+8b 
...  F(n–1)a+F(n)b 
G(A,B) 
A  B  A+B  A+2B  2A+3B  3A+5B  5A+8B 
...  F(n–1)A+F(n)B 
G(a,b)+ G(A,B) 
a+A  b+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 Fibonaccitype 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=  0  1  2  3  4  5 
6  7  8  9 
G(3,2,i)  3  2  5  7  12  19  31 
50  81  131 
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=  0  1  2  3  4  5 
6  7  8  9 
Fib(i+3)  2  3  5 
8  13  21  34  55  89  144 
G(3,2,i)  3  2  5  7  12  19  31 
50  81  131 
difference  1  1  0  1  1  2  3 
5  8  13 
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
 What if a=b? e.g. G(1,1) or G(2,2)? Find a formula for G(a,a,i).
 Find a simpler form for G(1,3,i)
 solely in terms of Fibonacci numbers
 in terms of Lucas numbers
 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).
 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(i1) + 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(i1) + 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 tradeoff 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!
A Formula for G(a,b,n)
An earlier page gives a formula for Fib(i), often called Binet's Formula:
Fib(n) =  Phi^{n} – (–Phi)^{–n} 
=  Phi^{n} – (–phi)^{n} 



5 
5 
Phi=1.61803... and –phi=–0.618033... are, as usual on these pages, the two roots of the equation x^{2} = 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 x^{i} and solve it for x:
x^{n+2} = x^{n+1} + x^{n} but we can divide by x^{n}:
x^{2} = 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 Fibonaccitype 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 Phi^{n} + 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) = (Phi^{n} – (–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) Phi^{n} + (a Phi – b) ( –phi )^{n} )/ √5
G(a, b, n) = ( (a(√5 – 1) + 2b) Phi^{n} + (a(√5 + 1) – 2b) ( –phi)^{n} ) / (2√5)
Things to do
 Verify the formula for the Lucas series L(n) = G(2,1,n) = Phi^{n} + phi^{n}.
 Earlier we noticed that G(0,0,i) = 0 for all i. Does the G formula work in this case?
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 (√51)/2.
Since the Fibonacci series is twosided, 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  1  0  1  2  3  ... 
13  14  15  ... 
Fib(n)  ...  610  377  233  ... 
2  1  1  0  1  1  2  ... 
233  377  610  ... 
Fib(n+1) 

Fib(n) 


...  0.6180327..  0.6180371..  0.6180257..  ... 
0.5  1  0  ?  0  1  2  ... 
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:
 G(a,b,n) is P Phi^{n} + 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.
 (phi)^{n} will get smaller and smaller as n gets larger (since phi<1)
 so the Q (phi)^{n} term gets smaller and smaller as n gets larger
 Phi^{n} gets larger and larger as n gets larger (since Phi>1)
 so P Phi^{n} gets larger too
 For "large" n, G(a,b,n) becomes almost exactly P Phi^{n} because the phi terms get so small that they are insignificant
 so the ratio of G(a,b,n+1) to G(a,b,n) becomes closer and closer to (P Phi^{n+1})/(P Phi^{n})
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 (twosided) 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 rounddown function (take any noninteger value down to the next integer below)
and ceiling as the roundup 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:
n  1  2  3  4  5  6  7 
n Phi  1.6180  3.2361  4.8541  6.4721  8.0902 
9.7082  11.3262 
n Phi 
1  3  4  6  8  9  11 
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 
0  1  1  2  3  5  8  13  21  34  55  89  144 
1  3  4  7  11  18  29  47  76  123 
2  4  6  10  16  26  42  68  110 
3  6  9  15  24  39  63  102 
4  8  12  20  32  52  84  136 
5  9  14  23  37  60  97  157 
6  11  17  28  45  73  118  191 
7  12  19  31  50  81  131  212 
8  14  22  36  58  94  152  246 
9  16  25  41  66  107  173  280 
10  17  27  44  71  115  186  301 
11  19  30  49  79  128  207  335 
12  21  33  54  87  141  296  479 
13  22  35  57  92  149  241  390 
14  24  38  62  100  162  262  424 
15  25  40  65  105  170  275  445 
16  27  43  70  113  183  296  479 
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:
 Every row and every column is in increasing order.
 Every number from 1 upwards appears once and once only in the array.
 The first row is the Fibonacci sequence.
 The second row is the Lucas sequence.
 Any and every G sequence which eventually has only positive numbers occurs as a row in this array.
 Row n and column c in the Wythoff Array is floor( (n+1)Phi )F(c+2) + nF(c+1)
where the first column in black is column c=0.
 The first number on each row (in black) is the smallest number not in any previous row.
 if one number in a row R appears between two numbers in row S then all numbers in row R do so too.
This is called an interspersion by
Clark Kimberling (see the link).
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 nonconsecutive 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 (nonconsecutive) Fibonacci numbers so it is written as 10101 (since the column headings are
...8 5 3 2 1).
Some further Wythoff Array facts:
 Each number in column 0 has a Zeckendorf representation ending in 1 and all such numbers
are in that column.
 The Zeckendorf representation of every number after the first in a row is formed by appending "0" to
the Zeckendorf representation of the previous number in that row.
To illustrate the Zeckendorf properties, here is part of the array (the black numbers only) in their
Zeckendorf representation form:
0  1  10 
100  1000  ... 
1  101  1010 
10100  101000  ... 
2  1001  10010 
100100  1001000  ... 
3  10001  100010 
1000100  10001000  ... 
4  10101  101010 
1010100  10101000  ... 
5  100001  1000010 
10000100  100001000  ... 
6  100101  1001010 
10010100  100101000  ... 
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:
n  1  2  3  4  5  6  7 
8  9  10  11  12  13  14  15  16 
17  18  19  20 
row  0  0  0  1  0  2  1  0  3 
2  1  4  0  5  3  2  6  1  7 
4 

n  21  22  23  24  25  26 
27  28  29  30  31  32  33  34 
35  36  37  38  39  40 
row  0  8  5  3  9  2  10  6 
1  11  7  4  12  0  13  8  5 
14  3  15 
0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, ...
John H Conway calls this sequence
the Vertical ParaFibonacci 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 selfreproducing 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 betweenzeroes 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(n1) to up F(n)1 into
row n after each number that appeared in row n1. For example:
 the row 0 5 3 2 6 1 7 4 will have
the 5 numbers 8 9 10 11 12 inserted into it after each the numbers that were in the row 0,3,2,1,4:
0 5 3 2 6 1 7 4
has 8 9 10 11 12 inserted after each of 0 3 2 1 4 to give:
0 8 5 3 9 2 10 6 1 11 7 4 12

The row 0 8 5 3 9 2 10 6 1 11 7 4 12
has the 8 numbers from 13 up to 20 inserted after each occurrence of the 8 numbers 0 5 3 2 6 1 7 4
to give:
0 13 8 5 14 3
15 9 2 16 10 6 17
1
18 11 7 19 4 20 12
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.
n  1  2  3  4  5  6  7 
8  9  10  11  12  13  14  15  16 
17  18  19  20 
col  0  1  2  0  3  0  1  4 
0  1  2  0  5  0  1  2  0 
3  0  1 

n  21  22  23  24  25  26 
27  28  29  30  31  32  33  34 
35  36  37  38  39  40 
col  6  0  1  2  0  3  0 
1  4  0  1  2  0  7  0 
1  2  0  3  0 
This sequence also has a selfreproducing property:
if we remove all (green) zeroes and decrease all nonzero numbers by 1
we obtain the original sequence:
0  1  2  0  3  0  1  4  0  1  2  0  5  0  1  2  0  3  0  1  ... 
 0  1   2   0  3   0  1   4   0  1   2   0  ... 
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 paraFibonacci 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 (selfreproducing) 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 n1. 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:
 Start with 0 1 2
 To insert the next new number n (initially n is 3), continue the sequence by copying it out from the beginning
until you meet n2 (which is not copied) and then write down the new number (n).
 Repeat the above step on successive values of n.
Here is the sequence being constructed by this method:
 Start with
0 1 2
 To continue the sequence up to 3:
Copy out the sequence from the start up to 1 and then write the new number 3:
0 1 2 0 3
 To continue the sequence up to 4:
Copy out the sequence from the start up to 2 and then write the new number 4:
0 1 2 0 3 0 1 4
 To continue the sequence up to 5:
Copy out the sequence from the start up to 3 and then write the new number 5:
0 1 2 0 3 0 1 4 0 1 2 0 5
 ...
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 Fibonaccitype 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 (rounddown) 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 "rounddown" or floor function
x :
n  1  2  3  4  5  6  7 
n Phi  1.6180  3.2361  4.8541  6.4721  8.0902 
9.7082  11.3262 
n Phi 
1  3  4  6  8  9  11 
[ n Phi ]  2  3  5  6  8  10  11 
Stolarsky Array entries up to 100
 0  1  2  3  4  5  6  7  8  9 
0  1  2  3  5  8  13  21  34  55  89 
1  4  6  10  16  26  42  68 
2  7  11  18  29  47  76 
3  9  15  24  39  63 
4  12  19  31  50  81 
5  14  23  37  60  97 
6  17  28  45  73 
7  20  32  52  84 
8  22  36  58  94 
9  25  40  65 
10  27  44  71 
11  30  49  79 
12  33  53  86 
13  35  57  92 
14  38  61  99 
15  41  66 
16  43  70 
17  46  74 
18  48  78 
19  51  83 
20  54  87 
21  56  91 
22  59  95 
23  62  100 
24  64 
25  67 
26  69 
27  72 
28  75 
29  77 
30  80 
31  82 
32  85 
33  88 
34  90 
35  93 
36  96 
37  98 
 The first row of Stolarsky's array is again the Fibonacci sequence.
 Each subsequent row begins with the smallest number
missing from all the rows above.
 Thereafter on any row, the entry to the right of number k is
[k Phi], Round(k Phi), the nearest integer to k Phi.
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:
1  2  3  5  8  13  21  ... 
4  6  10  16  26  42  68  ... 
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 g^{c+1}( [r+0.5]Phi] )where g(x) is [ x Phi ] and
g^{p} 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:
n  1  2  3  4  5  6  7 
8  9  10  11  12  13  14  15  16 
17  18  19  20 
row  0  0  0  1  0  1  2  0  3 
1  2  4  0  5  3  1  6  2  4 
7 

n  21  22  23  24  25  26 
27  28  29  30  31  32  33  34 
35  36  37  38  39  40 
row  0  8  5  3  9  1  10  6 
2  11  4  7  12  0  13  8  5 
14  3  9 

n  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60 
row  15  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:
n  1  2  3  4  5  6  7 
8  9  10  11  12  13  14  15  16 
17  18  19  20 
col  0  1  2  0  3  1  0  4 
0  2  1  0  5  0  1  3  0 
2  1  0 

n  21  22  23  24  25  26 
27  28  29  30  31  32  33  34 
35  36  37  38  39  40 
col  6  0  1  2  0  4  0  1 
3  0  2  1  0  7  0  1  2 
0  3  1 

n  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60 
col  0  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 selfreproducing property of
column numbers for the Wythoff array.
Can you find the rule that governs the sectioncopying rule here of the same kind that
we discovered for Wythoff columns?
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.

Generalised Wythoff Arrays, Shuffles and Interspersions
A Fraenkel, C Kimberling Discrete Math. vol 126
(1994), pages 137149.

Orderings of the set of all positive Fibonacci Sequences
C Kimberling in
Applications of the Fibonacci Numbers 5
editors: A N Philippou, A F Horodam, G E Bergum;
Kluwer (1993), pages 405416.

Interspersions and Dispersions
Prof. Clark Kimberling's web page on the Wythoff Array's interspersions and dispersions with more references.

A Stolarsky Array of Wythoff Pairs
D R Morrison in
A Collection of Manuscripts Related to the
Fibonacci Sequence editors: V E Hoggatt Jr., M BicknellJohnson, published by The Fibonacci Association, (1980)
pages 134  136.

A Set of Generalised Fibonacci Sequences such that Each natural Number Belongs to Exactly One
K B Stolarsky Fibonacci Quarterly, vol 15 (1977), page 224.

The Fibonacci Numbers: Exposed D Kalman, R Mena
Mathematics Magazine 76 (2003), pages 167181.
This is an excellent article to examine extensions of the Fibonacci Numbers to the
General Fibonacci series covered on this page. Their aim is to show that
many Fibonacci properties extend to the secondoder recurrences of the kind
A(n+2) = a A(n+1) + b(A(n) for some numbers a and b. Also we need to decide on
A(0) and A(1) too.

The Fibonacci Numbers: Exposed More Discretely A T Benjamin, J J Quinn
Mathematics Magazine 76 (2003),pages 182192
extends the Kalman and Mena article using nice counting arguments.
© 20032013 Dr Ron Knott
created 14 August 2003; updated 8 January 2013