proof that a Zeckendorf representation represents a unique positive integer

Theorem. For any positive integer n, the Zeckendorf representationMathworldPlanetmath Z (with k elements all 0s or 1s) of n is unique.

For our proof, we accept it as axiomatic that F0=F1=1 but F0 is not used in the Zeckendorf representation of any number, and we also accept as axiomatic that all Fi are distinct as long as i>0.


Assume that there are two integers a and b such that 0<a<b, yet they both have the same Zeckendorf representation Z with k elements all 0s or 1s. We compute


where Fx is the xth Fibonacci numberMathworldPlanetmath. We can be assured that there is only one possible value for c since all Fi are distinct for i>0 and each Fi was added only once or not at all, since each Zi is limited by definition to 0 or 1. Now c holds the value of the Zeckendorf representation Z. If c=a, it follows that c<b, but that would mean that Z is not the Zeckendorf representation of b after all, hence this results in a contradictionMathworldPlanetmathPlanetmath of our initial assumptionPlanetmathPlanetmath. And if on the other hand c=b and c>a, then this leads to a similar contradiction as to what is the Zeckendorf representation of a really is. ∎

Title proof that a Zeckendorf representation represents a unique positive integer
Canonical name ProofThatAZeckendorfRepresentationRepresentsAUniquePositiveInteger
Date of creation 2013-03-22 16:36:46
Last modified on 2013-03-22 16:36:46
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 8
Author PrimeFan (13766)
Entry type Proof
Classification msc 11B39
Classification msc 11A63