Fibonacci tattoo!

From Pink Haired Girl, who I apparently share several mutual friends with: a tattoo to generate the Fibonacci sequence, in Scheme.

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² + 2F_k-1F_n+1F_n + F_k-2F_n²

Now, note that we get F_-2 = -1 , F_-1 = 1 , F₀ = 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² + 2F_n+1F_n.
Letting m+1 = n, we get
F_2m = F_m² + 2F_mF_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.