PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof that a Zeckendorf representation represents a unique positive integer (Proof)

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 $0 < a < b$ , yet they both have the same Zeckendorf representation $Z$ with $k$ elements all 0s or 1s. We compute $$c = \sum_{i = 1}^k Z_iF_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 $c < b$ , 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. $ \qedsymbol$




"proof that a Zeckendorf representation represents a unique positive integer" is owned by PrimeFan.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: similar, contradiction, mean, Fibonacci number, number, axiomatic, proof, elements, Zeckendorf representation, integer, positive, theorem

This is version 5 of proof that a Zeckendorf representation represents a unique positive integer, born on 2007-01-23, modified 2009-11-22.
Object id is 8810, canonical name is ProofThatTheZeckendorfRepresentationOfAPositiveIntegerIsUnique.
Accessed 1562 times total.

Classification:
AMS MSC11B39 (Number theory :: Sequences and sets :: Fibonacci and Lucas numbers and polynomials and generalizations)
 11A63 (Number theory :: Elementary number theory :: Radix representation; digital problems)

Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)