I recently read an article about difference equations and found the solution of the fibonacci recurence there. It is this function:
$f(n) = \frac{1}{\sqrt5}\left (\frac{1+\sqrt5}{2} \right )^{n}- \frac{1}{\sqrt5}\left (\frac{1-\sqrt5}{2} \right )$
My question is this: On programming contests you can come up with some recurence relations for the problems. If you find the satisfying function can you use it to gain on speed or memory due eliminating the recursive calls? Can we always find the desired function given its recursive definition and base cases? Is there a point to solve this at programming contests? I will be thankful if you suggest any good literature to read more about this. My question is somewhat programming oriented but i couldn't write the equation on stackoverflow so i hope its not a problem i posted it here. Thanks.