Using the Fibonacci numbers to represent whole numbers
First we show how to use the Fibonacci numbers only to represent every whole number, how to use it
to convert easily between miles and kilometres, that multiplication in this
system is easy and
a connection with the Rabbit sequence.
All this is done from scratch and does not need lots of mathematical experience.
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 way we write our numbers is based on a system of tens  the
decimal system. Each column is worth ten times the one on its right so that the
columns indicate powers of ten:
... 1000 100 10 1
3 6 0 7 = three thousand, six hundred (no tens) and seven
Since each column is TEN times the one on its right, we need ten symbols
to represent the ten values in each column: 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9, called digits.
Each positive number has a unique representation in the decimal system.
Why use 10? The reason is almost certainly that early writing systems were based on
counting using the fingers.
[Our word digit comes from the Latin for finger. ]
Tally systems were ways of putting marks or notches in
wooden sticks (tally sticks) and they can be read more easily if grouped in batches of
5 or 10 for convenience.
What if we used another power or base rather than ten?
Binary
Using powers of 2, we have the binary system, used in almost all computers.
Here the columns are labelled with the powers of 2, and there are just 2
binary digits, 0 and 1, called bits.
... 16 8 4 2 1
1 0 1 1
= 8 + 2+1 = eleven
In order to distinguish 11 (eleven) from 11 in another base, we will
put the
base as a _{subscript} (or sometimes in brackets) after the representation to avoid confusion. So 1011 in binary is 11 in
base 10 is written as:
1011_{2} = 11_{10}
Note that the base numbers (here 2 and 10) are always
ordinary decimal numbers.
In the next section we will see that the binary system is used in musical notation.
Musical Notation
If a crotchet is taken as lasting for one beat,
then the semibreve is 4 beats , the minim 2,
a quaver ^{1}/_{2}, a semiquaver ^{1}/_{4} and
demisemiquaver is ^{1}/_{8}.
They are written in musical notation as shown here:
Note  Symbol  Duration (beats) 
Semibreve   4 
Minim   2 
Crotchet   1 
Quaver   1/2 
Semiquaver   1/4 
Demisemiquaver   1/8 
A dot is placed after a note to add on one half of its value.
So a dotted crotchet is a crotchet plus a quaver and has a duration of 1·5 time units;
two dots after a crotchet give a duration of 1 + 1/2 + 1/4 = 1·75 units.
F.J Budden in
An Introduction to Number Scales and Computers, Longmans, 1965,
page 65, says he thinks the record number of dots is 4 in Verdi's Requiem in the
Rex Tremenda. It is useful when a long note is followed by a quick note and the next note is "on the beat".
 
