View source for Zeckendorf's theorem

{{short description|On the unique representation of integers as sums of non-consecutive Fibonacci numbers}}
[[Image:Zeckendorf representations 89px.png|thumb|right|267px|The first 89 [[natural number]]s in Zeckendorf form. Each rectangle has a Fibonacci number {{math|''F''<sub>''j''</sub>}} as width (blue number in the center) and {{math|''F''<sub>''j''−1</sub>}} as height. The vertical bands have width 10.]]
In [[mathematics]], '''Zeckendorf's theorem''', named after [[Belgium|Belgian]] amateur mathematician [[Edouard Zeckendorf]], is a [[theorem]] about the representation of [[integer]]s as sums of [[Fibonacci number]]s.

Zeckendorf's theorem states that every [[positive integer]] can be represented [[uniqueness quantification|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 {{mvar|N}} is any positive integer, there exist positive integers {{math|''c''<sub>''i''</sub> ≥ 2}}, with {{math|''c''<sub>''i'' + 1</sub> > ''c''<sub>''i''</sub> + 1}}, such that

:<math>N = \sum_{i = 0}^k F_{c_i},</math>
      
where {{mvar|F<sub>n</sub>}} is the {{mvar|n}}<sup>th</sup> Fibonacci number.  Such a sum is called the '''Zeckendorf representation''' of {{mvar|N}}. The [[Fibonacci coding]] of {{mvar|N}} can be derived from its Zeckendorf representation.

For example, the Zeckendorf representation of 64 is

:{{math|1=64 = 55 + 8 + 1}}.

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

