Negafibonacci

Definition

In mathematics, negaFibonacci numbers are the negatively indexed elements of the Fibonacci sequence.

The negaFibonacci numbers are defined inductively by the recurrence relation:
*F_-1 = 1,
*F_-2 = -1,
*F_n = F_(n+2)−F_(n+1).

They may be defined by the formula F_−n = (−1)ⁿ⁺¹F_n.

The first 10 negaFibonacci numbers are F_-1 = 1, F_-2 = -1, F_-3 = 2, F_-4 = -3, F_-5 = 5, F_-6 = -8, F_-7 = 13, F_-8 = -21, F_-9 = 34, F_-10 = -55.

Integer representation

Any integer can be uniquely represented Fact|date=September 2007 as a sum of negaFibonacci numbers in which no two consecutive negaFibonacci numbers are used. For example:

* -11 = F_-4 + F_-6 = (-3) + (-8)
* 12 = F_-2 + F_-7 = (-1) + 13
* 24 = F_-1 + F_-4 + F_-6 + F_-9 = 1 + (-3) + (-8) + 34
* -43 = F_-2 + F_-7 + F_-10 = (-1) + 13 + (-55)
* 0 is represented by the empty sum.

Note that 0 = F_-1 + F_-2, 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 for coding numbers using a binary representation. In the string representing the integer "x", the "n"^th 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_-1 + F_-4 + F_-6 + F_-9. The integer "x" is represented by a string of odd length if and only if $x>0$.