Here's another interesting formula for finding fibonacci numbers, this one using only f
n-1 and n:
f
n = (f
n-1 + sqrt(5f
n-12 - 4(-1)
n)/2
With f
0 defined as 0.
The derivation for this is fairly straightforward.
First, it needs to be shown that f
n+1f
n-1 - f
n2 = (-1)
n for all n, without using the function above. It's easy to establish that for n=1, 1*0 - 1*1 = -1 = (-1)
1. Since f
n+1 = f
n-1 + f
n, f
n+1f
n-1 - f
n2 is equivalent to f
n-12 + f
nf
n-1 - f
n2, which equals f
n(f
n-1 - f
n) + f
n-12. Replacing f
n-1-f
n with -f
n-2 gives f
n-12 - f
nf
n-2. In other words, letting g(n) = f
n+1f
n-1 - f
n2, g(n) = -g(n-1), and so by
induction on n, g(n) = (-1)
n for all
natural numbers n.
Since f
n+1 = f
n + f
n-1, f
n-1(f
n + f
n-1) - f
n2 = (-1)
n by the equation above. Simplifying to get everything on one side yields: f
n2 - f
n-1f
n - f
n-12 + (-1)
n = 0. Using the
quadratic formula on that gives the equation for f
n in terms of f
n-1 and n.
This formula makes the relation between the fibonacci numbers and the
golden mean very apparent without actually using the golden mean at any point, which seemed pretty interesting to me when I first learned of it.