proof that a Zeckendorf representation represents a unique positive integer
Theorem. For any positive integer , the Zeckendorf representation (with elements all 0s or 1s) of is unique.
For our proof, we accept it as axiomatic that but is not used in the Zeckendorf representation of any number, and we also accept as axiomatic that all are distinct as long as .
Proof.
Assume that there are two integers and such that , yet they both have the same Zeckendorf representation with elements all 0s or 1s. We compute
where is the th Fibonacci number. We can be assured that there is only one possible value for since all are distinct for and each was added only once or not at all, since each is limited by definition to 0 or 1. Now holds the value of the Zeckendorf representation . If , it follows that , but that would mean that is not the Zeckendorf representation of after all, hence this results in a contradiction of our initial assumption. And if on the other hand and , then this leads to a similar contradiction as to what is the Zeckendorf representation of 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 |