## Recurrence Relation

A mathematical relationship expressing as some combination of with . The solutions to linear recurrence can be computed straightforwardly, but Quadratic Recurrences are not so well understood. The sequence generated by a recurrence relation is called a Recurrence Sequence. Perhaps the most famous example of a recurrence relation is the one defining the Fibonacci Numbers,

for and with .

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Recurrence Relations and Clenshaw's Recurrence Formula.'' §5.5 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 172-178, 1992.