# Zeckendorf's theorem

**Zeckendorf's theorem**, named after Belgian mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers.

Zeckendorf's theorem states that every positive integer can be represented uniquely as the sum of *one or more* distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. More precisely, if N is any positive integer, there exist positive integers *c*_{i} ≥ 2, with *c*_{i + 1} > *c*_{i} + 1, such that

where F_{n} is the n^{th} Fibonacci number. Such a sum is called the **Zeckendorf representation** of N. The Fibonacci coding of N can be derived from its Zeckendorf representation.

For example, the Zeckendorf representation of 64 is

- 64 = 55 + 8 + 1.

There are other ways of representing 64 as the sum of Fibonacci numbers – for example

- 64 = 34 + 21 + 8 + 1
- 64 = 55 + 5 + 3 + 1

but these are not Zeckendorf representations because 34 and 21 are consecutive Fibonacci numbers, as are 5 and 3.

For any given positive integer, a representation that satisfies the conditions of Zeckendorf's theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage.

## HistoryEdit

While the theorem is named after the eponymous author who published his paper in 1972, the same result had been published 20 years earlier by Gerrit Lekkerkerker.^{[1]} As such, the theorem is an example of Stigler's Law of Eponymy.

## ProofEdit

This section does not cite any sources. (September 2012) (Learn how and when to remove this template message) |

Zeckendorf's theorem has two parts:

**Existence**: every positive integer n has a Zeckendorf representation.**Uniqueness**: no positive integer n has two different Zeckendorf representations.

The first part of Zeckendorf's theorem (existence) can be proven by induction. For *n* = 1, 2, 3 it is clearly true (as these are Fibonacci numbers), for *n* = 4 we have 4 = 3 + 1. If *n* is a Fibonacci number then we're done. Else there exists j such that *F*_{j} < *n* < *F*_{j + 1} . Now suppose each *a* < *n* has a Zeckendorf representation (induction hypothesis) and consider *a* = *n* − *F*_{j} . Since *a* < *n*, a has a Zeckendorf representation. At the same time, *a* < *F*_{j + 1} − *F*_{j} = *F*_{j − 1} , so the Zeckendorf representation of a does not contain *F*_{j − 1} . As a result, *n* can be represented as the sum of F_{j} and the Zeckendorf representation of a.

The second part of Zeckendorf's theorem (uniqueness) requires the following lemma:

*Lemma*: The sum of any non-empty set of distinct, non-consecutive Fibonacci numbers whose largest member is F_{j}is strictly less than the next larger Fibonacci number*F*_{j + 1}.

The lemma can be proven by induction on j.

Now take two non-empty sets of distinct non-consecutive Fibonacci numbers **S** and **T** which have the same sum. Consider sets **S ′** and

**T**which are equal to

`′`**S**and

**T**from which the common elements have been removed (i.e.

**S**=

`′`**S**\

**T**and

**T**=

`′`**T**\

**S**). Since

**S**and

**T**had equal sum, and we have removed exactly the elements from

**S**

**T**from both sets,

**S**and

`′`**T**must have the same sum as well.

`′`Now we will show by contradiction that at least one of **S ′** and

**T**is empty. Assume the contrary, i.e. that

`′`**S**and

`′`**T**are both non-empty and let the largest member of

`′`**S**be F

`′`_{s}and the largest member of

**T**be F

`′`_{t}. Because

**S**and

`′`**T**contain no common elements,

`′`*F*

_{s}≠

*F*

_{t}. Without loss of generality, suppose

*F*

_{s}<

*F*

_{t}. Then by the lemma, the sum of

**S**is strictly less than

`′`*F*

_{s + 1}and so is strictly less than F

_{t}, whereas the sum of

**T**is clearly at least F

`′`_{t}. This contradicts the fact that

**S**and

`′`**T**have the same sum, and we can conclude that either

`′`**S**or

`′`**T**must be empty.

`′`Now assume (again without loss of generality) that **S ′** is empty. Then

**S**has sum 0, and so must

`′`**T**. But since

`′`**T**can only contain positive integers, it must be empty too. To conclude:

`′`**S**=

`′`**T**= ∅ which implies

`′`**S**=

**T**, proving that each Zeckendorf representation is unique.

## Fibonacci multiplicationEdit

One can define the following operation on natural numbers a, b: given the Zeckendorf representations
and we define the **Fibonacci product**

For example, the Zeckendorf representation of 2 is , and the Zeckendorf representation of 4 is ( is disallowed from representations), so

(The product is not always in Zeckendorf form. For example, )

A simple rearrangement of sums shows that this is a commutative operation; however, Donald Knuth proved the surprising fact that this operation is also associative.^{[2]}

## Representation with negafibonacci numbersEdit

The Fibonacci sequence can be extended to negative index n using the re-arranged recurrence relation

which yields the sequence of "negafibonacci" numbers satisfying

Any integer can be uniquely represented^{[3]} as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:

- −11 =
*F*_{−4}+*F*_{−6}= (−3) + (−8) - 12 =
*F*_{−2}+*F*_{−7}= (−1) + 13 - 24 =
*F*_{−1}+*F*_{−4}+*F*_{−6}+*F*_{−9}= 1 + (−3) + (−8) + 34 - −43 =
*F*_{−2}+*F*_{−7}+*F*_{−10}= (−1) + 13 + (−55) - 0 is represented by the empty sum.

0 = *F*_{−1} + *F*_{−2} , for example, so the uniqueness of the representation does depend on the condition that no two consecutive negafibonacci numbers are used.

This gives a system of coding integers, similar to the representation of Zeckendorf's theorem. In the string representing the integer x, the n^{th} digit is 1 if F_{−n} appears in the sum that represents x; that digit is 0 otherwise. For example, 24 may be represented by the string 100101001, which has the digit 1 in places 9, 6, 4, and 1, because 24 = *F*_{−1} + *F*_{−4} + *F*_{−6} + *F*_{−9} . The integer x is represented by a string of odd length if and only if *x* > 0.

## See alsoEdit

## ReferencesEdit

**^**Historical note on the name Zeckendorf Representation by R Knott, University of Surrey**^**Knuth, Donald E. (1988). "Fibonacci multiplication" (PDF).*Applied Mathematics Letters*.**1**(1): 57–60. doi:10.1016/0893-9659(88)90176-0. ISSN 0893-9659. Zbl 0633.10011.**^**Knuth, Donald (2008-12-11).*Negafibonacci Numbers and the Hyperbolic Plane*. Annual meeting, Mathematical Association of America. The Fairmont Hotel, San Jose, CA.

- Zeckendorf, E. (1972). "Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas".
*Bull. Soc. R. Sci. Liège*(in French).**41**: 179–182. ISSN 0037-9565. Zbl 0252.10011.

## External linksEdit

- Weisstein, Eric W. "Zeckendorf's Theorem".
*MathWorld*. - Weisstein, Eric W. "Zeckendorf Representation".
*MathWorld*. - Zeckendorf's theorem at cut-the-knot
- G.M. Phillips (2001) [1994], "Zeckendorf representation",
*Encyclopedia of Mathematics*, EMS Press - OEIS sequence A101330 (Knuth's Fibonacci (or circle) product)

*This article incorporates material from proof that the Zeckendorf representation of a positive integer is unique on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.*