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

Zeckendorf's theorem has two parts:

1. Existence: every positive integer n has a Zeckendorf representation.
2. 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 there is nothing to prove. Otherwise there exists j such that F_j < n < F_j + 1 . Now suppose each positive integer a < n has a Zeckendorf representation (induction hypothesis) and consider b = n − F_j . Since b < n, b has a Zeckendorf representation by the induction hypothesis. At the same time, 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 b does not contain F_j − 1 , and hence also does not contain F_j . As a result, n can be represented as the sum of F_j and the Zeckendorf representation of b, such that the Fibonacci numbers involved in the sum are distinct.

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 ${\displaystyle S}$ and ${\displaystyle T}$ of distinct non-consecutive Fibonacci numbers which have the same sum, ${\textstyle \sum _{x\in S}x=\sum _{x\in T}x}$. Consider sets ${\displaystyle S'}$ and ${\displaystyle T'}$ which are equal to ${\displaystyle S}$ and ${\displaystyle T}$ from which the common elements have been removed (i. e. ${\displaystyle S'=S\setminus T}$ and ${\displaystyle T'=T\setminus S}$). Since ${\displaystyle S}$ and ${\displaystyle T}$ had equal sum, and we have removed exactly the elements from ${\displaystyle S\cap T}$ from both sets, ${\displaystyle S'}$ and ${\displaystyle T'}$ must have the same sum as well, ${\textstyle \sum _{x\in S'}x=\sum _{x\in T'}x}$.

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

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

One can define the following operation ${\displaystyle a\circ b}$ on natural numbers a, b: given the Zeckendorf representations ${\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)}$ and ${\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)}$ we define the Fibonacci product ${\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.}$

For example, the Zeckendorf representation of 2 is ${\displaystyle F_{3}}$, and the Zeckendorf representation of 4 is ${\displaystyle F_{4}+F_{2}}$ (${\displaystyle F_{1}}$ is disallowed from representations), so ${\displaystyle 2\circ 4=F_{3+4}+F_{3+2}=13+5=18.}$

(The product is not always in Zeckendorf form. For example, ${\displaystyle 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}.}$)

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]

The Fibonacci sequence can be extended to negative index n using the rearranged recurrence relation

${\displaystyle F_{n-2}=F_{n}-F_{n-1},}$

which yields the sequence of "negafibonacci" numbers satisfying

${\displaystyle F_{-n}=(-1)^{n+1}F_{n}.}$

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₋₄ + F₋₆ = (−3) + (−8)
• 12 = F₋₂ + F₋₇ = (−1) + 13
• 24 = F₋₁ + F₋₄ + F₋₆ + F₋₉ = 1 + (−3) + (−8) + 34
• −43 = F₋₂ + F₋₇ + F₋₁₀ = (−1) + 13 + (−55)
• 0 is represented by the empty sum.

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 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₋₁ + F₋₄ + F₋₆ + F₋₉ . The integer x is represented by a string of odd length if and only if x > 0.

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

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

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