The calculators on this page require JavaScript but you appear to have switched JavaScript off
(it is disabled). Please go to the Preferences for this browser and enable it if you want to use the
calculators, then Reload this page.
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
You do the maths... section of questions to start your own investigations.
The calculator icon
indicates that there is a live interactive calculator in that 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.
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:
Here is a simple calculator to show you some terms of a General Fibonacci Series.
It will produce one or a range of consecutive values of a G function.
Enter your values for a and b,
for the starting index "from" value and, if you want more than one value, the ending "to" index also,
either of which may be negative.
Click the Show button.
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
G(a,b,i):
...
–3a+2b
2a–b
–a+b
a
b
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(0,1,i)
0
1
1
2
3
5
8
13
21
34
F(i)
G(1,1,i)
1
1
2
3
5
8
13
21
34
55
F(i+1)
G(1,2,i)
1
2
3
5
8
13
21
34
55
89
F(i+2)
G(2,3,i)
2
3
5
8
13
21
34
55
89
144
F(i+3)
G(1,0,i)
1
0
1
1
2
3
5
8
13
21
F(i–1)
G(–1,1,i)
–1
1
0
1
1
2
3
5
8
13
F(i–2)
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.
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−1), F(k), 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 ith 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 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=
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:
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:
You do the maths...
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(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!
An earlier page gives a formula for Fib(i), often called Binet's Formula:
Fib(n) =
Phin – (–Phi)–n
=
Phin – (–phi)n
√5
√5
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
Using results about Solving the Quadratic that we learn in maths classes at school
we can easily find that 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:
Verify the formula for the Lucas series L(n) = G(2,1,n) = Phin + phin.
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 (√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
-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 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.
(-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
Phin gets larger and larger as n gets larger (since Phi>1)
so P Phin gets larger too
For "large" n, G(a,b,n) becomes almost exactly P Phin 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 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!
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:
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 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:
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 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:
exactly the same sequence!
Looking at the permutations themselves reveals some further interesting patterns.
Here is the same sequence with the permutations shown individually:
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:
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:
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 32 6 1 7 4
has 8 9 10 11 12 inserted after each of 0 3 2 1 4 to give: 08 5 39210 6 111 7 412
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: 013 8 514315 9 216 10 617118 11 719420 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 self-reproducing property:
if we remove all (green) zeroes and decrease all non-zero 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 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:
012 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:
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 n-2 (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: 01 2 03
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 12 0 3 0 14
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 03 0 1 4 0 1 2 05
...
Wythoff and Fibonacci Representation Calculator
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
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 ⌋:
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 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:
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:
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 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?
Every number n is in some G series, for instance G(1,n).
But there are a limited number of G series without negative numbers
that contain n. Which is the longest?
If the starting values a and b have a common factor then,
since G( a, b, n ) = F( n – 1 ) a + F( n ) b, all the following terms will have that factor and so the
series will never contain any primes.
Surprisingly, in 1962, Ronald Graham found a pair of starting values that have no factor in common and
yet no number following them in the G series is ever prime:
a = 331635635998274737472200656430763 and b = 1510028911088401971189590305498785
Since then, smaller pairs numbers have been found but the current smallest (found in 2004) still have 12 digits each:
a = 106276436867 and b = 35256392432.
It is not known if there are any smaller pairs.
Factors of every G series
In 1964, Brother Alfred first noted that some primes appear as a factor of numbers in every G series.
For instance, there is always an even number in every G series:
If one of a or b is even, then we have found our number!
If both are odd then G(a,b,0)=a, G(a,b,1)=b and G(a,b,2)=a+b which as a sum of two odd numbers must be even.
On the other hand, 5, for instance, is never a factor of any Lucas number G(2,1,i)
Similarly 3, 7, 23, 43, 67, ... A000057, the primes of the form
20k + 3 or 20k + 7, also appear as a factor of numbers in every G series.
Brother Alfred proves these are the only primes together with 2.
Once we find a G-series number with a factor n then there are infinitely many more in that G series
that also have this factor and they occur at a regular periodic interval
(called the Pisano period).
The list of all numbers that are factors of every G series begins
2, 3, 4, 6, 7, 9, 14, 23, 27, ... A064414
Generalised Wythoff Arrays, Shuffles and Interspersions
A Fraenkel, C Kimberling Discrete Math. vol 126
(1994), pages 137-149.
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 405-416.
Interspersions and Dispersions
Prof. Clark Kimberling's web page on the Wythoff Array's interspersions and dispersions with more references.
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. pdf
The Fibonacci Numbers: Exposed D Kalman, R Mena
Mathematics Magazine 76 (2003), pages 167-181.
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 second-oder 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 182-192
extends the Kalman and Mena article using nice counting arguments.
A Fibonacci-like sequence of composite numbers Ronald L. Graham, Mathematics
Magazine 37 (1964), 322-324.
A New Fibonacci-like Sequence of Composite Numbers
M Vsemirnov
Journal of Integer Sequences vol 7, (2004) Article 04.3.7
(pdf)
Primes which are factors of all Fibonacci sequences,Brother U Alfred, Fib Quart, 2 (1964),
pages 33-38. PDF
icon means there is a
You do the maths... section of questions to start your own investigations.
calculator icon
indicates that there is a live interactive calculator in that section.
You do the maths...
Fibonacci - the man and His Times
Fibonacci Home Page 
The Fibonomials
Fibonacci, Phi and Lucas numbers Formulae
© 2003-2018 Dr Ron Knott
