Recurrence relations

The formula

x[n] = f( x[n−1], x[n−2], …, x[n−k] )

The general form: the next value is computed from the previous k values. Give it k starting values and it generates the whole sequence, one step at a time.

x[n] = a₁·x[n−1] + a₂·x[n−2] + … + a_k·x[n−k] + u[n]

The linear constant-coefficient case — the one you can actually solve. It is the discrete twin of a linear ODE: u[n] is the forcing input, the coefficients are the plant.

F(n) = F(n−1) + F(n−2),    F(0) = 0,  F(1) = 1

The Fibonacci sequence, the canonical example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

r^k = a₁·r^(k−1) + a₂·r^(k−2) + … + a_k

The characteristic equation. Guess x[n] = rⁿ, substitute, and the recurrence collapses to a polynomial. The roots decide everything: the general solution is x[n] = c₁·r₁ⁿ + c₂·r₂ⁿ + … for distinct roots, with the c's fixed by the initial conditions. A root repeated m times contributes the extra terms n·rⁿ, n²·rⁿ, …, n^(m−1)·rⁿ alongside rⁿ.

F(n) = (φⁿ − ψⁿ)/√5,    φ = (1+√5)/2 ≈ 1.6180,   ψ = (1−√5)/2 ≈ −0.6180

Binet's formula — the characteristic-root method applied to Fibonacci. Since |ψ| < 1, the second term dies out and F(n) is φⁿ/√5 rounded to the nearest integer; consecutive ratios converge to φ (F(20)/F(19) = 6765/4181 ≈ 1.618034).

all |rᵢ| < 1  →  decays to steady state       any |rᵢ| > 1  →  blows up

The stability rule. The unit circle plays the role the jω-axis plays for continuous systems.

Where you meet it

On the bench, inside the DAQ chain. Every first-order IIR smoother is the recurrence y[n] = (1−α)·y[n−1] + α·x[n] — the discretized RC filter. With α = 0.1 the pole sits at 0.9 and the effective time constant is −1/ln(0.9) ≈ 9.5 samples; after 22 samples a step input has reached 90% (1 − 0.9²² ≈ 0.9015). When someone asks why the displayed reading "lags," this recurrence is the answer.
On the test stand, in the discrete PID loop. The integrator term is the recurrence I[n] = I[n−1] + Ki·e[n]·Δt, and the whole controller is a difference equation clocked at the loop rate. Integrator windup, sample-rate sensitivity, and limit cycles are all recurrence behavior, not analog behavior.
In the algorithm review. The running time of a divide-and-conquer routine is a recurrence: mergesort obeys T(n) = 2·T(n/2) + n, which solves to n·log₂ n (T(1024) = 10,240 operations against 1,024 items). Binary search obeys T(n) = T(n/2) + 1 → 20 probes for a million-entry table. If a teammate's telemetry parser is quadratic, the recurrence is where you prove it before the flight-day data set does.
In the program review, wearing a dollar sign. A monthly account with contribution P and rate r per period obeys B[n+1] = (1+r)·B[n] + P. At 0.5% per month and $500 per month from zero, 120 iterations give $81,940 — same math as battery depletion per duty cycle and parts-count decay per half-life.

How it works

For linear constant-coefficient recurrences, the characteristic roots are a complete behavior dictionary. A real root in (0, 1) gives smooth decay. A root in (−1, 0) decays while alternating sign — the sample-to-sample chatter you see in a marginally tuned digital loop. A complex pair r = ρ·e^(±jθ) gives an oscillation at θ radians per sample inside an envelope of ρⁿ. A simple (non-repeated) root on the unit circle sustains forever; a repeated root there grows polynomially — x[n] = 2·x[n−1] − x[n−2] has a double root at r = 1, ramps linearly, and is exactly the discrete double integrator a test-stand control engineer meets at the margin. Outside the circle, any root grows without bound, and not slowly — a loop with an effective root of 1.01 multiplies by about 1,059 in 700 samples. The z-transform is the bookkeeping machine for all of this: it turns the recurrence into algebra, and the poles it hands you are exactly the characteristic roots.

