Zeckendorf's Theorem

From ProofWiki
Jump to navigation Jump to search


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$
$\displaystyle 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.


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.


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.


$\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:

\(\displaystyle F_j + a\) \(=\) \(\displaystyle k + 1\)
\(\displaystyle \) \(<\) \(\displaystyle F_{j + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle F_j + F_{j - 1}\)
\(\displaystyle a\) \(<\) \(\displaystyle 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.



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 \displaystyle \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:

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

and so:

$\displaystyle \sum S' < F_T$

But from $(1)$:

$\displaystyle \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.


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$.


  • 1952: C.G. LekkerkerkerVoorstelling van natuurlijke getallen door een som van getallen van Fibonacci (Simon Stevin Vol. 29: pp. 190 – 195)