Binary fractions are written using column headings as follows:
... 8 4 2 1 · 1/2 1/4 1/8 ...
So 1/4 = 0·01_{2} and 3/8 = 0·011_{2} since it is 1/4+1/8.
In binary, a dot after a crotchet adds a one in a fractional column:
crotchet = 1
crotchet dot = 1·1_{2}
crotchet dot dot = 1·11_{2}
crotchet dot dot dot = 1·111_{2}
and so on.
More bases
Base 8 is called octal and is presumably used by
intelligent octopuses (or should that be octopi)!
It uses "digits" 0, 1, 2, 3, 4, 5, 6 and 7.
Base 3 is ternary and uses only 0, 1 and 2.
Here is one hundred expressed in all the bases from 2 to 9:
1100100_{2} = 10201_{3} = 1210_{4} = 400_{5} = 244_{6} = 202_{7} = 144_{8} = 121_{9} = 100_{10}
Base 2 is called binary,
Base 3 is called ternary,
Base 4 is called quaternary,
Base 5 is called quinary,
Base 6 is called senary,
Base 7 is called septenary,
Base 8 is called octonary or octal,
Base 9 is called nonary,
Base 10 is called denary or decimal,
continued below ...
What about Base 1?
Numbers in base 1 have columns that are powers of 1, so they are all ones!
You might think that
this base is not very good, but it was, in fact, the earliest system of written numbers.
In Base 1,
2 is 11, 3 is 111, 4 is 1111, etc. So we make marks (1s) to count the number.
This was used in a Talley System which worked like this:
Suppose I lent you 5 sheep to graze on your field and cut your grass,
I would make a mark for each sheep on a stick. Then the
stick would be broken in half lengthways (across the marks) so we each had a copy of the 5 marks.
The two sticks could then
be compared to see if they tallied (agreed) to prevent me adding a mark or you erasing a mark on the sticks.
Our English word score for the number of points made by one side in a game also means "to cut".
The system was widely used in England from the twelfth century until 1826 by the Exchequer (see Oystein Ore's book
below for pictures). When the collection of
old wooden tallies was burned in 1836, it caused a fire in the old wooden Parliament buildings in
London and burnt them down. The current
Houses of Parliament (Westminster Palace) was built to replace them.
Number Theory and Its History O Ore, Dover (1988), 388 pages, is an excellent and
classic book to get you into all aspects of the mathematics of whole numbers (or Number Theory).
What about bases bigger than 10?
There is no logical reason why we cannot use any integer bigger than zero
for a base.
The only problem is what to use to represent 10 or more in a single
column? We need a single symbol for each value from 0 to B1 in base B.
Usually the capital letters, A, B, C, etc, are used which take us up to
base 36 (using the 10 digits and the 26 letters)  after that, it's up to you!
10_{10} = A, 11_{10} = B, 12_{10} = C, and so on.
Here is one hundred again, this time expressed in some bases bigger than ten:
100_{10} = 91_{11} = 84_{12} = 79_{13} = 72_{14} = 6A_{15}
Base 11 is called undenary,
Base 12 is called duodenary or duodecimal,
Base 16 is called hexadecimal.
Chad Lake
at the University of Utah has a nice page on what he calls the Snake Algorithm
for converting from one base to another on paper. It is a web page for a course he gave at Indiana University.
Here is an investigation into representing numbers as sums of Fibonacci numbers.
First, let's just use any Fibonacci number once in any of our sums to see what we get.
For example:
 1 is a sum all on its own! So there is just one sum of Fibonacci numbers with a sum of 1!
 1+1=2 but we are not allowing this as a Fibonacci sum since we have used 1 more than once!
 2 is, however, a sum formed of Fibonacci numbers but with just one number all on its own.
 1+2=3 and 3 is also a Fibonacci number so there are two sums for 3.
 1+3=4 is the only way to make a total of 4 using only Fibonacci numbers.
 2+3=5 and again 5 is a Fibonacci number so there are two sums for 5
 Find two sums for 6.
 Find the single sum for 7.
 How many ways can you make 8?
Did you remember that 8 is also a Fibonacci number in the last example above? If so,
you will have found three ways to make 8 as a Fibonacci sum.
1  is the smallest number with just a single number in its Fibonacci sum 
3  is the first number with two Fibonacci sums; 
8  is the smallest number with three such sums: 1+2+5=3+5=8 
?  What is the smallest number with 4 Fibonacci sums? (Hint: It is less than 20) 
?  What is the smallest number with 5 Fibonacci sums? (Hint: It is less than 30) 
...  Can you continue this series of smallest numbers with n Fibonacci sums?

You might have noticed that we are assuming:
Every number is the sum of some set of Fibonacci Numbers
Note: By set here we mean the mathematical term for
a collection of unique items, no
item being repeated.
The set {1,3,5} is allowed as a collection of Fibonacci numbers
with a sum of 9
because each number in the collection appears no more than once
(all the items are unique).
But {2,2,5} is excluded as a set totalling 9
even though all the numbers are Fibonacci numbers
because it has a repeated number in it.
This result is indeed true but we do not prove it here.
It forms the idea behind representing numbers using Fibonacci numbers that we will
investigate now in different forms on the rest of this page.
Our decimal system relies on the fact that
Every number is the sum of some collection of Powers Of Ten where we can use
each power of ten up to ten times.
A013583
is Sloane's series of the smallest numbers
that can be written as a sum of n unique Fibonacci numbers: use it to check your answers.
You might expect that the more numbers we want in the Fibonacci sum, the larger will be the first number
we find with such a sum, and, in general, you would be right.
But notice that this series is not always increasing! You will therefore be able to find numbers a and b where
a is less than b, but a will have more Fibonacci sums than the larger number b in this list!
Things to do
 What about the number of Fibonacci sums for the Fibonacci numbers themselves?
