# 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.

## Our decimal system

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.

## Other bases

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:
10112 = 1110
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 demi-semiquaver is 1/8. They are written in musical notation as shown here:
NoteSymbolDuration
(beats)
Semi-breve4
Minim2
Crotchet1
Quaver1/2
Semiquaver1/4
Demisemiquaver1/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·012 and 3/8 = 0·0112 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·12
crotchet dot dot = 1·112
crotchet dot dot dot = 1·1112
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:
11001002 = 102013 = 12104 = 4005 = 2446 = 2027 = 1448 = 1219 = 10010
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 B-1 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!

1010 = A, 1110 = B, 1210 = C, and so on.
Here is one hundred again, this time expressed in some bases bigger than ten:
10010 = 9111 = 8412 = 7913 = 7214 = 6A15
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.

C A L C U L A T O R
in base to base
R E S U L T S:

## Sumthing about Fibonacci Numbers

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!

C A L C U L A T O R
 of unique Fibonacci numbers whose sum is
R E S U L T S:

#### Things to do

1. 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?
2. 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?
3. 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 289-306 and 322.
The smallest positive integer having Fk representations as sums of distinct Fibonacci numbers Marjorie Bicknell-Johnson 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 47-52.
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 61-73, is about turning R(n) directly into music.

## The Fibonacci base system

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.

### Digits in the Fibonacci system

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 = 2000Fib = 5 + 3 + 2 = 1110Fib = 3 3 + 1 = 301Fib = 10 1 = AFib
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:
DecimalFibonacci
00
11
210
3100
4101
51000
61001
71010
810000
910001
1010010
1110100
1210101
13100000
14100001
15100010
16100100
17100101
18101000
19101001
20101010

#### Historical Note

We can also call this the Fibonaccimal system (pronounced fib-on-arch-i-mal) 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 179-182.
A Generalized Fibonacci Numeration E Zeckendorf Fibonacci Quarterly vol 10 (1972) page 365-372 with Errata Fibonacci Quarterly vol 11 (1973) page 524.
Edouard Zeckendorf C Kimberling Fibonacci Quarterly 36 (1998), pages 416-418.

C A L C U L A T O R
R E S U L T S:

#### Things to do

1. 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.
2. 4 has a Zeckendorf representation of 101Fib = 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?
3. Investigate the number of ones in the Zeckendorf representations. What patterns can you find? Can you express your patterns as mathematical formulae?
4. 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)?

## An Application of the Fibonacci Number Representation

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

1. 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)?
2. The speed limit on UK motorways is 70 mph. What is this in kilometres per hour?
3. 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?
4. 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, Addison-Wesley, section 6.6.

## An easy way to Multiply

### The Egyptian system - using Doubling...

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

1. Check that if you halve the 65 column and double the 19 column the method still works.
2. Try the Egyptian method on 32x65.
3. Try it on 31x65.

### The Fibonacci system

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

1. Try it the other way round, starting with 19 and stop when the Fibonacci number exceeds 65.
2. Try the same multiplications as above: 32x65 and 31x65.
3. 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 177-187.

## Patterns in the Fibonacci representations

### Patterns in the columns - the Rabbit sequence

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 right-hand 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(i-1) 1s followed by F(i) 0s.
DecimalFibonacci
00
11
210
3100
4101
51000
61001
71010
810000
910001
1010010
1110100
1210101
13100000
14100001
15100010
16100100
17100101
18101000
19101001
20101010

### 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:
nnFib1's
1 11
2 101
3 1001
4 1012
5 10001
6 10012
7 10102
8 100001
9 100012
10 100102
11 101002
12 101013
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=1Fib 1, 2=10Fib 1, 3=100Fib,4=101Fib 1,2 5=1000Fib, 6=1001Fib, 7=1010Fib 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.

### Palindromic Fibonacci Representations

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
11
4101
61001
910001
1210101
14100001
221000001
271001001
331010101
3510000001
5110100101
56100000001
64100010001
74100101001
80101000101
88101010101
901000000001
Is there a formula for the series 1,4,6,9,12,14,...?

## A more general Fibonacci System

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 multi-set or bag of Fibonacci numbers whose sum is N.
NFib numbers whose sum is N
allowing repeats
Count
111
22, 1+12
33, 2+1, 1+1+13
43+1, 2+2, 2+1+1, 1+1+1+14
55, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+16
65+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+18
Notice the following things about this table:
1. 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.
2. 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).
3. 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 No. ofreps N No. ofreps N No. ofreps N No. ofreps 1 2 3 4 5 6 7 8 9 10 1 2 3 4 6 8 10 14 17 22 11 12 13 14 15 16 17 18 19 20 27 33 41 49 59 71 83 99 115 134 21 22 23 24 25 26 27 28 29 30 157 180 208 239 272 312 353 400 453 509 31 32 33 34 35 36 37 38 39 40 573 642 717 803 892 993 1102 1219 1350 1489

C A L C U L A T O R
 of Fibonacci numbers (repetitions allowed) whose sum is
R E S U L T S:

### 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
 ... 5 3 2 1 1 0 3 2 Fib = 13

### 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.
Advanced note: The generating function for this series is
 i = 2 1 = 1 + x + 2x2 + 3x3 + 4x4 + 6x5 + ... 1 – xFib(i)

## 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

1. 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.
2. 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 317-331 is a useful introduction to results in this area, but for post-18 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.

© 1996-2006 Dr Ron Knott
updated 26 May 2004