Zeckendorf's Theorem - Proof

Proof

Zeckendorf's theorem has two parts:

1. Existence: every positive integer n has a Zeckendorf representation.
2. Uniqueness: no positive integer n has two different Zeckendorf representations.

The first part of Zeckendorf's theorem (existence) can be proven by induction. For n = 1, 2, 3 it is clearly true (as these are Fibonacci numbers), for n = 4 we have 4 = 3 + 1. Now suppose each n ≤ k has a Zeckendorf representation. If k + 1 is a Fibonacci number then we're done, else there exists j such that F_j < k + 1 < F_j + 1 . Now consider a = k + 1 − F_j . Since a ≤ k, a has a Zeckendorf representation (by the induction hypothesis). At the same time, F_j + a < F_j + 1 and since (by definition of Fibonacci numbers), a < F_j − 1, so the Zeckendorf representation of a does not contain F_j − 1 . As a result, k + 1 can be represented as the sum of F_j and the Zeckendorf representation of a.

The second part of Zeckendorf's theorem (uniqueness) requires the following lemma:

Lemma: The sum of any non-empty set of distinct, non-consecutive Fibonacci numbers whose largest member is F_j is strictly less than the next largest Fibonacci number F_j + 1 .

The lemma can be proven by induction on j.

Now take two non-empty sets of distinct non-consecutive Fibonacci numbers S and T which have the same sum. Consider sets S′ and T′ which are equal to S and T from which the common elements have been removed (i.e. S′ = S\T and T′ = T\S). Since S and T had equal sum, and we have removed exactly the elements from S T from both sets, S′ and T′ must have the same sum as well.

Now we will show by contradiction that at least one of S′ and T′ is empty. Assume the contrary, i.e. that S′ and T′ are both non-empty and let the largest member of S′ be F_s and the largest member of T′ be F_t. Because S′ and T′ contain no common elements, F_s ≠ F_t. Without loss of generality, suppose F_s < F_t. Then by the lemma, the sum of S′ is strictly less than F_s + 1 and so is strictly less than F_t, whereas the sum of T′ is clearly at least F_t. This contradicts the fact that S′ and T′ have the same sum, and we can conclude that either S′ and T′ must be empty.

Now assume (again without loss of generality) that S′ is empty. Then S′ has sum 0, and so must T′. But since T′ can only contain positive integers, it must be empty too. To conclude: S′ = T′ = which implies S = T, proving that each Zeckendorf representation is unique.