We have seen the number of Fibonacci sums for 1 and for 2 is 1; for 3 and for 5 is 2; for 8 it is 3.
What about 13? and 21? What is the pattern here? Can you explain it?
 What is special about the number of Fibonacci sums for these numbers:
1,2,4,7,12,20,... ?
What are the next 2 numbers with the same property?
Suggest a simple formula for the numbers in this series.
Again, can you prove or explain your result?
 Find the series of numbers that have just 2 Fibonacci sums.
Quite a bit is now known about this series: the number of representations of n as a sum of unique Fibonacci
numbers (Sloane's A000119) which is called R(n).
Here is a graph of it up for n from 1 to 143. At first it looks fairly random, but look closely and you'll
find several examples of a fractal pattern where a section of the pattern is repeated but surrounded
before and afterwards by another pattern.
If you have a nice explanation or a proof of your answers to the questions above or you find some
other patterns, please email me
using the address at the bottom of this page.
Representations of N as a sum of distinct elements from special sequences
D. A. Klarner, Fibonacci Quarterly, vol 4 (1966), pages 289306 and 322.
The smallest positive integer having F_{k} representations as sums of distinct
Fibonacci numbers Marjorie BicknellJohnson in Applications of Fibonacci Numbers Vol 8
(Proceedings of the Eighth International Research Conference of Fibonacci Numbers and their Applications,
Rochester, USA, June 1998, editor F T Howard, Kluwer Academic) pages 4752.
The above article solves the problem of a formula for R(n), the number of sets of Fibonacci numbers
whose total is n, by giving a recursive definition for it. The article is followed by two others, the second of which is...
Composing with Sequences:... but is it art? by John Bliss, in Applications of Fibonacci Numbers Vol 8
(Proceedings of the Eighth International Research Conference of Fibonacci Numbers and their Applications,
Rochester, USA, June 1998, editor F T Howard, Kluwer Academic), pages 6173,
is about turning R(n) directly into music.
Going back to the decimal number system,
what if we labelled the columns with the Fibonacci numbers instead
of powers of 10? We follow the usual conventions of larger column sizes being on the LEFT:
... 13 8 5 3 2 1
We will show that a number is represented in this system by putting _{Fib}
after it: e.g.:
 8  5  3  2  1 
ten =  1  0  0  1  0  _{Fib} =  8 + 2 
which distinguishes it from ten thousand and ten (10010) in decimal.
This time it is not clear what digits we should use in the columns. For instance, there are
many ways to represent the value ten in this system as well as in the example above:
10_{ }  = 2 5 = 2000_{Fib} 
 = 5 + 3 + 2 = 1110_{Fib} 
 = 3 3 + 1 = 301_{Fib} 
 = 10 1 = A_{Fib} 
Usually a number representation system is most useful if it has a unique representation
of every integer. If we use only the digits 0 and 1
then we have our Fibonacci Sums of the previous section. But we saw there that, although
each number does have such a sum (i.e. it is representable),
some numbers have more than one sum and so their representation is not unique.
We can find a single way to write every number as a sum of Fibonacci numbers if we also have
the rule that no two consecutive Fibonacci numbers can be used in the same sum.
In terms of the base system with Fibonacci numbers as the headings, this means
that no two ones can occur next to each other.
This last condition is because the sum of any two consecutive Fibonacci numbers is
just the following Fibonacci number, so we can always replace ..011.. by ..100.. .
To convince yourself that every number can be represented in this system, write
down the Fibonacci representations of all the numbers from 1 to 40. It starts
as follows:
Decimal  Fibonacci 
0  0 
1  1 
2  10 
3  100 
4  101 
5  1000 
6  1001 
7  1010 
8  10000 
9  10001 
10  10010 
11  10100 
12  10101 
13  100000 
14  100001 
15  100010 
16  100100 
17  100101 
18  101000 
19  101001 
20  101010 
Historical Note
We can also call this the Fibonaccimal system (pronounced fibonarchimal)
as Marijke van Gans does because decimal refers to Base 10.
This system is also called the Zeckendorf representation of a number after
Edouard Zeckendorf who wrote about it (in French) in 1972. He proved that
each representation of a number n as a sum of distinct Fibonacci numbers,
but where no two consecutive Fibonacci numbers are used (and there is onyl one column
headed "1"), is unique.
Earlier, Lekkerkerker had written about this representation in 1952 (in Dutch) showing that
there is only one way to write a number in this system.
Représentation des nombres naturels par une somme de nombres de Fibonacci
ou de nombres de Lucas, E Zeckendorf,
Bulletin de las Societe Royale des Science de Liege
vol 41 (1972) pages 179182.
A Generalized Fibonacci Numeration E Zeckendorf Fibonacci Quarterly
vol 10 (1972) page 365372 with Errata Fibonacci Quarterly vol 11 (1973) page 524.
Edouard Zeckendorf C Kimberling Fibonacci Quarterly 36 (1998), pages 416418.
Things to do
 The Zeckendorf system uses the set with the
fewest Fibonacci numbers in it. What about choosing that set with the most
Fibonacci numbers with a sum of n, each Fibonacci number being used at most once?
This is called the maximal Fibonacci bit representation. "Bit" means that
the only digits in the representations are 0 and 1. Zeckendorf's is therefore the
minimal Fibonacci bit representation.
Make a table of the maximal bit representation for n from 1 to 25.
 4 has a Zeckendorf representation of 101_{Fib} = 3+1. It is also the only
set of Fibonacci numbers with a sum of 4. What other numbers have just a single set of
Fibonacci numbers that sum to them?
 Investigate the number of ones in the Zeckendorf representations. What patterns
can you find? Can you express your patterns as mathematical formulae?
 What about the size of the largest sets (the number of ones in the maximal bit representations)?
Is there a formulae for this function (from n to the size of the largest set)?
There are approximately 8 kilometres in 5 miles. Since both of these are Fibonacci numbers
then there are approximately Phi (1.618..) kilometres in 1 mile and phi (0.618..) miles
in 1 kilometres.
The real figure is more like 1.6093.. kilometres in 1 mile.
This comes from the precise definition of 1 inch equals 2.54 centimetres exactly,
and 100,000 centimetres make 1 kilometre. In the imperial
system, 36 inches are 1 yard and 1760 yards are 1 mile.
Replacing each Fibonacci number by the one before it
has the effect of reducing it
by approximately 0.618 (phi) times (the ratio of a Fibonacci number to the one before it
is nearly phi).
So to convert 13 kilometres to miles, replace 13 by the previous Fibonacci number, 8, and
13 kilometres is about 8 miles. Similarly, 5 kilometres is about 3 miles and
2 kilometres is about 1 mile.
Now suppose we want to convert 20 kilometres to miles where 20 is not a Fibonacci number.
We can express 20 as a sum of Fibonacci numbers and convert each number separately
and then add them up.
Thus 20 = 13 + 5 + 2.
Using
to stand for approximately equals and replacing 13 by 8, 5 by 3 and 2 by 1, we have
20 kms  =  13 + 5 + 2 kilometres 
 
8 + 3 + 1 miles 
 =  12 miles. 
To convert miles to kilometres,
we write the number of miles as a sum of Fibonacci
numbers and then replace each by the next larger Fibonacci number:
20 miles  =  13 + 5 + 2 miles 
 
21 + 8 + 3 kilometres 
 =  32 kilometres. 
There is no need to use the Fibonacci Representation of a number, which uses the
fewest Fibonacci numbers, but you can use any combination of numbers that add to the
number you are converting. For instance, 40 kilometres is 2
20 and we have just seen that
20 kms is 12 miles.
So 40 kms is 2 12 = 24 miles
approximately.
[With thanks to Paul V S Townsend for reminding me of this application.]
Things to do
 A few years ago, the speed limit in USA was 55 miles per hour (mph).
What would that be in kilometres per hour (km/h)?
 The speed limit on UK motorways is 70 mph.
What is this in kilometres per hour?

The speed limit in
built up areas is 30 mph in the UK. What is 30 mph in km/h?
What do you think the "30" signs would be replaced by if
road signs went metric, i.e. round your conversion to the nearest 5 km/h?
 The current train speed record of 552 km/h was set on April 14 1999
in Japan.
What is the equivalent speed in mph using the Fibonacci method?
What is the equivalent speed in mph using the conversion factor
of 1.6093 km per mile?
Reference
Concrete Mathematics
(2nd edition) by Graham, Knuth and Patashnik, AddisonWesley, section 6.6.
The Egyptians had an easy way to multiply two integers which involved only doubling
numbers and adding  no multiplication tables to learn and no need for a calculator
(except to do the addition).
For example, 19 x 65.
We write the two numbers at the head of two columns, choosing one column to
keep doubling and the other to keep halving (ignoring remainders),
until the halving column reaches 1:
halve double odd?
19 65 +
9 130 +
4 260
2 520
1 1040 +
Any row whose halving column entry was odd is marked (here with +) and we
add the marked values from the doubling column. In our example
65+130+1040=1235 which is the product of 19 and 65.
The method works because if we represent 19 in the binary system we have
16+2+1=10011(2) and so 19x65=(16+2+1)x65 which is 16*65 + 2*65 + 1*65. ie,
the 1st, 2nd and 5th values in the doubling column above.
Things to do
 Check that if you halve the 65 column and double the 19 column the method still
works.
 Try the Egyptian method on 32x65.
 Try it on 31x65.
A similar system uses the Fibonacci representation to replace each doubling of the
Egyptian method with an addition.
Let's take the same example: 19x65.
This time we take just one number  say 65  as the head of the right hand column, the
left column starting with 1. The second row has 2 on the left and we double 65 to get 130
on the right.
Now each successive row is the sum of the previous TWO entries above it, taking
each column separately. So since we started with 1 and 2 on the left we will get 3,5,8,...
that is, the
Fibonacci numbers on the left hand side. Stop when we can find a Fibonacci number
which is bigger than the other number in the product  here 19:
1 65 +
2 130
3 195
5 325 +
8 520
13 845 +
21
We mark the rows this time by finding those entries in the left column that add up to 19.
There many be several ways to do this selection but any will do. Here we have chosen 13+5+1.
If we add up the right hand entries on these rows we have: 65+325+845=1235 which is again
19x65.
Things to do
 Try it the other way round, starting with 19 and stop when the Fibonacci number
exceeds 65.
 Try the same multiplications as above: 32x65 and 31x65.
 Look up the article where this idea was first presented:
Fibonacci, Lucas and the Egyptians by S La Barbera in
The Fibonacci Quarterly, Vol 9, 1971, pages 177187.
Patterns in the Fibonacci representations
In base 10, if we list all the integers from 1, then there are patterns
in the columns:
Decimal patterns
Column 1 (units) cycles through all the digits
0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 repeatedly;
Column 2 (tens) cycles through all the digits but each digit occurs
ten times;
Column 3 (hundreds) is the same but each digits occurs 100 times;
and so on.
Fibonacci Representations patterns
Is there a pattern in the columns of numbers in the Fibonacci base system?
Yes there is!
It is based on the Rabbit sequence
which now includes the initial 0.
The pattern in column one (the righthand column)
is derived from the rabbit sequence where
every "1" in the rabbit sequence has been replaced by "10":
The rabbit sequence:
010110101101101011010... becomes:
0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 ...
0 10 0 10 10 0 10 0 10 10 0 10 10 0 10 0 10 10 0 10 0 ...
which is column 1 above, read downwards.
[N.B. This is exactly the same as if we flipped the bits (1 changes to 0 and 0 to 1) in the
Rabbit sequence (without its initial zero)!! However, there is a pattern in the other columns which
is better seen with the description above.]
What about column 2 of the Fibonacci
representations?
This is derived similarly:
every "1" in the rabbit sequence is replaced by "100" and
every "0" is replaced by "00".
0 1 0 1 1 0 1 0 1 1 0 1 1 0 ... Rabbit Sequence
00 100 00 100 100 00 100 00 100 100 00 100 100 00 ... Column 2
where column 2 in the Table of Fibonacci representations is read downwards.
For column 3, replace "0" by "000" and "1" by "11000"
For column 4, replace "0" by "00000" and "1" by "11100000"
For column 5, replace "0" by "00000000" and "1" by "1111100000000"
The same pattern follows for all the columns:
Column i the just the rabbit sequence with
"0" replaced by F(i) 0s and
"1" replaced by F(i1) 1s followed by F(i) 0s.

Decimal  Fibonacci 
0  0 
1  1 
2  10 
3  100 
4  101 
5  1000 
6  1001 
7  1010 
8  10000 
9  10001 
10  10010 
11  10100 
12  10101 
13  100000 
14  100001 
15  100010 
16  100100 
17  100101 
18  101000 
19  101001 
20  101010 

The number of 1s in a Fibonacci Representation
What is the least number of Fibonacci numbers that sum to a given n?
This is the number of 1s in the Fibonacci representation, since the description
given above guarantees the least number of Fibonacci's and is also called
the minimal Fibonacci representation.
Here we repeat the Fibonacci Representation table from
above but now include the number of 1's in each representation:
n  n_{Fib}  1's 
1  1  1 
2  10  1 
3  100  1 
4  101  2 
5  1000  1 
6  1001  2 
7  1010  2 
8  10000  1 
9  10001  2 
10  10010  2 
11  10100  2 
12  10101  3 
From the table, we can see that the number of numbers with a Fibonacci representation
of a given length is a Fibonacci number:
There is 1 of length 1,
there is 1 of length 2,
there are 2 of length 3,
there are 3 of length 4,
there are 5 of length 5,...
Here is a more compact list of the number of 1s in the (minimal) Fibonacci representation
of the first few whole numbers :
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  ... 
1  1  1  2  1  2  2  1  2  2  2  3  1  2  2  2  3  2  3  3  1  2  2  2  3  2  3  3  2  3  3  3  4  ... 
If we split this list into sublists corresponding to the different lengths of Fibonacci
representations we have the following:
1=1_{Fib}  1, 
2=10_{Fib}  1, 
3=100_{Fib},4=101_{Fib}  1,2 
5=1000_{Fib}, 6=1001_{Fib}, 7=1010_{Fib}  1,2,2 
8, 9, 10, 11 and 12  1,2,2,2,3 
13 to 20  1,2,2,2,3,2,3,3 
21 to 33  1,2,2,2,3,2,3,3,2,3,3,3,4 
34 to 54  1,2,2,2,3,2,3,3,2,3,3,3,4,2,3,3,3,4,3,4,4 
...  ... 
It is quite easy to see where this pattern comes from: Each time we put a 1 at the start
of our Fibonacci representations and then copy the earlier patterns. For example,
8, 9, 10, 11 and 12 are 8+0, 8+1, 8+2, 8+3 and 8+4.
Can you see any patterns in these sequences?
It seems that each sequence starts off the following sequence.
Can you discover how the remainder of each is formed, that is,
the part that follows (the copy of) the previous sequence?
It is not quite the sequence before, but,
one added to all the items of the sequence before:
 Start with 1 and 1.
 The next sequence is the preceding one followed by adding one to
the sequence before the preceding one.
Since each sequence in the list above starts off the following one, it defines a
unique infinite sequence.
A palindrome is a word or list that is the same when reversed, e.g. radar
or 1001.
Here is the start of the list of numbers which are palindromes in the Fibonacci representation:
N  Fib rep of N 
1  1 
4  101 
6  1001 
9  10001 
12  10101 
14  100001 
22  1000001 
27  1001001 
33  1010101 
35  10000001 
51  10100101 
56  100000001 
64  100010001 
74  100101001 
80  101000101 
88  101010101 
90  1000000001 
Is there a formula for the series 1,4,6,9,12,14,...?
Suppose that, instead of finding just a set of Fibonacci numbers that sum to N,
that is each Fibonacci number is included at most once in the representation, we allow
multiples of any Fibonacci number. We will then have a multiset or bag
of Fibonacci numbers whose sum is N.
N  Fib numbers whose sum is N allowing repeats  Count 
1  1  1 
2  2, 1+1  2 
3  3, 2+1, 1+1+1  3 
4  3+1, 2+2, 2+1+1, 1+1+1+1  4 
5  5, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1  6 
6  5+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1  8 
Notice the following things about this table:
 Since we can have just a single use of a Fibonacci number (no repeats)
in this new system, all the Zeckendorf representations that we looked at above are also included
in the table. Every number has a Zeckendorf representation which is given first.
 There are more sets of Fibonacci numbers that sum to N (i.e. where no Fibonacci number is used
more than once) than the Zeckendorf representation. In the Zeckendorf representation no
two consecutive Fibonacci numbers are used. We can have any Fibonacci numbers in our bags
and so this time we do
allow neighbouring Fibonacci numbers in any collection (bag).
 We are only interested in the collection of Fibonacci numbers that sum to n,
where we allow repeated use of any Fibonacci number. For example 5 is 2+2+1
and this is the same collection
or bag as 1+2+2 and 2+1+2, since each includes two 2's and one 1.
If we had been interested in the
order of the numbers, then we would be studying sequences or lists.
Here is a count of the number of Fibonacci bags with a sum from 1 to 40:
N  1  2  3  4  5  6  7  8  9  10 
No. of reps  1  2  3  4  6  8  10  14  17  22 

N  11  12  13  14  15  16  17  18  19  20 
No. of reps  27  33  41  49  59  71  83  99  115  134 

N  21  22  23  24  25  26  27  28  29  30 
No. of reps  157  180  208  239  272  312  353  400  453  509 

N  31  32  33  34  35  36  37  38  39  40 
No. of reps  573  642  717  803  892  993  1102  1219  1350  1489 
Fibagonacci System
Using bags of Fibonacci's that sum to n, and the existence of at least one bag for
every number n, means we now have another system of representing numbers:
the Fibagonacci Representation!
The columns of this "Fibonacci base" system are again the Fibonacci numbers from 1 upwards
(1 only occurring once). The entries in the columns are the number of copies of that Fibonacci
number in a bag with a sum of n.
This 13 is the sum of the Fibonacci bag 5,2,2,2,1,1 and so is written as
How many Fibagonacci representations of N are there for a number N?
Any number n is just the sum of n 1's and F(2)=1 so that's one bag of Fibonacci's that sum to n, no
matter what n is.
All the sets of Fibonacci numbers that sum to n are also included in the
bags, since a set is a special kind of bag (with no items repeated in it).
Neil Sloane's Online Encyclopedia of
Integer Sequences
lists this as sequence
A003107.
Some more representations using Fibonacci Numbers
Here are some more research topics and ivestigations on other types of collections
of Fibonacci numbers.
Things to do
 We can also look at other kinds of Fibonacci representations. For both sets and bags, it
is the ityems in the collection (and hte number of them) that matters, the order in which they are lsited
begin immaterial since 1,2,3 is the same set (and bag) as 3,1,2.
If the order of elements in the collection now does matter
we would be studying
sequences of Fibonacci numbers whose sum is N also called
compositions.
List the number of compositions of n that contain only Fibonacci numbers.
 Alternatively, we could look
at sets but without the Zeckendorf restriction. Such sets (of unique items)
could now contain consecutive Fibonacci numbers.
On a later page we will investigate what happens if instead
of using the Fibonacci numbers as column headers we use powers of Phi (1.61803..), ie base Phi.
References

A Primer for the Fibonacci Numbers: Part XII, V E Hoggatt Jr, N Cox, M Bicknell
in Fibonacci Quarterly, vol 11 (1973), pages 317331
is a useful introduction to results in this area, but for post18 mathematics students.


Représentation des nombres naturels par une sommme de
nombres de Fibonacci ou de nombres de Lucas by E Zeckendorf in
Bulletin de la Société Royale des Sciences de Liège
vol 41, 1972, pages 179  182
is the article from which the name Zeckendorf Representation is derived.
He says he first found
the Theorem now named after him in 1939. This paper shows that we can use the
Lucas numbers also as a representation system with some
minor conditions.


Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci
C. G. Lekkerkerker, Simon Stevin vol 29, 1952, pages 190  195
appears to be the first article in print that is about the
Fibonacci Number System now usually called the Zeckendorf Representation.

© 19962006 Dr Ron Knott
updated 26 May 2004