1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Wikipedia's page on Zeckendorf's theorem states that the result you seek is true. I think you can adapt the proof proposed on the webpage to the negative case (which is a simple inductive argument) $\endgroup$
    – GreginGre
    Dec 28, 2020 at 11:33
  • $\begingroup$ The Binet formula has another purpose than finding Zeckendorf Representations , namely to directly calculate $F_n$. (I am not the downvoter). If I understand the question right, you are looking for representations where negative indeces are allowed so we won't have uniqueness in general anymore, did I understand it right ? $\endgroup$
    – Peter
    Dec 28, 2020 at 11:38
  • $\begingroup$ OK, I found the Wikipedia paragraph, en.wikipedia.org/wiki/Zeckendorf%27s_theorem its source is not available anymore (I'm gonna check archives). I was mainly looking for the existence and the method to find it. $\endgroup$
    – Crypto
    Dec 28, 2020 at 11:53

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

This paper that proves the existence and shows a method

(we prove that) every integer can be represented uniquely as a sum of nonconsecutive Fibonacci numbers Fi where i < 0 and we specify an algorithm that leads to this representation

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .