Honsberger's Identity/Negative Indices
Theorem
Let $n \in \Z_{< 0}$ be a negative integer.
Let $F_n$ be the $n$th Fibonacci number (as extended to negative integers).
Then Honsberger's Identity:
- $F_{m + n} = F_{m - 1} F_n + F_m F_{n + 1}$
continues to hold, whether $m$ or $n$ are positive or negative.
Proof
The proof proceeds by induction.
For all $n \in \Z_{\le 0}$, let $\map P n$ be the proposition:
- $F_{m + n} = F_{m - 1} F_n + F_m F_{n + 1}$
This can equivalently be written:
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
- $F_{m - n} = F_{m - 1} F_{-n} + F_m F_{-n + 1}$
$\map P 0$ is the case:
\(\ds F_{m - 1} F_0 + F_m F_1\) | \(=\) | \(\ds F_m\) | Definition of Fibonacci Number: $F_0 = 0, F_1 = 1$ | |||||||||||
\(\ds \) | \(=\) | \(\ds F_{m + 0}\) |
Thus $\map P 0)$ is seen to hold.
Basis for the Induction
$\map P 1$ is the case:
\(\ds F_{m - 1} F_{-1} + F_m F_0\) | \(=\) | \(\ds F_{m - 1} F_{-1}\) | Definition of Fibonacci Number: $F_0 = 0$ | |||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - 1} \paren {-1}^0 F_1\) | Fibonacci Number with Negative Index | |||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - 1} F_1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - 1}\) | Definition of Fibonacci Number: $F_1 = 1$ |
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $\map P k$ and $\map P {k - 1}$ are true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
- $F_{m - k} = F_{m - 1} F_{-k} + F_m F_{-k + 1}$
and:
- $F_{m - \paren {k - 1} } = F_{m - 1} F_{-\paren {k - 1} } + F_m F_{-\paren {k - 1} + 1}$
from which it is to be shown that:
\(\ds F_{m - \paren {k + 1} }\) | \(=\) | \(\ds F_{m - 1} F_{-\paren {k + 1} } + F_m F_{-\paren {k + 1} + 1}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds F_{m - k - 1}\) | \(=\) | \(\ds F_{m - 1} F_{-k - 1} + F_m F_{-k}\) |
Induction Step
First we note that:
\(\ds F_{m - k}\) | \(=\) | \(\ds F_{m - 1} F_{-k} + F_m F_{-k + 1}\) | ||||||||||||
\(\ds \leadstoandfrom \ \ \) | \(\ds F_{m - k}\) | \(=\) | \(\ds F_{m - 1} F_{-k} + F_m F_{-\paren {k - 1} }\) |
and:
\(\ds F_{m - \paren {k - 1} }\) | \(=\) | \(\ds F_{m - 1} F_{-\paren {k - 1} } + F_m F_{-\paren {k - 1} + 1}\) | ||||||||||||
\(\ds \leadstoandfrom \ \ \) | \(\ds F_{m - k + 1}\) | \(=\) | \(\ds F_{m - 1} F_{-k + 1} + F_m F_{-k + 2}\) |
This is the induction step:
\(\ds F_{m - k - 1}\) | \(=\) | \(\ds F_{m - k + 1} - F_{m - k}\) | Definition of Fibonacci Number for Negative Index | |||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - \paren {k - 1} } - F_{m - k}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {F_{m - 1} F_{-\paren {k - 1} } + F_m F_{-\paren {k - 1} + 1} } - \paren {F_{m - 1} F_{-k} + F_m F_{-k + 1} }\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - 1} \paren {F_{-\paren {k - 1} } - F_{-k} } + F_m \paren {F_{-\paren {k - 1} + 1} - F_{-k + 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - 1} \paren {F_{-k + 1} - F_{-k} } + F_m \paren {F_{-k + 2} - F_{-k + 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_{m - 1} F_{-k - 1} + F_m F_{-k}\) | Definition of Fibonacci Number for Negative Index |
So $\map P k \land \map P {k - 1} \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall n \in \Z_{\le 0}: F_{m + n} = F_{m - 1} F_n + F_m F_{n + 1}$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $9$