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: $F_0=1$, $F_1=1$ and $F_m=F_{m-2}+F_{m-1}$ for all $m>0$. 1 and 1 are not distinct even though the first is $F_0$ and the latter is $F_1$. We will consider two Fibonacci numbers $F_i$ and $F_j$ 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

$$\sum _{i=1}^k{Z}_i{F}_i=n,$$

where $Z_i$ is the $i$th 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, $F_8+F_6+F_4+F_1$. Furthermore, $Z=(1,0,1,0,1,0,0,1)$. We list the constituent elements in descending order from $Z_k$ to $Z_1$ 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

$$\sum _{i=1}^k{Z}_i{2}^{i-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.

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