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 ci ≥ 2, with ci + 1 > ci + 1, such that
- N=∑i=0kFci,{displaystyle N=sum _{i=0}^{k}F_{c_{i}},}
where Fn is the nth 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.
Contents
1 History
2 Proof
3 Fibonacci multiplication
4 Representation with negafibonacci numbers
5 See also
6 References
7 External links
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.[1] As such, the theorem is an example of Stigler's Law of Eponymy.
Proof
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 Fj < n < Fj + 1 . Now suppose each a < n has a Zeckendorf representation (induction hypothesis) and consider a = n − Fj . Since a < n, a has a Zeckendorf representation. At the same time, a < Fj + 1 − Fj = Fj − 1 , so the Zeckendorf representation of a does not contain Fj − 1 . As a result, n can be represented as the sum of Fj 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 Fj is strictly less than the next larger Fibonacci number Fj + 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′ = ST and T′ = TS). Since S and T had equal sum, and we have removed exactly the elements from S ∩{displaystyle cap } 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 Fs and the largest member of T′ be Ft. Because S′ and T′ contain no common elements, Fs ≠ Ft. Without loss of generality, suppose Fs < Ft. Then by the lemma, the sum of S′ is strictly less than Fs + 1 and so is strictly less than Ft, whereas the sum of T′ is clearly at least Ft. 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 multiplication
One can define the following operation a∘b{displaystyle acirc b} on natural numbers a, b: given the Zeckendorf representations
a=∑i=0kFci(ci≥2){displaystyle a=sum _{i=0}^{k}F_{c_{i}};(c_{i}geq 2)} and b=∑j=0lFdj(dj≥2){displaystyle b=sum _{j=0}^{l}F_{d_{j}};(d_{j}geq 2)} we define the Fibonacci product a∘b=∑i=0k∑j=0lFci+dj.{displaystyle acirc b=sum _{i=0}^{k}sum _{j=0}^{l}F_{c_{i}+d_{j}}.}
For example, the Zeckendorf representation of 2 is F3{displaystyle F_{3}}, and the Zeckendorf representation of 4 is F4+F2{displaystyle F_{4}+F_{2}} (F1{displaystyle F_{1}} is disallowed from representations), so 2∘4=F3+4+F3+2=13+5=18.{displaystyle 2circ 4=F_{3+4}+F_{3+2}=13+5=18.}
(Note that the product is not always in Zeckendorf form. For example, 4∘4=(F4+F2)∘(F4+F2)=F4+4+2F4+2+F2+2=21+2⋅8+3=40=F9+F5+F2.{displaystyle 4circ 4=(F_{4}+F_{2})circ (F_{4}+F_{2})=F_{4+4}+2F_{4+2}+F_{2+2}=21+2cdot 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]
Representation with negafibonacci numbers
The Fibonacci sequence can be extended to negative index n using the re-arranged recurrence relation
- Fn−2=Fn−Fn−1,{displaystyle F_{n-2}=F_{n}-F_{n-1},}
which yields the sequence of "negafibonacci" numbers satisfying
- F−n=(−1)n+1Fn.{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−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.
Note that 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 nth 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 also
- Complete sequence
- Fibonacci coding
- Fibonacci nim
- Ostrowski numeration
References
^ 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..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
^ 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 links
- 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", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
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.