Linear recurrence relations (or how to solve recursive sequences effectively)

This article will have quite a few equations but they are not as hard to follow as they look so bear with me. Every programmer has written a program that finds the nth Fibonacci number. Some of you did it with recursion, others went a step ahead and used dynamic programming. Still, even with dynamic ...