I've always been a bit annoyed when a mathematical result is pulled out, in the middle of a slick argument, because it works. Sometimes this presentation is necessary, since the long, painful path to the result is not useful in and of itself. Often, though, slickness hides the fact that mathematics is a lot of messy work.
An example of these is the closed form for F(n), the nth Fibonacci number. Without even getting in to the controversy of what qualifies as a closed form, this result has the "feature" that F(n) is equal to the sum of two roots of the quadratic r^2 = r + 1, after you multiply them by a suitable coefficient.
Certainly this result can be proved by induction: a nice exercise in simple induction. But how would you ever dream of coming up with the conjecture in the first place? This week I gave an account of how you might find your way from the recursive expression for F(n), and its closed form.
Subscribe to:
Post Comments (Atom)
2 comments:
There is another pretty interesting way to derive the closed form formula for the Fibonacci numbers (presented in problem 24-15 in Spivak's Calculus 3rd edition). It goes something like this:
1. Show F(n+1)/F(n) <= 2
2. Let f(x) = Sigma(F(n)*x^(n-1), n=1, infinity). Prove it converges for abs(x) < 1/2
3. Prove that if abs(x) < 1/2 then f(x) = (-1)/(x^2 + x -1)
4. Obtain another power series for f by using the partial fraction decomposition of 1/(x^2 + x -1) and the power series for 1/(x-a)
Then the formula follows. Admittedly, this also has some of "pulling out of hat" feel to it; but it's a lot better than just showing the formula to someone, and magically proving it by induction. Someone with enough experience with infinite series might actually be able to come up with this process. And it has the advantage of not needing an induction proof (since it is not a guess).
Really great to see such a clear and well structured derivation of closed-form for Fibonacci nums, Danny.
Ah Spivak's Caculus text... that book blew me away (though I did not take mat157)
Post a Comment