Zeckendorf's theorem
Zeckendorf's theorem, named after Belgian mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers.
Zeckendorf's theorem states that every positive integer can be represented uniquely 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 ci ≥ 2, with ci + 1 > ci + 1, such that
where Fn is the nth Fibonacci number. Such a sum is called the Zeckendorf representation of N. The Fibonacci coding of N can be derived from its Zeckendorf representation.
For example, the Zeckendorf representation of 100 is
There are other ways of representing 100 as the sum of Fibonacci numbers – for example
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.
While the theorem is named after the eponymous author who published his paper in 1972, the same result had been published 20 years earlier by Gerrit Lekkerkerker. As such, the theorem is an example of Stigler's Law of Eponymy.
Zeckendorf's theorem has two parts:
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 Fj < k + 1 < Fj + 1 . Now consider a = k + 1 − Fj . Since a ≤ k, a has a Zeckendorf representation (by the induction hypothesis). At the same time, Fj + a < Fj + 1 and since Fj + 1 = Fj + Fj − 1 (by definition of Fibonacci numbers), a < Fj − 1, so the Zeckendorf representation of a does not contain Fj − 1 . As a result, k + 1 can be represented as the sum of Fj and the Zeckendorf representation of a.
...
Wikipedia