Zeckendorf's Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Every positive integer has a unique Zeckendorf representation.


That is: Let $n$ be a positive integer.

Then there exists a unique increasing sequence of integers $\left\langle{c_i}\right\rangle$ such that:

$\forall i \in \N: c_i \ge 2$
$c_{i + 1} > c_i + 1$
$\ds n = \sum_{i \mathop = 0}^k F_{c_i}$

where $F_m$ is the $m$th Fibonacci number.


For any given $n$, such a $\left\langle{c_i}\right\rangle$ is unique.


Proof

First note that every Fibonacci number $F_n$ is itself a Zeckendorf representation of itself, where the sequence $\left\langle{c_i}\right\rangle$ contains $1$ term.


Existence

We will use strong induction on $n$.

We have that:

$F_2 = 1$
$F_3 = 2$
$F_4 = 3$

so each of the integers $1$, $2$, and $3$ have a Zeckendorf representation.


Basis of the Induction

$4$ has the Zeckendorf representation:

$4 = 1 + 3 = F_2 + F_4$

This is the basis for the induction.


Induction Hypothesis

Let the induction hypothesis be that each $n \le k$ has a Zeckendorf representation.

The induction step remains to be proved: that $k + 1$ has a Zeckendorf representation.


Induction Step

If $k + 1$ is a Fibonacci number, then it is itself a Zeckendorf representation.

In that case, the induction step holds.


Suppose that $k + 1$ is not a Fibonacci number.

Then:

$\exists j \in \Z: F_j < k + 1 < F_{j + 1}$

Consider $a = k + 1 - F_j$.

Since $a \le k$, it must have a Zeckendorf representation by the induction hypothesis.

In addition:

\(\ds F_j + a\) \(=\) \(\ds k + 1\)
\(\ds \) \(<\) \(\ds F_{j + 1}\)
\(\ds \) \(=\) \(\ds F_j + F_{j - 1}\)
\(\ds a\) \(<\) \(\ds F_{j - 1}\)

Thus the Zeckendorf representation of $a$ does not contain $F_{j - 1}$.

Thus $k + 1$ has the Zeckendorf representation of $a + F_j$.

It follows by strong induction that for every positive integer there exists a Zeckendorf representation.

$\Box$


Uniqueness

Let $n \in \Z_{>0}$.

Aiming for a contradiction, suppose $S$ and $T$ are distinct Zeckendorf representation for $n$.


Consider $S' = S \setminus T$ and $T' = T \setminus S$, that is, each of the sets without their common elements.

Since $S$ and $T$ had equal sums:

$(1): \quad \ds \sum S' = \sum T'$

Without loss of generality, assume that $S'$ is empty.

Then in order for $T'$ to have the same sum using only positive integers, $T'$ must also be empty.

But as $S \ne T$, it follows that neither $S'$ nor $T'$ is empty.


Let the largest element of $S'$ be $F_S$.

Let the largest element of $T'$ be $F_T$.

Since $S'$ and $T'$ contain no common elements, $F_S \ne F_T$.

Without loss of generality, let $F_S < F_T$.

From Sum of Non-Consecutive Fibonacci Numbers:

$\ds \sum S' < F_{S + 1}$

and so:

$\ds \sum S' < F_T$

But from $(1)$:

$\ds \sum S' = \sum T'$

From this contradiction, it cannot be the case that $S'$ and $T'$ are non-empty.

So $S' = T' = \O$ and so $S = T$.

Thus the Zeckendorf representation is unique as desired.

$\blacksquare$


Source of Name

This entry was named for Edouard Zeckendorf.


Historical Note

Zeckendorf's Theorem appears to have been discovered in medieval India.

Edouard Zeckendorf rediscovered it in $1939$, but did not actually publish it until $1972$.

Cornelis Gerrit Lekkerkerker had in fact published it in $1952$, and named it after Zeckendorf at that time.

By the time Zeckendorf published his summary of this result in $1972$ several others had been referring to it as Zeckendorf's Theorem as a result of Lekkerkerker's article.

It is in fact a special case of a theorem by Alexander Markowich Ostrowski which had been published in $1922$.


Sources

  • 1952: C.G. Lekkerkerker: Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci (Simon Stevin Vol. 29: pp. 190 – 195)
Retrieved from "https://proofwiki.org/w/index.php?title=Zeckendorf%27s_Theorem&oldid=625166"