Zeckendorf's theorem

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.{{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}} As such, the theorem is an example of Stigler's Law of Eponymy.

Zeckendorf's theorem has two parts:

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

The first part of Zeckendorf's theorem (existence) can be proven by 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_j < n < F_j + 1 }}. Now suppose each positive integer {{math|a < n}} has a Zeckendorf representation (induction hypothesis) and consider {{math|1=b = n − F_j }}. Since {{math|b < n}}, {{mvar|b}} has a Zeckendorf representation by the induction hypothesis. At the same time, {{math|1=b = n − F_j < F_j + 1 − F_j {{=}} F_j − 1 }} (we apply the definition of Fibonacci number in the last equality), so the Zeckendorf representation of {{mvar|b}} does not contain {{math|F_j − 1 }}, and hence also does not contain {{math|F_j }}. As a result, {{math|n}} can be represented as the sum of {{mvar|F_j}} and the Zeckendorf representation of {{mvar|b}}, such that the Fibonacci numbers involved in the sum are distinct.{{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}}

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_j}} is strictly less than the next larger Fibonacci number {{math|F_j + 1 }}.

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

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

Now we will show by contradiction that at least one of $S\text{'}$ and $T\text{'}$ is empty. Assume the contrary, i. e. that $S\text{'}$ and $T\text{'}$ are both non-empty and let the largest member of $S\text{'}$ be {{mvar|F_s}} and the largest member of $T\text{'}$ be {{mvar|F_t}}. Because $S\text{'}$ and $T\text{'}$ contain no common elements, {{math|F_s ≠ F_t}}. Without loss of generality, suppose {{math|F_s < F_t}}. Then by the lemma, , and, by the fact that , , whereas clearly $\backslash sum\_\{x\; \backslash in\; T\text{'}\}\; x\; \backslash geq\; F\_t$. This contradicts the fact that $S\text{'}$ and $T\text{'}$ have the same sum, and we can conclude that either $S\text{'}$ or $T\text{'}$ must be empty.

Now assume (again without loss of generality) that $S\text{'}$ is empty. Then $S\text{'}$ has sum 0, and so must $T\text{'}$. But since $T\text{'}$ can only contain positive integers, it must be empty too. To conclude: $S\text{'}\; =\; T\text{'}\; =\; \backslash emptyset$ which implies $S\; =\; T$, proving that each Zeckendorf representation is unique.

One can define the following operation $a\backslash circ\; b$ on natural numbers {{mvar|a}}, {{mvar|b}}: given the Zeckendorf representations

$a=\backslash sum\_\{i=0\}^kF\_\{c\_i\}\backslash ;(c\_i\backslash ge2)$ and $b=\backslash sum\_\{j=0\}^lF\_\{d\_j\}\backslash ;(d\_j\backslash ge2)$ we define the Fibonacci product $a\backslash circ\; b=\backslash sum\_\{i=0\}^k\backslash sum\_\{j=0\}^lF\_\{c\_i+d\_j\}.$

For example, the Zeckendorf representation of 2 is $F\_3$, and the Zeckendorf representation of 4 is $F\_4\; +\; F\_2$ ($F\_1$ is disallowed from representations), so $2\; \backslash circ\; 4\; =\; F\_\{3+4\}\; +\; F\_\{3+2\}\; =\; 13\; +\; 5\; =\; 18.$

(The product is not always in Zeckendorf form. For example, $4\; \backslash circ\; 4\; =\; (F\_4\; +\; F\_2)\; \backslash circ\; (F\_4\; +\; F\_2)\; =\; F\_\{4+4\}\; +\; 2F\_\{4+2\}\; +\; F\_\{2+2\}\; =\; 21\; +\; 2\backslash cdot\; 8\; +\; 3\; =\; 40\; =\; F\_9\; +\; F\_5\; +\; F\_2.$)

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.{{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 }}

The Fibonacci sequence can be extended to negative index {{mvar|n}} using the rearranged recurrence relation

:$F\_\{n-2\}\; =\; F\_n\; -\; F\_\{n-1\},$

which yields the sequence of "negafibonacci" numbers satisfying

:$F\_\{-n\}\; =\; (-1)^\{n+1\}\; F\_n.$

Any integer can be uniquely represented{{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}} as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:

• {{math|1=−11 = F₋₄ + F₋₆ = (−3) + (−8)}}
• {{math|1=12 = F₋₂ + F₋₇ = (−1) + 13}}
• {{math|1=24 = F₋₁ + F₋₄ + F₋₆ + F₋₉ = 1 + (−3) + (−8) + 34}}
• {{math|1=−43 = F₋₂ + F₋₇ + F₋₁₀ = (−1) + 13 + (−55)}}
• 0 is represented by the empty sum.

{{math|1=0 = F₋₁ + F₋₂ }}, 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 {{mvar|x}}, the {{mvar|n}}^th digit is 1 if {{mvar|F_−n}} 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₋₁ + F₋₄ + F₋₆ + F₋₉ }}. The integer {{mvar|x}} is represented by a string of odd length if and only if {{math|x > 0}}.

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

{{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 }}

• {{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