# 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.

## 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 |