There are faster algorithms to generated the Fibonacci sequence, but they obscure the recursive definition; her tattoo follows the simple recursive definition F

_{n}= F

_{n-1}+ F

_{n-2}, which takes O(n) arithmetic operations to compute F

_{n}. Wikipedia's article on Fibonacci numbers gives an identity

F

_{2n+k}= F

_{k}F

_{n+1}

^{2}+ 2F

_{k-1}F

_{n+1}F

_{n}+ F

_{k-2}F

_{n}

^{2}

Now, note that we get F

_{-2}= -1 , F

_{-1}= 1 , F

_{0}= 0 by running the recursion backwards. Letting k=1 gives

F

_{2n+1}= (2F

_{n+1}- F

_{n}) F

_{n}

and letting k=2 gives

F

_{2n+2}= F

_{n+1}

^{2}+ 2F

_{n+1}F

_{n}.

Letting m+1 = n, we get

F

_{2m}= F

_{m}

^{2}+ 2F

_{m}F

_{m-1}

= F

_{m}(F

_{m}+ 2F

_{m-1})

= F

_{m}(F

_{m+1}+ F

_{m-1}).

Thus we can express F

_{n}in terms of Fibonacci numbers of indices around n/2, and thus find Fibonacci numbers in logarithmic time... but that obscures the central fact about these numbers, which is the recursion that produces them. (There are probably other ways to arrange those identities that give more efficient algorithms than the one I'm alluding to, but I didn't try that hard.) There are also identities for F

_{n}in terms of Fibonacci numbers of index around n/3, for example -- see Wikipedia -- which could be even faster.

## 2 comments:

You can prove most of these identities by noting that the matrix:

[ 1 1 ]

[ 1 0 ]

raised to an integral power generates the Fibonacci numbers. You can then prove statements about F_2m by squaring matrices.

she totally hung out in our hammock tree

Post a Comment