Fibonacci numbers in O(lgn) steps
1.1 Matrix formulation for recursive calculation
1.2 At most log2n multiplications needed size z <= log2n
This can be extended to any recursive formula.
2.1 Given the formula
2.2 If we start with the ansatz for either of the two sequences, un and vn, that compose Fn
2.3 This yields two distinct roots
2.4 The two roots individually form two sequences, u and v, that are linearly independent. Thus Fibonacci numbers can be written in terms of these basis vectors.
2.5 The values of α and β can be evaluation by solving the linear systems, and eventually