|
Theorem. Every positive integer can be represented as a sum of distinct 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:  ,  and
 for all  . 1 and 1 are not distinct even though the first is  and the latter is  .
A consequence of the theorem is that for every positive integer  there is a unique ordered tuplet  consisting of  elements, all 0s or 1s, such that
where  is the  th element in  . This ordered tuplet  is the Zeckendorf representation of  , or we might even say the Fibonacci base representation of  (or the Fibonacci coding of  ).
So for example, 53 = 34 + 13 + 5 + 1, that is,
 . Furthermore,
 . We list the constituent elements in descending order from  to  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
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.
- 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
|
