TAOCP 1.2.8 Exercise 8
We extend the Fibonacci sequence to negative indices by the recurrence F_{n+2} = F_{n+1} + F_n for all integers $n$.
Section 1.2.8: Fibonacci Numbers
Exercise 8. [15] In many cases it is convenient to define $F_n$ for negative $n$, by assuming that $F_{n+2}=F_{n+1}+F_n$ for all integers $n$. Explore this possibility: What is $F_{-1}$? What is $F_{-2}$? Can $F_{-n}$ be expressed in a simple way in terms of $F_n$?
Verified: no
Solve time: -
Solution
We extend the Fibonacci sequence to negative indices by the recurrence
$$ F_{n+2} = F_{n+1} + F_n $$
for all integers $n$. To find $F_{-1}$, set $n=-1$ in the recurrence:
$$ F_{1} = F_{0} + F_{-1}. $$
Since $F_0=0$ and $F_1=1$ by definition, we have
$$ 1 = 0 + F_{-1} \implies F_{-1} = 1. $$
Next, set $n=-2$ to find $F_{-2}$:
$$ F_0 = F_{-1} + F_{-2}. $$
Substituting $F_0=0$ and $F_{-1}=1$ gives
$$ 0 = 1 + F_{-2} \implies F_{-2} = -1. $$
Continuing in this manner, we can compute a few more terms:
$$ F_{-3} = F_{-1} - F_{-2} = 1 - (-1) = 2, $$
$$ F_{-4} = F_{-2} - F_{-3} = -1 - 2 = -3, $$
$$ F_{-5} = F_{-3} - F_{-4} = 2 - (-3) = 5. $$
Observing the pattern, we see that
$$ F_{-n} = (-1)^{,n+1} F_n $$
for all positive integers $n$. This formula can be proved by induction. For the base case $n=1$, we have $F_{-1} = 1 = (-1)^2 F_1$, and for $n=2$, $F_{-2} = -1 = (-1)^3 F_2$. Assume the formula holds for $n=k$ and $n=k-1$, then
$$ F_{-(k+1)} = F_{-(k-1)} - F_{-k} = (-1)^{k} F_{k-1} - (-1)^{k+1} F_k = (-1)^{k+2} F_{k+1}, $$
which confirms the induction step. Therefore the formula is valid for all positive integers $n$.
In conclusion, the negative-index Fibonacci numbers satisfy
$$ \boxed{F_{-1}=1, \quad F_{-2}=-1, \quad F_{-n}=(-1)^{,n+1}F_n \text{ for } n>0}. $$
This completes the proof.
∎