30
$\begingroup$

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?

$\endgroup$
  • 10
    $\begingroup$ I'd be tempted to use the Binet Formula and define $F(x)=\frac {(1+\sqrt 5)^x-(1-\sqrt 5)^x}{2^x\sqrt 5}$, but of course that sacrifices a lot of the properties you like. $\endgroup$ – lulu Aug 13 '16 at 21:47
  • 5
    $\begingroup$ See en.wikipedia.org/wiki/Fibonacci_number#Negafibonacci $\endgroup$ – aventurin Aug 13 '16 at 21:49
  • 5
    $\begingroup$ @lulu: Why does it "sacrifice a lot of the properties you like"? Nearly all the properties hold without change because of the matrix form for Fibonacci, including the one the asker wanted, as I show in my answer. Your formula holds too, because it is given by the recurrence which goes in both directions. $\endgroup$ – user21820 Aug 14 '16 at 3:11
  • 2
    $\begingroup$ Too lazy to search, but this seems like such a canonical question that there should be a million duplicates. $\endgroup$ – arctic tern Aug 14 '16 at 3:56
  • 2
    $\begingroup$ @user21820 Absolutely right. Lazily, I had just thrown the expression down and checked values. Which would have worked had my code actually been correct. As you remark, the algebra goes through just fine. $\endgroup$ – lulu Aug 14 '16 at 9:47
38
$\begingroup$

$ \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.

$\endgroup$
  • 1
    $\begingroup$ All other algebraic identities hold as well. For example compare the entries of the matrix on both sides of $\matrix{1&1\\1&0}^{2n} = \matrix{1&1\\1&0}^n \matrix{1&1\\1&0}^n$ to get $F_{2n+1} = {F_{n+1}}^2 + {F_n}^2$ and $F_{2n} = F_{n+1} F_n + F_n F_{n-1}$. $\endgroup$ – user21820 Aug 14 '16 at 3:21
  • 1
    $\begingroup$ Non-algebraic properties may not hold, such as terms being positive, which clearly fails for negative $n$. $\endgroup$ – user21820 Aug 14 '16 at 3:37
  • 1
    $\begingroup$ At least for the identity Dave mentioned, since $F_{n - 1}$ and $F_{n + 1}$ have (with only one exception) the same sign, they multiply to a positive number the same as ${F_n}^2$. $\endgroup$ – Robert Soupe Aug 14 '16 at 16:01
  • 1
    $\begingroup$ @RobertSoupe: If you're referring to the identity David mentioned, yes that is true, but the underlying reason that all algebraic identities hold is because the underlying recurrence is symmetric in both directions, and the sign flipping for Fibonacci sequence is quite coincidental and plays no actual role in the algebraic identities. For example if $F_0 = 3$ and $F_1 = 1$ we get different numbers on both sides, not just a sign change, but the method I've described here to obtain algebraic identities still work for both sides simultaneously. $\endgroup$ – user21820 Aug 14 '16 at 16:26
13
$\begingroup$

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)$.

$\endgroup$
10
+200
$\begingroup$

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.

Crab-claw Spiral

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

As @lulu mentions, one can produce a formula for the nth Fibonacci number known as Binet's Formula. If we let $\phi=\frac{1+\sqrt5}2$ be the golden ratio and $a_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt5}$, then it's easy to see that

$$a_{n+2}=a_{n+1}+a_n\forall n\in\mathbb R\\a_0=0,a_1=1$$

OLikewise, it is very direct that to see that

$$a_{-n}=\frac{\phi^{-n}-(-\phi)^n}{\sqrt5}=(-1)^{n+1}\frac{\phi^n-(-\phi)^{-n}}{\sqrt5}=(-1)^{n+1}a_n\forall n\in\mathbb R$$

Furthermore, this formula extends to non-integer values (though not nicely) and can be used to directly prove some formulas.

$\endgroup$
  • $\begingroup$ Actually, it's not at all difficult to do a non-integer, or even complex values, provided you have the software to handle it. Then $$a_n(z)=\frac{\varphi^z-\psi^z}{\varphi-\psi}$$ This is just the analytic continuation of the Binet formula. One example is what I call the other Fibonacci spiral, which can be found in the PDF linked in here: web.calstatela.edu/curvebank/waldman7/waldman7.htm. $\endgroup$ – Cye Waldman May 27 '17 at 22:29
  • $\begingroup$ Well, yes, but the results tend to be non-real. That's all I meant by that. $\endgroup$ – Simply Beautiful Art May 28 '17 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.