Zeckendorf's Theorem

Theorem

Every positive integer has a unique representation as the sum of non-consecutive Fibonacci numbers.

More specifically, for all positive integers $n$, there exists some increasing sequence $\left\langle{ c_i }\right\rangle$ satisfying $c_i \geq 2$ and $c_{i + 1} > c_i + 1$ such that

$\displaystyle n = \sum_{i = 0}^k F_{c_i}$.

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

Proof

Existence

We will use induction on $n$.

Clearly we can represent $1$, $2$, and $3$ as a sum of non-consecutive Fibonacci numbers since they are themselves Fibonacci numbers. In addition $4 = 3 + 1$ also can be represented as desired.

Now suppose that each $n \leq k$ has a Fibonacci representation.

If $k + 1$ is a Fibonacci number, then obviously it has a Fibonacci representation, so we're done.

Otherwise, there is some $j$ where $F_j < k + 1 < F_{j + 1}$. Let's consider $a = k + 1 - F_j$. Since $a \leq k$, it must have a Fibonacci representation by the induction hypothesis. In addition, we have:

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

Thus the Fibonacci representation of $a$ does not contain $F_{j - 1}$, so we may simply represent $k + 1$ using the representation of $a$ plus $F_j$.

Thus we have shown by induction that there is some Fibonacci representation of every positive integer.

Uniqueness

Take two non-empty sets of distinct, non-consecutive Fibonacci numbers $S$ and $T$ that have the same sum - that is, take two different Fibonacci representations of the same number.

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, $S'$ and $T'$ must also have equal sums.

Assume that neither $S'$ nor $T'$ is empty. Let the largest element of $S'$ be $F_S$ and the largest element of $T'$ be $F_T$.

Since the sets $S'$ and $T'$ contain no common elements, $F_S \neq F_T$. WLOG let $F_S < F_T$.

From Sum of Non-Consecutive Fibonacci Numbers, we have that the sum of $S'$ is strictly less than $F_{S + 1}$ and thus strictly less than $F_T$, whereas the sum of $T'$ is clearly at least $F_T$. This is a contradiction, so it cannot have been the case that neither $S'$ nor $T'$ was empty.

WLOG 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 then $S' = T' = \varnothing$, so $S = T$ and the two Fibonacci representations must be the same.

Thus the Fibonacci representation is unique as desired.

$\blacksquare$

Source of Name

This entry was named for Edouard Zeckendorf.