# Zeckendorf's Theorem

## 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)

- 1972: E. Zeckendorf:
*Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas*(*Bull. Soc. R. Sci. Liège***Vol. 41**: pp. 179 – 182)

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $34$