Zeckendorf's theorem

File:Zeckendorf representations 89px.png

The first 89 natural numbers in Zeckendorf form. Each rectangle has a Fibonacci number Template:Math as width (blue number in the center) and Template:Math as height. The vertical bands have width 10.

In mathematics, Zeckendorf's theorem, named after Belgian amateur 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 Template:Mvar is any positive integer, there exist positive integers Template:Math, with Template:Math, such that

<math>N = \sum_{i = 0}^k F_{c_i},</math>

where Template:Mvar is the Template:Mvar^th Fibonacci number. Such a sum is called the Zeckendorf representation of Template:Mvar. The Fibonacci coding of Template:Mvar can be derived from its Zeckendorf representation.

For example, the Zeckendorf representation of 64 is

Template:Math.

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

Template:Math

Template:Math

Template:Math

Template:Math

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

For any given positive integer, its Zeckendorf representation can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage.

History

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.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> As such, the theorem is an example of Stigler's Law of Eponymy.

Proof

Zeckendorf's theorem has two parts:

1. Existence: every positive integer Template:Mvar has a Zeckendorf representation.
2. Uniqueness: no positive integer Template:Mvar has two different Zeckendorf representations.

The first part of Zeckendorf's theorem (existence) can be proven by induction. For Template:Math it is clearly true (as these are Fibonacci numbers), for Template:Math we have Template:Math. If Template:Math is a Fibonacci number then there is nothing to prove. Otherwise there exists Template:Mvar such that Template:Math. Now suppose each positive integer Template:Math has a Zeckendorf representation (induction hypothesis) and consider Template:Math. Since Template:Math, Template:Mvar has a Zeckendorf representation by the induction hypothesis. At the same time, Template:Math (we apply the definition of Fibonacci number in the last equality), so the Zeckendorf representation of Template:Mvar does not contain Template:Math, and hence also does not contain Template:Math. As a result, Template:Math can be represented as the sum of Template:Mvar and the Zeckendorf representation of Template:Mvar, such that the Fibonacci numbers involved in the sum are distinct.<ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

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 Template:Mvar is strictly less than the next larger Fibonacci number Template:Math.

The lemma can be proven by induction on Template:Mvar.

Now take two non-empty sets <math>S</math> and <math>T</math> of distinct non-consecutive Fibonacci numbers which have the same sum, <math display="inline">\sum_{x \in S} x = \sum_{x \in T} x</math>. Consider sets <math>S'</math> and <math>T'</math> which are equal to <math>S</math> and <math>T</math> from which the common elements have been removed (i. e. <math>S' = S\setminus T</math> and <math>T' = T\setminus S</math>). Since <math>S</math> and <math>T</math> had equal sum, and we have removed exactly the elements from <math>S\cap T</math> from both sets, <math>S'</math> and <math>T'</math> must have the same sum as well, <math display="inline">\sum_{x \in S'} x = \sum_{x \in T'} x</math>.

Now we will show by contradiction that at least one of <math>S'</math> and <math>T'</math> is empty. Assume the contrary, i. e. that <math>S'</math> and <math>T'</math> are both non-empty and let the largest member of <math>S'</math> be Template:Mvar and the largest member of <math>T'</math> be Template:Mvar. Because <math>S'</math> and <math>T'</math> contain no common elements, Template:Math. Without loss of generality, suppose Template:Math. Then by the lemma, <math display="inline">\sum_{x \in S'} x < F_{s + 1}</math>, and, by the fact that <math display="inline">F_{s} < F_{s + 1} \leq F_{t}</math>, <math display="inline">\sum_{x \in S'} x < F_t</math>, whereas clearly <math display="inline">\sum_{x \in T'} x \geq F_t</math>. This contradicts the fact that <math>S'</math> and <math>T'</math> have the same sum, and we can conclude that either <math>S'</math> or <math>T'</math> must be empty.

Now assume (again without loss of generality) that <math>S'</math> is empty. Then <math>S'</math> has sum 0, and so must <math>T'</math>. But since <math>T'</math> can only contain positive integers, it must be empty too. To conclude: <math>S' = T' = \emptyset</math> which implies <math>S = T</math>, proving that each Zeckendorf representation is unique.<ref name=":0" />

Fibonacci multiplication

One can define the following operation <math>a\circ b</math> on natural numbers Template:Mvar, Template:Mvar: given the Zeckendorf representations <math>a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2)</math> and <math>b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2)</math> we define the Fibonacci product <math>a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}.</math>

