Everybody knows and loves the Fibonacci Sequence, right?
How F_{0} = 0, F_{1} = 1,
and F_{n} = F_{n1} + F_{n2} 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^{0+}}? 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 leftbrain and rightbrain, art and science that exists in Mathematics. And
we get to crunch out zillions of beautiful Fibonacci numbers.
Iterated Fibonacci Sequence 

