Zeckendorf’s theorem
Theorem. Every positive integer can be represented as a sum of distinct non-consecutive Fibonacci numbers in a unique way.
This is Zeckendorf’s theorem, first formulated by Edouard Zeckendorf.
For our purposes here, define the Fibonacci sequence thus: F0=1, F1=1 and Fm=Fm-2+Fm-1 for all m>0. 1 and 1 are not distinct even though the first is F0 and the latter is F1. We will consider two Fibonacci numbers Fi and Fj consecutive if their indexes i and j are consecutive integers, e.g., j=i+1.
A consequence of the theorem is that for every positive integer n there is a unique ordered tuplet Z consisting of k elements, all 0s or 1s, such that
k∑i=1ZiFi=n, |
where Zi is the ith element in Z. This ordered tuplet Z is the Zeckendorf representation of n, or we might even say the Fibonacci base representation of n (or the Fibonacci coding of n).
So for example, 53 = 34 + 13 + 5 + 1, that is, F8+F6+F4+F1. Furthermore, Z=(1,0,1,0,1,0,0,1). We list the constituent elements in descending order from Zk to Z1 to facilitate reinterpretation as a binary integer, 10101001 (or 169) in this example. Taking the Zeckendorf representations of integers in order and reinterpreting in binary as
k∑i=1Zi2i-1 |
gives the sequence 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, … (A003714 in Sloane’s OEIS). It can be observed that these numbers have no consecutive 1s in their binary representations.
References
- 1 J. Tatersall, Elementary number theory in nine chapters Cambridge: Cambridge University Press (2005): 44
- 2 J.-P. Allouche, J. Shallit and G. Skordev, “Self-generating sets, integers with missing blocks and substitutions” Discrete Math., 292 (2005): 1 - 15
Title | Zeckendorf’s theorem |
Canonical name | ZeckendorfsTheorem |
Date of creation | 2013-03-22 16:03:57 |
Last modified on | 2013-03-22 16:03:57 |
Owner | CompositeFan (12809) |
Last modified by | CompositeFan (12809) |
Numerical id | 11 |
Author | CompositeFan (12809) |
Entry type | Theorem |
Classification | msc 11A63 |
Classification | msc 11B39 |
Synonym | Zeckendorff’s theorem |
Related topic | FibonacciSequence |
Related topic | UniquenessOfDigitalRepresentation |
Defines | Zeckendorf representation |
Defines | Fibonacci base |
Defines | Fibonacci coding |