Fibonacci Numbers - Other Identities

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 L_n 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 F_n 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.