An order-k recurrence needs k initial conditions, full stop. Hand a second-order difference equation one starting value and you haven't defined a sequence; you've defined a family of them. This is the discrete version of forgetting an initial condition on an ODE, and it shows up in code as an uninitialized filter state that rings for the first hundred samples of every run.

Three gotchas that bite working engineers:

A recurrence is a definition, not an algorithm. Coding Fibonacci as a naive recursive function evaluates F(n−1) and F(n−2) separately and does exponential work — the call count itself grows like φⁿ. Iterate forward or memoize and it's linear. The recurrence tells you what the sequence is; how you compute it is a separate decision.
Round-off recruits the dominant root. When a recurrence has a growing root and a decaying root, floating-point error injected at every step gets amplified by the growing one. Compute the decaying solution forward and it drowns; NIST's guidance is to run such recurrences backward instead ^[13]. The same effect kills closed forms: Binet's formula in double precision first rounds to the wrong integer at F(71), while integer iteration is exact forever.
The coefficients belong to the sample rate. Discretize a controller or filter at 1 kHz and the recurrence coefficients encode that Δt. Change the loop rate without recomputing them and the poles move — sometimes across the unit circle. A loop that was stable at 1 kHz can oscillate at 500 Hz with identical "gains." Retune on every rate change; it is not optional.

For the algorithm-analysis recurrences T(n) = a·T(n/b) + f(n), the master theorem is the lookup table: compare f(n) against n^(log_b a) and the larger term wins (they split the credit — an extra log factor — when they tie). It covers most divide-and-conquer code you'll ever review; the Akra–Bazzi method handles the stragglers.

The mistake people make with all of them is trusting a few iterations. Discrete systems can look docile for dozens of steps while a root barely outside the unit circle compounds; 1.01ⁿ is indistinguishable from flat until it isn't. Check the roots, not the plot.

History

The famous sequence is older than its name. Counting patterns obeying F(n) = F(n−1) + F(n−2) appear in Indian prosody centuries before Europe saw them — in the tradition following Pingala, with a clear statement attributed to Virahanka around the 8th century ^[1]^[3]. Europe met the sequence in 1202, when Leonardo of Pisa — called Fibonacci — published Liber Abaci, the book that carried Hindu-Arabic numerals into European commerce, and tucked into it a puzzle about breeding rabbit pairs whose monthly totals run 1, 2, 3, 5, 8, … ^[2]^[3]. Leonardo treated it as one exercise among hundreds; he never knew it would carry his name.

The machinery for solving recurrences came five centuries later. Abraham de Moivre introduced generating functions around 1730 precisely to crack linear recurrences, and obtained the closed form for Fibonacci-type sequences ^[4]^[5]. Daniel Bernoulli and Euler knew the result too, but the formula ended up named for Jacques Binet, who published it in 1843 ^[5]^[6]. The sequence itself got its modern name in the 1870s from Édouard Lucas, who traced it back to Leonardo's book while building his own theory of related sequences — the Lucas numbers — and his large-prime tests ^[7]^[8].

The engineering chapter is a 20th-century story. Witold Hurewicz's 1947 treatment of sampled-data systems — radar work — turned linear difference equations into a transform calculus, and in 1952 John Ragazzini and Lotfi Zadeh's sampled-data group at Columbia named it the z-transform ^[9]^[10]. Digital control and DSP have run on it since. On the computing side, Jon Bentley, Dorothea Haken, and James Saxe published the general method for divide-and-conquer recurrences in SIGACT News in 1980 ^[11]^[12]; the Introduction to Algorithms textbook later made "master theorem" the term every code review uses.

Related tools

/tools/rc-filter — the discretized RC filter is exactly the first-order recurrence y[n] = (1−α)·y[n−1] + α·x[n]
/tools/rc-charge-time — the continuous-time twin of the same first-order decay
/tools/half-life-decay — a geometric recurrence: each period multiplies the population by a fixed ratio

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →