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.