Zeckendorf’s theorem

Theorem. Every positive integer can be represented as a sum of distinct non-consecutive Fibonacci numbersMathworldPlanetmath 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


where Zi is the ith element in Z. This ordered tuplet Z is the Zeckendorf representationMathworldPlanetmath 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


gives the sequenceMathworldPlanetmath 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
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