What Is a Recurrence Relation? Defining Each Term From the Ones Before
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Some sequences are easiest to describe by saying how each term follows from earlier ones rather than by giving a formula for the term itself. That description is exact and useful, and converting it into a direct formula is a separate problem.
What the definition looks like
A recurrence has two parts and both are necessary. The rule states how a term is obtained from one or more previous terms, and the initial conditions state enough starting values for the rule to have something to work from. Together they determine every term, since applying the rule repeatedly generates the sequence indefinitely, and either part alone determines nothing. The order of a recurrence is how many previous terms the rule uses, so a rule referring to the single preceding term is first order and one referring to the two preceding terms is second order, which requires two starting values. Rules can be linear, where previous terms appear only multiplied by constants and added, or nonlinear, where they are multiplied together or otherwise combined, and the linear ones are far more tractable.
Where they turn up
The pattern of defining things in terms of smaller versions of themselves appears widely:
- •The Fibonacci sequence, where each term is the sum of the two before, which arises in counting problems about arrangements
- •Compound interest, where each year's balance is a multiple of the previous year's, which is a first order linear recurrence
- •Population models, where next season depends on this season, and where nonlinear versions produce chaotic behaviour
- •Counting problems generally, where the number of arrangements of a certain size is expressed using smaller sizes
- •The running time of recursive algorithms, which is described by a recurrence and solved to obtain the efficiency
- •Numerical methods, where a sequence of approximations converges on a solution
Turning one into a formula
A recurrence tells you how to compute the thousandth term by computing the nine hundred and ninety-nine before it, which is correct and inefficient, so obtaining a direct formula is worth the effort. For linear recurrences with constant coefficients there is a standard method, which assumes the solution has the form of a constant raised to the term number, substitutes that into the rule, and obtains a polynomial equation whose roots give the possible bases. The general solution combines those, with the initial conditions determining how much of each appears. Applied to the Fibonacci sequence this produces a closed formula involving the golden ratio, which is startling because the terms are all whole numbers and the formula is not. Generating functions provide a more general approach that handles cases the elementary method cannot, by encoding the whole sequence as a single object and manipulating it.
Recursion and the same idea
A recurrence in mathematics and a recursive function in programming are the same idea in different notation, and seeing the correspondence makes both clearer. A function that calls itself on a smaller input, with a base case that stops the descent, is exactly a rule plus initial conditions. The naive implementation of the Fibonacci sequence that way is famously inefficient, because it recomputes the same values enormously many times, and fixing it by storing results as they are computed converts an impractical algorithm into an instant one, which is the standard introduction to that technique. Working from the bottom up rather than the top down achieves the same thing. Analysing how long a recursive algorithm takes produces another recurrence, which then has to be solved, and the standard results for that are among the most used tools in the study of algorithms.
When they misbehave
Nonlinear recurrences are a different subject and produce behaviour that linear ones cannot. The simplest interesting case, a population model where next year's value depends on this year's multiplied by how much room is left, behaves completely differently depending on a single parameter, settling to a steady value for small values, oscillating between two values as it increases, then between four, then eight, with the transitions accelerating until the behaviour becomes aperiodic and unpredictable while remaining entirely deterministic. That route to chaos was a founding example of the field and is remarkable because the rule is about as simple as a rule can be while the behaviour is not describable by any formula. The transitions occur at ratios that turn out to be universal, appearing in completely unrelated systems, which is one of the more surprising results in mathematics.
The takeaway
A rule relating each term to earlier ones plus enough starting values determines a sequence completely, and neither part works alone. Compound interest, counting problems and the running time of recursive algorithms all take this form. Linear recurrences convert to direct formulas by a standard method, which for the Fibonacci sequence gives a formula built from the golden ratio. A very simple nonlinear one produces genuine chaos.