Zeckendorf with Negative Fibonacci Numbers

fibonacci-numbers

Zeckendorf : Every positive integer N can be expressed uniquely as a sum of distinct non-consecutive Fibonacci numbers

I was wondering if this theorem can be applied with the extended Fibonacci numbers, and especially I am looking for a way to find the Zeckendorf-like representation of $ N $, with Fibonacci numbers $ F_n $ having only negative indexes. (First for $ N \in \mathbb{N} $ then maybe $ N \in \mathbb{Z} $)

Mathworld states that this theorem only applies on positive numbers but do not says if Fibonacci numbers can be negative.
Online Zeckendorf Representation pages show positive indexes only and mostly use Binet's formula.

I've read that Binet's formula can be applied to generalized Fibonacci numbers (Proof), but it does not prove that Zeckendorf theorem can be used as well.

EDIT : I missed a paragraph in this Wikipedia page called Representation with Negafibonacci numbers that states this Zeckendorf-like representation exists and is unique. I probably can use NegaFibonacci coding method to find the indexes.

Best Answer

The negative fibbonacci numbers run as $F(-n)=F(n)$ for odd $n$ and $F(-n)=-F(n)$ for even $n$.

So we get for fibonacci numbers

 -21  13  -8   5  -3   2  -1   1
                          -1
                  -3           1
                  -3
                  -3      -1
          -8           2       1
          -8           2
          -8       t0 12
  -21          5       2       1
  -21     -8       -3     -1

So yes, all of the natural numbers can be expressed as a sum of non-consecutive fibonacci numbers of negative index.

It ought be a straight-forward conversion from the positive to negative schema.

  eg  -21            5     2      1
       21           -5    -2     -1
           13   8   -5    -2    -1
           13           3 -2     -1
           13

It's possible to go both ways, and there is a carry rule to prevent adjacent columns being filled with more than one counter.

Related Question