PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (195)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof that the Zeckendorf representation of a positive integer is unique (Proof)

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

Before proving the theorem, it's necessary to prove a related lemma.

Lemma. If

$\displaystyle \sum_{i = 1}^k {Z_i F_i}$
is a Zeckendorf representation of a positive integer $ n$, and $ Z_k \neq 0$, then $ n < F_{k + 1}$.
Proof. (B. M. Scott) The proof is by induction on $ k$. For $ k = 1$, the only Zeckendorf representation is $ F_1 = 1$, and $ 1 < F_2 = 2$. Now suppose that $ m > 1$ and that the lemma is true for all $ k < m$, and assign
$\displaystyle \sum_{i = 1}^m {Z_i F_i}$
, with $ Z_m \neq 0$ as a Zeckendorf representation of some integer $ n$. Assign
$\displaystyle p = \sum_{i=1}^{m - 1} {Z_i F_i}.$
 Then either $ p = 0$, or
$\displaystyle \sum_{i = 1}^{m - 1} {Z_i F_i}$
is a Zeckendorf representation whose largest non-zero term is $ F_j$ for some $ j < m - 1$. If $ p = 0$, then $ n = F_m < F_{m + 1}$. Otherwise it follows from the induction hypothesis that $ p < F_{m - 1}$, whence $ n = p + F_m < F_{m + 1} + F_m = F_{m + 1}$, as desired. $ \qedsymbol$

With this lemma we can now proceed to prove the theorem.

Proof. (B. M. Scott) Suppose that
$\displaystyle \sum_{i = 1}^k {Z_i F_i}$
and
$\displaystyle \sum_{i = 1}^m {Y_i F_i}$
are distinct Zeckendorf representations of the same positive integer $ n$. Without loss of generality, we may assume that $ k \leq m$. If $ k < m$, assign $ Z_i = 0$ for $ i = k + 1, \ldots, m$, so that both representations are of the same length $ m$.

Since the two representations are distinct, we can choose $ j$ to be the largest index such that $ Y_j \neq Z_j$; without loss of generality assume that $ Y_j = 1$ and $ Z_j = 0$. If $ j < m$, then

$\displaystyle p = \sum_{i = j + 1}^m {F_i}$
; otherwise $ p = 0$. Then
$\displaystyle \sum_{i = 1}^j {Y_i F_i}$
and
$\displaystyle \sum{i = 1}^j {Z_i F_i}$
are distinct Zeckendorf representations of $ n - p$, and in particular these sums are equal.

Now $ Y_j = 1$, so

$\displaystyle \sum_{i = 1}^j {Y_i F_i} \geq F_j.$
 But $ Z_j = 0$, so by the lemma
$\displaystyle \sum_{i = 1}^j {Z_i F_i} < F_j.$
 This contradiction shows that the original representations must have been identical and hence that $ n$ has a unique Zeckendorf representation. $ \qedsymbol$



"proof that the Zeckendorf representation of a positive integer is unique" is owned by PrimeFan.
(view preamble)

View style:


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

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
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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