:{{math|1=64 = 55 + 5 + 3 + 1}}
:{{math|1=64 = 34 + 21 + 8 + 1}}
:{{math|1=64 = 34 + 21 + 5 + 3 + 1}}
:{{math|1=64 = 34 + 13 + 8 + 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, 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>{{Cite web |title=Fibonacci bases and Other Ways of Representing Numbers |url=https://r-knott.surrey.ac.uk/Fibonacci/fibrep.html |access-date=2024-03-16 |website=r-knott.surrey.ac.uk}}</ref> As such, the theorem is an example of [[Stigler's law of eponymy|Stigler's Law of Eponymy]].

==Proof==
Zeckendorf's theorem has two parts:

#'''Existence''': every positive integer {{mvar|n}} has a Zeckendorf representation.
#'''Uniqueness''': no positive integer {{mvar|n}} has two different Zeckendorf representations.

The first part of Zeckendorf's theorem (existence) can be proven by [[Mathematical induction|induction]]. For {{math|1=''n'' = 1, 2, 3}} it is clearly true (as these are Fibonacci numbers), for {{math|1=''n'' = 4}} we have {{math|1=4 = 3 + 1}}. If {{math|''n''}} is a Fibonacci number then there is nothing to prove. Otherwise there exists {{mvar|j}} such that {{math|''F''<sub>''j''</sub> < ''n'' < ''F''<sub>''j'' + 1</sub> }}. Now suppose each positive integer {{math|''a'' < ''n''}} has a Zeckendorf representation (induction hypothesis) and consider {{math|1=''b'' = ''n'' − ''F''<sub>''j''</sub> }}. Since {{math|''b'' < ''n''}}, {{mvar|b}} has a Zeckendorf representation by the induction hypothesis. At the same time, {{math|1=''b'' = ''n'' − ''F''<sub>''j''</sub> < ''F''<sub>''j'' + 1</sub> − ''F''<sub>''j''</sub> {{=}} ''F''<sub>''j'' − 1</sub> }} (we apply the definition of Fibonacci number in the last equality), so the Zeckendorf representation of {{mvar|b}} does not contain {{math|''F''<sub>''j'' − 1</sub> }}, and hence also does not contain {{math|''F''<sub>''j''</sub> }}. As a result, {{math|''n''}} can be represented as the sum of {{mvar|F<sub>j</sub>}} and the Zeckendorf representation of {{mvar|b}}, such that the Fibonacci numbers involved in the sum are distinct.<ref name=":0">{{Cite web |last=Henderson |first=Nik |date=July 23, 2016 |title=What Is Zeckendorf's Theorem? |url=https://math.osu.edu/sites/math.osu.edu/files/henderson_zeckendorf.pdf |access-date=August 23, 2024 |website=Ohio State University}}</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 {{mvar|F<sub>j</sub>}} is strictly less than the next larger Fibonacci number {{math|''F''<sub>''j'' + 1</sub> }}.

The lemma can be proven by induction on {{mvar|j}}.

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.&nbsp;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 [[Proof by contradiction|by contradiction]] that at least one of <math>S'</math> and <math>T'</math> is empty. Assume the contrary, i.&nbsp;e. that <math>S'</math> and <math>T'</math> are both non-empty and let the largest member of <math>S'</math> be {{mvar|F<sub>s</sub>}} and the largest member of <math>T'</math> be {{mvar|F<sub>t</sub>}}. Because <math>S'</math> and <math>T'</math> contain no common elements, {{math|''F''<sub>''s''</sub> ≠ ''F''<sub>''t''</sub>}}. [[Without loss of generality]], suppose {{math|''F''<sub>''s''</sub> < ''F''<sub>''t''</sub>}}. 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 {{mvar|a}}, {{mvar|b}}:  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>{{cite journal |first=Donald E. |last=Knuth |authorlink=Donald Knuth |title=Fibonacci multiplication |journal=Applied Mathematics Letters |volume=1 |issue=1 |year=1988 |pages=57–60 | doi=10.1016/0893-9659(88)90176-0 |zbl=0633.10011 |issn=0893-9659 |url=http://www.cs.umb.edu/~rvetro/vetroBioComp/compression/FIBO/KnuthFibb.pdf|doi-access=free }}</ref>

==Representation with negafibonacci numbers==
The Fibonacci sequence can be extended to negative index&nbsp;{{mvar|n}} 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>{{cite conference |last=Knuth |first=Donald |authorlink=Donald Knuth |title=Negafibonacci Numbers and the Hyperbolic Plane |conference=Annual meeting, Mathematical Association of America |location=The Fairmont Hotel, San Jose, CA |date=2008-12-11 |url=http://www.allacademic.com/meta/p206842_index.html}}</ref> as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used.  For example:

* {{math|1=−11 = ''F''<sub>−4</sub> + ''F''<sub>−6</sub> = (−3) + (−8)}}
* {{math|1=12 = ''F''<sub>−2</sub> + ''F''<sub>−7</sub> = (−1) + 13}}
* {{math|1=24 =  ''F''<sub>−1</sub> + ''F''<sub>−4</sub> + ''F''<sub>−6</sub> + ''F''<sub>−9</sub> = 1 + (−3) + (−8) + 34}}
* {{math|1=−43 = ''F''<sub>−2</sub> + ''F''<sub>−7</sub> + ''F''<sub>−10</sub> = (−1) + 13 + (−55)}}
* 0 is represented by the [[empty sum]].

{{math|1=0 = ''F''<sub>−1</sub> + ''F''<sub>−2</sub> }}, for example, so the uniqueness of the representation does depend on the condition that no two consecutive negafibonacci numbers are used.

This gives a [[NegaFibonacci coding|system]] of coding [[integers]], similar to the representation of Zeckendorf's theorem. In the string representing the integer&nbsp;{{mvar|x}}, the {{mvar|n}}<sup>th</sup> digit is 1 if {{mvar|F<sub>−n</sub>}} appears in the sum that represents {{mvar|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 {{math|1=24 = ''F''<sub>−1</sub> + ''F''<sub>−4</sub> + ''F''<sub>−6</sub> + ''F''<sub>−9</sub> }}.  The integer&nbsp;{{mvar|x}} is represented by a string of odd length [[if and only if]] {{math|''x'' > 0}}.

==See also==
* [[Complete sequence]]
* [[Fibonacci coding]]
* [[Fibonacci nim]]
* [[Ostrowski numeration]]

==References==
{{reflist}}
* {{cite journal | zbl=0252.10011 | last=Zeckendorf | first=E. | title=Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas | language=French | journal=Bull. Soc. R. Sci. Liège | volume=41 | pages=179–182 | year=1972 | issn=0037-9565 }}

==External links==
*{{MathWorld |title=Zeckendorf's Theorem |urlname=ZeckendorfsTheorem}}
*{{MathWorld |title=Zeckendorf Representation |urlname=ZeckendorfRepresentation}}
*[http://www.cut-the-knot.org/ctk/OnePile.shtml#fibnim Zeckendorf's theorem] at [[cut-the-knot]]
*{{SpringerEOM|title=Zeckendorf representation|author=G.M. Phillips}}
*{{OEIS el|sequencenumber=A101330|name=Knuth's Fibonacci (or circle) product|formalname=Array read by antidiagonals: T(n,k) = Knuth's Fibonacci (or circle) product of n and k ("n o k"), n >= 1, k >= 1}}

{{PlanetMath attribution|id=8810|title=proof that the Zeckendorf representation of a positive integer is unique}}

[[Category:Fibonacci numbers]]
[[Category:Theorems in number theory]]
[[Category:Articles containing proofs]]