Recurrence Relations

A portfolio's value at the end of each month depends only on its value at the end of last month, plus that month's return. There's no need to re-derive the value from scratch each time using the entire history — you just need last month's number and this month's rule. That's the essence of a recurrence relation: a sequence defined not by a direct formula for the $n$-th term, but by a rule connecting each term to the ones just before it, plus a starting point. Recurrences are how compounding, backtests, and recursive algorithms are naturally described, and often the real work is converting a recurrence into a closed-form formula you can evaluate directly without looping through every prior step.

An analogy: a chain of dominoes

A recurrence relation is like a row of dominoes: knocking down domino $n$ depends entirely on domino $n-1$ having just fallen (and maybe $n-2$, if they're close enough to double-trigger). You don't need to know anything about domino 1 to predict domino 50's fate directly — you just need to know the rule connecting consecutive dominoes, plus where the row started. Compounding interest is the same: this month's balance is last month's balance times $(1+r)$, and that one local rule, applied repeatedly, determines the whole sequence.

The math, one piece at a time

A recurrence relation defines a sequence $a_n$ using earlier terms of the same sequence. The simplest useful kind quants meet is linear with constant coefficients, such as:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n),$$

where $a_n$ is the term you're solving for, $c_1, \ldots, c_k$ are fixed numbers, $a_{n-1}, \ldots, a_{n-k}$ are the $k$ previous terms the new term depends on, and $f(n)$ is an optional external "forcing" term that doesn't come from the sequence itself (like a fixed monthly deposit). In words: each new term is a weighted blend of a fixed number of the terms right before it, plus possibly some outside input. To actually compute values you also need initial conditions — enough starting terms ($a_0$, or $a_0$ and $a_1$, etc.) to seed the recursion; without them the relation alone has infinitely many possible sequences satisfying it.

Solving a recurrence means finding a closed form — a direct formula for $a_n$ in terms of $n$ alone, no recursion needed. For the simplest first-order case $a_n = r \cdot a_{n-1}$ with $a_0$ given, the closed form is $a_n = a_0 \, r^n$: each step multiplies by $r$ again, so after $n$ steps you've multiplied by $r$ a total of $n$ times.

Worked example 1: compounding by hand, recurrence vs. closed form

A $10,000 account earns 5% per year, recurrence: $a_n = 1.05 \, a_{n-1}$, $a_0 = 10{,}000$. Stepping through by hand: $a_1 = 10{,}500$, $a_2 = 11{,}025$, $a_3 = 11{,}576.25$. The closed form $a_n = 10{,}000 \times 1.05^n$ gives the same $a_3$ directly: $10{,}000 \times 1.157625 = 11{,}576.25$ — matching, but computed in one step instead of three, which matters enormously when $n$ is 30 years, not 3.

Worked example 2: the Fibonacci-style deposit sequence

Suppose a fund's monthly inflow follows $a_n = a_{n-1} + a_{n-2}$ (this month tracks the sum of the last two, a crude momentum rule), starting from $a_0 = 100$ and $a_1 = 150$ (units: $thousands). By hand: $a_2 = 250$, $a_3 = 400$, $a_4 = 650$, $a_5 = 1{,}050$. This is the Fibonacci recurrence with different starting values — it grows geometrically, at a rate approaching the golden ratio $\phi \approx 1.618$ per step, even though the rule only references the two immediately preceding terms.

What this means in practice

Recurrences are the natural way to describe anything that updates step by step: compounding returns, moving-average and EWMA filters (each new value blends the previous estimate with a new observation), backtest loops that carry state (inventory, cash, drawdown) forward one bar at a time, and dynamic-programming solutions to optimal-execution or option-pricing lattices. Recognizing a problem as a recurrence — "this value depends on the last one or two values plus a rule" — is often the first step to either writing a clean loop or, better, solving for a closed form that skips the loop entirely.