4 Complements

4.1 Fast computation of the Fibonacci numbers

It is well known that a straightforward implementation of the recurrence formula leads to a very bad algorithm, whose complexity is big integer operations. On the other hand, combining with a fast exponentiation algorithm leads to a complexity in big floating point operations. In the (genuine) Fibonacci case, the fact that leads to the even simpler result :

We will see now that the former results can be used to obtain an algorithm whose complexity is big integer operations. The expansion Eq. 12 allows to consider only the (generalized) Fibonacci sequence. From Eq. 16, this specific sequence verifies :

leading to Algorithm 1, that describes a "divide and conquer" algorithm for computing a given Fibonacci number. Obviously, this algorithm must deal with pairs of consecutive Fibonacci numbers in order to be actually logarithmic [3].

4.2 Another sight over the duplication formulae

Another way to derive these divide and conquer formulae can be obtain when prooving :

Proposition 5  

Let and be respectively any solution of Eq. 4 and the associated Fibonacci sequence. Then, for all indices, we have :

Proof. Translated in terms of generating function, we obtain the easily checked :

em If we substitute in Proposition 5, both Eq. 19 and Eq. 20 turn into :

and lead again to Eq. 18 when taking and . In terms of generating function, this becomes :

Equating the coefficients of in this expression, this leads to :

Taking , we obtain what looks like a "linearization", but this doesn't contradicts the negative result stated in sub:Essentially-different-relations since the sum Eq. 24 doesn't involves a fixed number of terms. On the other hand, taking , then and substracting gives another proof of the well known Eq. 9.

4.3 The case

The special case has been escaped until here. Let us now describe how to deal with this special case. Concerning the generating finction, the substitution into Eq. 6 followed by a first order Taylor expansion in leads to  :

One can test afterwards the correctness of the process by recognizing the geometric sequence ... and the (generalized) Fibonacci sequence in the second term.

Applying the same method to the squared sequence, we obtain :

and similar results for and . The same happens with the even and odd series. For example : french

Therefore, , and , , have a different expression, in a different canonical basis, than in the case. But nevertheless, when expanding , in the , , basis the relation stated in thm:even-odd holds again. In fact, this theorem states that a sequence of polynomials in the are all vanishing, and this fact remains true by continuity when .