TAOCP 1.2.8 Exercise 9
By exercise 8, the Fibonacci recurrence F_{n+2}=F_{n+1}+F_n is assumed to hold for all integers $n$.
Section 1.2.8: Fibonacci Numbers
Exercise 9. [M20] Using the conventions of exercise 8, determine whether Eqs. (4), (6), (14), and (15) still hold when the subscripts are allowed to be any integers.
Verified: no
Solve time: -
Solution
By exercise 8, the Fibonacci recurrence
$$ F_{n+2}=F_{n+1}+F_n $$
is assumed to hold for all integers $n$. We first determine the values for negative subscripts.
Taking $n=-1$ gives
$$ F_1=F_0+F_{-1}, $$
hence
$$ 1=0+F_{-1}, \qquad F_{-1}=1. $$
Taking $n=-2$ gives
$$ F_0=F_{-1}+F_{-2}, $$
hence
$$ 0=1+F_{-2}, \qquad F_{-2}=-1. $$
Continuing in this manner,
$$ F_{-3}=2,\qquad F_{-4}=-3, $$
which suggests
$$ F_{-n}=(-1)^{n+1}F_n. $$
We prove this formula by induction on $n\geq 0$. It holds for $n=0$, since
$$ F_0=0=(-1)^1F_0. $$
It holds for $n=1$, since
$$ F_{-1}=1=(-1)^2F_1. $$
Assume that for some $n\geq 1$,
$$ F_{-n}=(-1)^{n+1}F_n, \qquad F_{-(n-1)}=(-1)^nF_{n-1}. $$
Using the recurrence relation with index $-n$,
$$ F_{-(n+1)} = F_{-(n-1)}-F_{-n}. $$
Substituting the induction hypothesis gives
$$ F_{-(n+1)} = (-1)^nF_{n-1}-(-1)^{n+1}F_n = (-1)^n(F_{n-1}+F_n). $$
Since $F_{n+1}=F_n+F_{n-1}$,
$$ F_{-(n+1)} = (-1)^nF_{n+1} = (-1)^{(n+1)+1}F_{n+1}. $$
Thus
$$ F_{-n}=(-1)^{n+1}F_n \tag{A} $$
for all integers $n\geq 0$.
We now examine each equation.
For Eq. (4), let $n=-m$, where $m$ is a positive integer. Then
$$ F_{n+1}F_{n-1}-F_n^2 = F_{-(m-1)}F_{-(m+1)}-F_{-m}^2. $$
Using (A),
$$= (-1)^mF_{m-1}\cdot (-1)^{m+2}F_{m+1} - \left((-1)^{m+1}F_m\right)^2.$$
Since the exponents have the same parity,
$$= F_{m-1}F_{m+1}-F_m^2.$$
By Eq. (4) for positive indices,
$$= (-1)^m.$$
Because $n=-m$ and $(-1)^{-m}=(-1)^m$,
$$ F_{n+1}F_{n-1}-F_n^2 = (-1)^n. $$
Hence Eq. (4) remains valid for all integers $n$.
For Eq. (6), let $m,n$ be arbitrary integers. We must prove
$$ F_{n+m} = F_mF_{n+1}+F_{m-1}F_n. \tag{6} $$
Fix $m$ and define
$$ G_n = F_mF_{n+1}+F_{m-1}F_n. $$
Then
$$ G_{n+1} = F_mF_{n+2}+F_{m-1}F_{n+1} $$
and therefore
$$ G_{n+1} = F_m(F_{n+1}+F_n)+F_{m-1}F_{n+1} = (F_m+F_{m-1})F_{n+1}+F_mF_n. $$
Since $F_{m+1}=F_m+F_{m-1}$,
$$ G_{n+1} = F_{m+1}F_{n+1}+F_mF_n. $$
But this is exactly $G_n+G_{n-1}$, because
$$ G_{n-1} = F_mF_n+F_{m-1}F_{n-1}. $$
Thus $\langle G_n\rangle$ satisfies the Fibonacci recurrence. Furthermore,
$$ G_0 = F_mF_1+F_{m-1}F_0 = F_m, $$
and
$$ G_1 = F_mF_2+F_{m-1}F_1 = F_m+F_{m-1} = F_{m+1}. $$
Since both sequences $\langle G_n\rangle$ and $\langle F_{n+m}\rangle$ satisfy the same recurrence and agree for two consecutive values, they are identical for all integers $n$. Therefore Eq. (6) holds for arbitrary integer subscripts.
For Eq. (14),
$$ F_n=\frac{1}{\sqrt5}(\phi^n-\hat{\phi}^n), \tag{14} $$
the right-hand side satisfies the recurrence relation because
$$ \phi^{n+2} = \phi^{n+1}+\phi^n, \qquad \hat{\phi}^{,n+2} = \hat{\phi}^{,n+1}+\hat{\phi}^{,n}, $$
as $\phi$ and $\hat{\phi}$ are roots of
$$ x^2=x+1. $$
The formula is correct for
$$ n=0: \qquad \frac{1}{\sqrt5}(1-1)=0=F_0, $$
and for
$$ n=1: \qquad \frac{1}{\sqrt5}(\phi-\hat{\phi}) = 1 = F_1. $$
Hence Eq. (14) satisfies the defining recurrence and initial conditions for all integers $n$, positive or negative. Therefore Eq. (14) remains valid.
Finally consider Eq. (15):
$$ F_n = \phi^n/\sqrt5 \text{ rounded to the nearest integer.} \tag{15} $$
For $n\geq 0$, this was already proved in the text. Let $n=-m<0$, where $m>0$. By Eq. (14),
$$ F_{-m} = \frac{1}{\sqrt5} (\phi^{-m}-\hat{\phi}^{-m}). $$
Since
$$ \hat{\phi}=1-\phi=-\phi^{-1}, $$
we have
$$ \hat{\phi}^{-m} = (-1)^m\phi^m. $$
Hence
$$ F_{-m} = \frac{1}{\sqrt5} \left( \phi^{-m}-(-1)^m\phi^m \right). $$
If $m$ is odd,
$$ F_{-m} = \frac{1}{\sqrt5} (\phi^m+\phi^{-m}), $$
which differs from $\phi^{-m}/\sqrt5$ by more than $1/2$ for $m\geq 1$. For example,
$$ F_{-1}=1, \qquad \phi^{-1}/\sqrt5\approx 0.276. $$
If $m$ is even,
$$ F_{-m} = \frac{1}{\sqrt5} (\phi^{-m}-\phi^m), $$
which is negative, whereas $\phi^{-m}/\sqrt5$ is positive. For example,
$$ F_{-2}=-1, \qquad \phi^{-2}/\sqrt5\approx 0.171. $$
Thus Eq. (15) fails for negative subscripts.
In summary, Eqs. (4), (6), and (14) remain valid when subscripts are arbitrary integers, but Eq. (15) does not.
$$ \boxed{\text{(4), (6), (14) hold for all integers; (15) fails for negative } n.} $$