In mathematics, Zeckendorf's theorem, named after Belgian amateur 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 is any positive integer, there exist positive integers , with , such that where is the th Fibonacci number. Such a sum is called the Zeckendorf representation of . The Fibonacci coding of can be derived from its Zeckendorf representation. For example, the Zeckendorf representation of 64 is . There are other ways of representing 64 as the sum of Fibonacci numbers but these are not Zeckendorf representations because 34 and 21 are consecutive Fibonacci numbers, as are 5 and 3. For any given positive integer, its Zeckendorf representation can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. History 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. Proof Zeckendorf's theorem has two parts: Existence: every positive integer has a Zeckendorf representation. Uniqueness: no positive integer has two different Zeckendorf representations. The first part of Zeckendorf's theorem (existence) can be proven by induction. For it is clearly true (as these are Fibonacci numbers), for we have . If is a Fibonacci number then we're done. Else there exists such that . Now suppose each positive integer has a Zeckendorf representation (induction hypothesis) and consider . Since , has a Zeckendorf representation by the induction hypothesis. At the same time, (we apply the definition of Fibonacci number in the last equality), so the Zeckendorf representation of does not contain , and hence also does not contain . As a result, can be represented as the sum of and the Zeckendorf representation of , such that the Fibonacci numbers involved in the sum are distinct. 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 is strictly less than the next larger Fibonacci number . The lemma can be proven by induction on .