TAOCP 1.2.8 Exercise 17
Using the conventions of exercise 8, Fibonacci numbers are extended to all integer subscripts.
Section 1.2.8: Fibonacci Numbers
Exercise 17. [M24] Using the conventions of exercise 8, prove the following generalization of Eq. (4):
$$ F_{n+k}F_{m-k} - F_nF_m = (-1)^n F_{m-n-k}F_k. $$
Verified: yes
Solve time: 44s
Solution
Using the conventions of exercise 8, Fibonacci numbers are extended to all integer subscripts. In particular,
$$ F_{-r}=(-1)^{r+1}F_r . $$
Apply Eq. (6) with $m=k$ and $n$ replaced by $n$:
$$ F_{n+k}=F_kF_{n+1}+F_{k-1}F_n. $$
Similarly,
$$ F_m=F_kF_{m-k+1}+F_{k-1}F_{m-k}. $$
Hence
$$ \begin{aligned} F_{n+k}F_{m-k}-F_nF_m &=(F_kF_{n+1}+F_{k-1}F_n)F_{m-k} \ &\qquad -F_n(F_kF_{m-k+1}+F_{k-1}F_{m-k}) \ &=F_k\bigl(F_{n+1}F_{m-k}-F_nF_{m-k+1}\bigr). \end{aligned} $$
Therefore it suffices to evaluate
$$ F_{n+1}F_{m-k}-F_nF_{m-k+1}. $$
Cassini's identity (4) is the special case $m=n+1$ of the more general identity
$$ F_aF_{b-1}-F_{a-1}F_b=(-1)^bF_{a-b}, $$
which follows directly from Eq. (14). Indeed,
$$ \begin{aligned} F_aF_{b-1}-F_{a-1}F_b &=\frac1{5} \Bigl[ (\phi^a-\hat\phi^a)(\phi^{,b-1}-\hat\phi^{,b-1}) \ &\qquad -(\phi^{,a-1}-\hat\phi^{,a-1})(\phi^b-\hat\phi^b) \Bigr]. \end{aligned} $$
The terms $\phi^{a+b-1}$ and $\hat\phi^{,a+b-1}$ cancel, leaving
$$ \frac1{5} \left( -\phi^a\hat\phi^{,b-1} -\hat\phi^a\phi^{,b-1} +\phi^{,a-1}\hat\phi^b +\hat\phi^{,a-1}\phi^b \right). $$
Since $\phi\hat\phi=-1$,
$$ \begin{aligned} F_aF_{b-1}-F_{a-1}F_b &=\frac1{5} (-1)^{,b-1} (\phi-\hat\phi) \bigl(\phi^{a-b}-\hat\phi^{,a-b}\bigr) \ &=(-1)^b \frac{\phi^{a-b}-\hat\phi^{,a-b}}{\sqrt5} \ &=(-1)^bF_{a-b}. \end{aligned} $$
Now set
$$ a=m-k+1,\qquad b=n+1. $$
Then
$$ F_{m-k+1}F_n-F_{m-k}F_{n+1} =(-1)^{n+1}F_{m-k-n}. $$
Multiplying by $-1$,
$$ F_{n+1}F_{m-k}-F_nF_{m-k+1} =(-1)^nF_{m-n-k}. $$
Substituting into the earlier reduction gives
$$ F_{n+k}F_{m-k}-F_nF_m = F_k\bigl((-1)^nF_{m-n-k}\bigr). $$
Therefore
$$ \boxed{ F_{n+k}F_{m-k}-F_nF_m = (-1)^nF_{m-n-k}F_k }. $$
This completes the proof.
∎