The Math Department

Everybody knows and loves the Fibonacci Sequence, right? How F₀ = 0, F₁ = 1, and F_n = F_n-1 + F_n-2 for all n thereafter? It gives us chills in the night just thinking about it, doesn't it?

Well, as it's so easy to compute the members of the sequence F_n, wouldn't it be a joy to find an easy recurrence for computing the members of the sequence {F_Fn, n in Z⁰⁺}? These numbers grow very big very quickly! And very big numbers make me very happy, especially when they're Fibonacci numbers!

This particular problem is actually a pretty good example of how rigor is useful in establishing a result, but you really need the intuition to see the result in the first place.

For you see, the method of tackling this particular problem is simple: first, formulate the result. Then prove it.

Sit in a quiet corner in the library somewhere and try and figure out what the recurrence should be. From there, it's actually easy to prove the problem! Here you see, intuition gives us the answer, where rigor formulates the question that our answer is to.

The proof justifying this result is rigorous, although it's merely a string of ugly algrabraic equalities. There's almost no way one could sit down and simply work out the algebra to the result, without knowing ahead of time what the result should work out to be, since the proof requires applying the Fibonacci iteration over and over to simplify the result. Hence we see illustrated again the harmony between rigor and intuition, the left-brain and right-brain, art and science that exists in Mathematics. And we get to crunch out zillions of beautiful Fibonacci numbers.

---

Iterated Fibonacci Sequence

DVI file

Adobe PDF file

---