Other Identities
There are numerous other identities which can be derived using various methods. Some of the most noteworthy are:
- (Catalan's identity)
- (Cassini's identity)
- (d'Ocagne's identity)
where Ln is the n'th Lucas Number. The last is an identity for doubling n; other identities of this type are
- by Cassini's identity.
These can be found experimentally using lattice reduction, and are useful in setting up the special number field sieve to factorize a Fibonacci number.
More generally,
of which a special case is
Doubling identities of this type can be used to calculate Fn using O(log n) long multiplication operations of size n bits. The number of bits of precision needed to perform each multiplication doubles at each step, so the performance is limited by the final multiplication; if the fast Schönhage–Strassen multiplication algorithm is used, this is O(n log n log log n) bit operations.
Read more about this topic: Fibonacci Numbers