Zeckendorf's theorem
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 there is nothing to prove. Otherwise 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 . Now take two non-empty sets  and  of distinct non-consecutive Fibonacci numbers which have the same sum, . Consider sets  and  which are equal to  and  from which the common elements have been removed (i. e.  and ). Since  and  had equal sum, and we have removed exactly the elements from  from both sets,  and  must have the same sum as well, . Now we will show by contradiction that at least one of  and  is empty. Assume the contrary, i. e. that  and  are both non-empty and let the largest member of  be  and the largest member of  be . Because  and  contain no common elements, . Without loss of generality, suppose . Then by the lemma, , and, by the fact that ,  , whereas clearly . This contradicts the fact that  and  have the same sum, and we can conclude that either  or  must be empty. Now assume (again without loss of generality) that  is empty. Then  has sum 0, and so must . But since  can only contain positive integers, it must be empty too. To conclude:  which implies , proving that each Zeckendorf representation is unique. Fibonacci multiplication
One can define the following operation  on natural numbers , :  given the Zeckendorf representations
 and  we define the Fibonacci product 

For example, the Zeckendorf representation of 2 is , and the Zeckendorf representation of 4 is  ( is disallowed from representations), so 

(The product is not always in Zeckendorf form. For example, )

A simple rearrangement of sums shows that this is a commutative operation; however, Donald Knuth proved the surprising fact that this operation is also associative. Representation with negafibonacci numbers
The Fibonacci sequence can be extended to negative index  using the rearranged recurrence relation

which yields the sequence of "negafibonacci" numbers satisfying

Any integer can be uniquely represented as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:

 
 
 
 
 0 is represented by the empty sum. , for example, so the uniqueness of the representation does depend on the condition that no two consecutive negafibonacci numbers are used. This gives a system of coding integers, similar to the representation of Zeckendorf's theorem. In the string representing the integer , the th digit is 1 if  appears in the sum that represents ; that digit is 0 otherwise. For example, 24 may be represented by the string 100101001, which has the digit 1 in places 9, 6, 4, and 1, because . The integer  is represented by a string of odd length if and only if . See also
 Complete sequence
 Fibonacci coding
 Fibonacci nim
 Ostrowski numeration

References

External links

Zeckendorf's theorem at cut-the-knot

Fibonacci numbers
Theorems in number theory
Articles containing proofs