What is the proper way to extend the Fibonacci numbers to negative numbers?

I have a feeling this question is a duplicate, but it's not coming up in "Questions that may already have your answer."

We all know very well that $F(0) = 0$, $F(1) = 1$ and $F(n) = F(n - 2) + F(n - 1)$ for all $n > 1$.

I'm wondering about $n < 0$. My first thought was $F(-n) = -F(n)$, which is appealing from a multiplicative point of view, as it seems to preserve certain identities, like $F(n)^2 = F(n - 1) F(n + 1) - (-1)^n$.

But it doesn't quite make sense from an additive point of view, it doesn't seem to work both "forwards" and "backwards." For example, it would give us $F(-1) + F(0) = -1 \neq F(1)$.

How do we extend $F(n)$ to negative $n$ so as to maintain both the related identities and the basic defining identity?

Solution 1:

$ \def\zz{\mathbb{Z}} \def\matrix#1{\left[\begin{array}{c}#1\end{array}\right]} $The recurrence relation $F_{n+2} = F_{n+1}+F_n$ for every $n \in \zz$ uniquely defines the sequence in both directions once you fix $F_0 = 0$ and $F_1 = 1$. Note that $F_{-1} = 1$.

Take any $n \in \zz$.

Then $\matrix{F_{n+1}\\F_n} = \matrix{1&1\\1&0} \matrix{F_n\\F_{n-1}}$ by the recurrence.

Thus $\matrix{F_{n+1}&F_n\\F_n&F_{n-1}} = \matrix{1&1\\1&0} \matrix{F_n&F_{n-1}\\F_{n-1}&F_{n-2}} = \matrix{1&1\\1&0}^n \matrix{F_1&F_0\\F_0&F_{-1}} = \matrix{1&1\\1&0}^n$.

(Note that the above is valid even for negative $n$. We just need one induction for positive $n$ and one more for negative $n$, along with the fact that $\matrix{1&1\\1&0}$ is invertible.)

Thus $F_{n+1} F_{n-1} - {F_n}^2 = \det\matrix{F_{n+1}&F_n\\F_n&F_{n-1}} = (-1)^n$.

It holds for any $n \in \zz$, contrary to your assumption that it would break down!

If matrices are new to you, see this explanation of the motivation and intuition behind matrices.

Solution 2:

From $F(n)=F(n-2)+F(n-1)$ it follows that $F(n-2)=F(n)-F(n-1)$ for any $n$, in other words (letting $n$ stand for $n+2$), $F(n) = F(n+2)-F(n+1)$. So $F(-1)=F(1)-F(0) = 1-0 = 1$, $F(-2) = F(0)-F(1) = 0-1 = -1$, and so on.

You will get $F(-n)=(-1)^{n+1}F(n)$, and all the algebraic properties that you know of the sequence should be preserved.

The whole two-sided sequence will be $(\ldots, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, \ldots)$.

Solution 3:

By now you know very well how to determine the Fibonacci numbers for negative indices, albeit by the recursion formula or the Binet formula as well as various others. My contribution is to show you what it looks like. The figure below is my crab-claw spiral; it consists of a Fibonacci spiral for $f_{-32}:f_{32}$. The image on the left is the complete spiral, that on the right is a detail at approximately $10^6$-fold zoom. The cusps are due to the alternating signs in the negative indices.

Solution 4:

For the benefit of those who haven't learned about matrices yet, here's a thought process to get at the answer by elementary means. Of course it's well recommended to learn about matrices, as that gives you greater certainty you've got the right answer.

You've already seen that $F_{-n} = -F_n$ is not the answer, because the recurrence then doesn't work as expected. (Notation note: for the rest of this answer, I'll use $n$ to mean a positive integer; of course $F_0 = 0$.)

What you need are alternating signs, so then for example you have $-13 + 8 = -5$ and $8 + (-5) = 3$. This would be $F_{-n} = (-1)^n F_n$. For identities like the one concerning $(F_{-n})^2$ that you mention, this gives the right results, e.g., $8^2 = (-13)(-5) - 1$.

But then we have a problem in the crossover to positive arguments, since then $F_{-1} = -1$ and then $F_1 = -1$ as well. That's fixed easily enough by having the signs alternate differently: $F_{-n} = (-1)^{n + 1} F_n$. Our earlier examples then become $13 + (-8) = 5$ and $-8 + 5 = -3$, and $(-8)^2 = 13 \times 5 - 1$. And more importantly, $F_{-1} = 1$, keeping $F_n$ familiarly positive.