For example, the Zeckendorf representation of 2 is <math>F_3</math>, and the Zeckendorf representation of 4 is <math>F_4 + F_2</math> (<math>F_1</math> is disallowed from representations), so <math>2 \circ 4 = F_{3+4} + F_{3+2} = 13 + 5 = 18.</math>

(The product is not always in Zeckendorf form. For example, <math>4 \circ 4 = (F_4 + F_2) \circ (F_4 + F_2) = F_{4+4} + 2F_{4+2} + F_{2+2} = 21 + 2\cdot 8 + 3 = 40 = F_9 + F_5 + F_2.</math>)

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.<ref>Template:Cite journal</ref>

Representation with negafibonacci numbers

The Fibonacci sequence can be extended to negative index Template:Mvar using the rearranged recurrence relation

<math>F_{n-2} = F_n - F_{n-1}, </math>

which yields the sequence of "negafibonacci" numbers satisfying

<math>F_{-n} = (-1)^{n+1} F_n. </math>

Any integer can be uniquely represented<ref>Template:Cite conference</ref> as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:

• Template:Math
• Template:Math
• Template:Math
• Template:Math
• 0 is represented by the empty sum.

Template:Math, 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 Template:Mvar, the Template:Mvar^th digit is 1 if Template:Mvar appears in the sum that represents Template:Mvar; 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 Template:Math. The integer Template:Mvar is represented by a string of odd length if and only if Template:Math.

See also

• Complete sequence
• Fibonacci coding
• Fibonacci nim
• Ostrowski numeration

References

• Template:Cite journal

External links

• {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:ZeckendorfsTheorem%7CZeckendorfsTheorem.html}} |title = Zeckendorf's Theorem |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

• {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:ZeckendorfRepresentation%7CZeckendorfRepresentation.html}} |title = Zeckendorf Representation |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

• Zeckendorf's theorem at cut-the-knot
• Template:SpringerEOM
• Template:OEIS el

{{#if: | This article incorporates material from the following PlanetMath articles, which are licensed under the Creative Commons Attribution/Share-Alike License: {{#if: | proof that the Zeckendorf representation of a positive integer is unique | {{#if: 8810 | proof that the Zeckendorf representation of a positive integer is unique | [{{{sourceurl}}} proof that the Zeckendorf representation of a positive integer is unique] }} }}, {{#if: | {{{title2}}} | {{#if: | {{{title2}}} | [{{{sourceurl2}}} {{{title2}}}] }} }}{{#if: | , {{#if: | {{{title3}}} | {{#if: | {{{title3}}} | [{{{sourceurl3}}} {{{title3}}}] }} }} }}{{#if: | , {{#if: | {{{title4}}} | {{#if: | {{{title4}}} | [{{{sourceurl4}}} {{{title4}}}] }} }} }}{{#if: | , {{#if: | {{{title5}}} | {{#if: | {{{title5}}} | [{{{sourceurl5}}} {{{title5}}}] }} }} }}{{#if: | , {{#if: | {{{title6}}} | {{#if: | {{{title6}}} | [{{{sourceurl6}}} {{{title6}}}] }} }} }}{{#if: | , {{#if: | {{{title7}}} | {{#if: | {{{title7}}} | [{{{sourceurl7}}} {{{title7}}}] }} }} }}{{#if: | , {{#if: | {{{title8}}} | {{#if: | {{{title8}}} | [{{{sourceurl8}}} {{{title8}}}] }} }} }}{{#if: | , {{#if: | {{{title9}}} | {{#if: | {{{title9}}} | [{{{sourceurl9}}} {{{title9}}}] }} }} }}. | This article incorporates material from {{#if: | proof that the Zeckendorf representation of a positive integer is unique | proof that the Zeckendorf representation of a positive integer is unique}} on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. }}