Recurrence Relation

A mathematical relationship expressing $f_n$ as some combination of $f_i$ with $i<n$. 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,

$$F_n=F_{n-2}+F_{n-1}$$

for $n\geq 3$ and with $F_1=F_2=1$.

See also Argument Addition Relation, Argument Multiplication Relation, Clenshaw Recurrence Formula, Quadratic Recurrence, Recurrence Sequence, Reflection Relation, Translation Relation

References

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.