Vajda's Identity/Formulation 2
Jump to navigation
Jump to search
Theorem
Let $F_n$ be the $n$th Fibonacci number.
Then:
- $F_{n + k} F_{m - k} - F_n F_m = \left({-1}\right)^n F_{m - n - k} F_k$
Proof
We have:
\(\text {(1)}: \quad\) | \(\ds \) | \(\) | \(\ds \left({x^{n + k} - y^{n + k} }\right) \left({x^{m - k} - y^{m - k} }\right) - \left({x^n - y^n}\right) \left({x^m - y^m}\right)\) | |||||||||||
\(\ds \) | \(=\) | \(\ds x^{n + m} + y^{n + m} - x^{m - k} y^{n + k} - x^{n + k} y^{m - k} - x^{n + m} - y^{n + m} + x^n y^m + x^m y^n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x^n y^m + x^m y^n - x^{m - k} y^{n + k} - x^{n + k} y^{m - k}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x^n y^n \left({y^{m - n} + x^{m - n} - x^{m - n - k} y^k - x^k y^{m - n - k} }\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x^n y^n \left({x^{m - n - k} \left({x^k - y^k}\right) - y^{m - n - k} \left({x^k - y^k}\right)}\right)\) | ||||||||||||
\(\text {(2)}: \quad\) | \(\ds \) | \(=\) | \(\ds \left({x y}\right)^n \left({x^{m - n - k} - y^{m - n - k} }\right) \left({x^k - y^k}\right)\) |
Now substitute:
\(\ds x\) | \(=\) | \(\ds \phi\) | ||||||||||||
\(\ds y\) | \(=\) | \(\ds \hat \phi\) |
where:
- $\phi$ denotes the golden mean
- $\hat \phi = 1 - \phi$
first into $(2)$:
\(\ds \) | \(\) | \(\ds \left({\phi \hat \phi}\right)^n \left({\phi^{m - n - k} - \hat \phi^{m - n - k} }\right) \left({\phi^k - \hat \phi^k}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left({-1}\right)^n \left({\phi^{m - n - k} - \hat \phi^{m - n - k} }\right) \left({\phi^k - \hat \phi^k}\right)\) | Reciprocal Form of One Minus Golden Mean: $\hat \phi = -\dfrac 1 \phi$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \left({-1}\right)^n F_{m - n - k} F_k \times \left({\sqrt 5}\right)^2\) | Euler-Binet Formula |
and then into $(1)$:
\(\ds \) | \(\) | \(\ds \left({\phi^{n + k} - \hat \phi^{n + k} }\right) \left({\phi^{m - k} - \hat \phi^{m - k} }\right) - \left({\phi^n - \hat \phi^n}\right) \left({\phi^m - \hat \phi^m}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_{n + k} F_{m - k} - F_n F_m \times \left({\sqrt 5}\right)^2\) | Euler-Binet Formula |
$(1) = (2)$ and hence the result.
$\blacksquare$
Source of Name
This entry was named for Steven Vajda.
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 $17$