Zeckendorf's Theorem - Representation With Negafibonacci Numbers

Representation With Negafibonacci Numbers

The Fibonacci sequence can be extended to negative index n using the re-arranged 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:

• −11 = F₋₄ + F₋₆ = (−3) + (−8)
• 12 = F₋₂ + F₋₇ = (−1) + 13
• 24 = F₋₁ + F₋₄ + F₋₆ + F₋₉ = 1 + (−3) + (−8) + 34
• −43 = F₋₂ + F₋₇ + F₋₁₀ = (−1) + 13 + (−55)
• 0 is represented by the empty sum.

Note that 0 = F₋₁ + F₋₂ , 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 x, the nth digit is 1 if F_n appears in the sum that represents x; 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 24 = F₋₁ + F₋₄ + F₋₆ + F₋₉ . The integer x is represented by a string of odd length if and only if x > 0.