Recurrence relation

A recurrence relation defines each term of a sequence using one or more earlier terms, often together with initial values that determine a particular sequence.

Sequence: An ordered list of objects, often numbers, indexed by positive integers or another set. A recurrence relation is a rule for generating terms of a sequence.
Linear recurrence relation: A recurrence in which each term is a linear combination of earlier terms, possibly plus a forcing term. Linearity makes many recurrence relations solvable using algebraic methods.
Fibonacci sequence: The sequence beginning 0, 1 in which each later term is the sum of the two preceding terms. Its defining rule is a familiar second-order recurrence.
Dynamic programming: An algorithmic method that solves problems by combining solutions to overlapping subproblems. A recurrence states how a problem's solution depends on smaller subproblems.
Explicit formula: A formula that gives a sequence term directly from its index without requiring earlier terms. It computes terms directly, unlike a recurrence that depends on prior values.
Initial condition: A specified value that selects a particular solution from a family of possible solutions. Initial values give a recurrence enough information to determine a specific sequence.
Homogeneous recurrence relation: A recurrence relation with no additive term independent of the sequence values. Homogeneous recurrences isolate the effects of the earlier terms.
Arithmetic progression: A sequence in which the difference between consecutive terms is constant. Adding a fixed difference at each step gives a first-order recurrence.
Divide-and-conquer algorithm: An algorithm that splits a problem into smaller subproblems, solves them, and combines their results. Recurrences describe the running time of recursive divide-and-conquer procedures.
Differential equation: An equation relating an unknown function to one or more of its derivatives. Differential equations describe continuous change, while recurrences describe stepwise change.

Linked from 31 pages