|
|
|
|
proof that the Zeckendorf representation of a positive integer is unique
|
(Proof)
|
|
|
Theorem. For any positive integer , the Zeckendorf representation (with elements all 0s or 1s) of is unique.
Before proving the theorem, it's necessary to prove a related lemma.
Lemma. If
is a Zeckendorf representation of a positive integer , and
, then
.
Proof. (B. M. Scott) The proof is by induction on  . For  , the only Zeckendorf representation is  , and
 . Now suppose that  and that the lemma is true for all  , and assign
, with
 as a Zeckendorf representation of some integer  . Assign
Then either  , or
is a Zeckendorf representation whose largest non-zero term is  for some  . If  , then
 . Otherwise it follows from the induction hypothesis that
 , whence
 , as desired. 
With this lemma we can now proceed to prove the theorem.
Proof. (B. M. Scott) Suppose that
and
are distinct Zeckendorf representations of the same positive integer  . Without loss of generality, we may assume that  . If  , assign  for
 , so that both representations are of the same length  .
Since the two representations are distinct, we can choose to be the largest index such that
; without loss of generality assume that and . If , then
; otherwise  . Then
and
are distinct Zeckendorf representations of  , and in particular these sums are equal.
Now , so
But  , so by the lemma
This contradiction shows that the original representations must have been identical and hence that  has a unique Zeckendorf representation. 
|
"proof that the Zeckendorf representation of a positive integer is unique" is owned by PrimeFan.
|
|
(view preamble)
Cross-references: contradiction, sums, without loss of generality, index, length, representations, induction hypothesis, term, induction, proof, necessary, Zeckendorf representation, integer, positive
This is version 3 of proof that the Zeckendorf representation of a positive integer is unique, born on 2007-01-23, modified 2007-10-15.
Object id is 8810, canonical name is ProofThatTheZeckendorfRepresentationOfAPositiveIntegerIsUnique.
Accessed 944 times total.
Classification:
| AMS MSC: | 11B39 (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
|
|
|
|
|
|
|
|
|
|
|