Two notes from Jiřì Matoušek‘s book *Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra *[1,2].

**Fibonacci numbers in O(lg***n*) steps

1.1 Matrix formulation for recursive calculation

1.2 At most log_{2}n multiplications needed size z <= log_{2}n

This can be extended to any recursive formula.

**Fibonacci formula**

2.1 Given the formula

2.2 If we start with the ansatz for either of the two sequences, u_{n} and v_{n}, that compose F_{n}

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

### Like this:

Like Loading...

*Related*

phantomfive

said:I wonder if a similar approach can be taken to other problems.

LikeLiked by 1 person

umayrh

said:Yes, I think it should at least work for recursive problems.

LikeLike

Pingback: Continued Fractions | Sketches, polytopes