# proof that a Zeckendorf representation represents a unique positive integer

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

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

###### Proof.

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

$$c=\sum _{i=1}^{k}{Z}_{i}{F}_{i},$$ |

where ${F}_{x}$ is the $x$th Fibonacci number^{}. We can be assured that there is only one possible value for $c$ since all ${F}_{i}$ are distinct for $i>0$ and each ${F}_{i}$ was added only once or not at all, since each ${Z}_{i}$ is limited by definition to 0 or 1. Now $c$ holds the value of the Zeckendorf representation $Z$. If $c=a$, it follows that $$, but that would mean that $Z$ is not the Zeckendorf representation of $b$ after all, hence this results in a contradiction^{} of our initial assumption^{}. 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 |