Zeckendorf's theorem

Zeckendorf's theorem states that every positive integer can be represented in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. More precisely, if N is any positive integer, there exist positive integers c_i ≥ 2, with c_{i + 1} > c_i + 1, such that

where F_n is the n^th Fibonacci number. Such a sum is called the Zeckendorf representation of N.

For example, the Zeckendorf representation of 100 is

100 = 89 + 8 + 3

There are other ways of representing 100 as the sum of Fibonacci numbers - for example

100 = 89 + 8 + 2 + 1

100 = 55 + 34 + 8 + 3

but these are not Zeckendorf representations because 1 and 2 are consecutive Fibonacci numbers, as are 34 and 55.

For any given positive integer, a representation that satisfies the conditions of Zeckendorf's theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage.

Proof of Zeckendorf's theorem

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 proved by induction. For n = 1, 2, 3 it is clearly true, for n = 4 we have 4 = 3 + 1. Now let each have a Zeckendorf's 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 it is a < k, a has a Zeckendorf representation; moreover F_j + a < F_{j + 1} then a < F_{j − 1} so the Zeckendorf representation of a does not contain F_{j − 1}. Then k + 1 can be represented as a + F_j. Moreover, it is obvious that each Zeckendorf representation corresponds to only one integer.

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 proved by induction on F_j.

Now take two non-empty sets of distinct non-consecutive Fibonacci numbers S and T which have the same sum. Eliminate common members to form two sets S' and T' with no members in common. We want to show that S' and T' are both empty i.e. that S=T.

First we show that at least one of S' and T' is empty. Assume the contrary i.e. that S' and T' are both non-empty. Let the largest member of S' be F_s and the largest member of T' be 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 means that S' and T' cannot have the same sum, and so S and T cannot have the same sum. So our assumption that S' and T' are both non-empty must be incorrect.

If S' is empty and T' is non-empty then S is a proper sub-set of T, and so S and T cannot have the same sum. Similarly we can eliminate the case where S' is non-empty and T' is empty. The only remaining case is that S' and T' are both empty, so S=T. We conclude that any two Zeckendorf representations that have the same sum must be identical (up to order).

[edit] Fibonacci multiplication

One can define the following operation on natural numbers a, b: given the Zeckendorf representations and we define the Fibonacci product .

For example, the Zeckendorf representation of 2 is F₃, and the Zeckendorf representation of 4 is F₄ + F₂ (F₁ is disallowed from representations), so .