Skip to content

Recurrence relation

Describe a sequence one step at a time, solve a cash-balance recurrence, and see why initial conditions and deposit timing change the answer.

A recurrence relation is an equation that expresses a term of a sequence using earlier terms. In quant work, it turns a period-by-period rule—update a cash balance, propagate a model state, count admissible paths—into mathematics that can be computed and checked. The rule needs starting values, called initial conditions, to select a particular sequence. Brandt's recurrence notes introduce this distinction.

A balance sheet that advances one period

Consider a fictional account with 100 currency units initially. Each period, its opening balance grows by a stipulated 5%, then a deposit of 10 arrives at the end of the period. There are no fees, taxes, withdrawals or rounding during the calculation. Let BnB_n be the balance after nn complete periods and their deposits, so
B0=100,Bn+1=1.05Bn+10,n≥0.B_0=100,\qquad B_{n+1}=1.05B_n+10,\qquad n\geq 0.

Applying the rule gives

B1=1.05(100)+10=115,B2=1.05(115)+10=130.75,B3=1.05(130.75)+10=147.2875.\begin{aligned} B_1&=1.05(100)+10=115,\\ B_2&=1.05(115)+10=130.75,\\ B_3&=1.05(130.75)+10=147.2875. \end{aligned}

The recurrence is a compact statement of the accounting convention: the new deposit earns no growth in the period when it arrives. The 5% is an assumption of this deterministic example, not a prediction of market returns.

Change the timing to a deposit at the beginning of each period, and the equation becomes B~n+1=1.05(B~n+10)\widetilde B_{n+1}=1.05(\widetilde B_n+10), with the same initial 100 measured before the first deposit. Its first closing balance is 115.5, because the deposit also earns 5% that period. Parentheses encode a real economic difference.
A fictional cash balance starts at 100. With an end-period deposit it grows to 105 and then receives 10, closing at 115; with a beginning-period deposit it rises to 110 and then grows to 115.5. End-deposit balances at periods 0 to 3 are 100, 115, 130.75 and 147.2875; beginning-deposit balances are 100, 115.5, 131.775 and 148.86375.
A fictional cash balance starts at 100. With an end-period deposit it grows to 105 and then receives 10, closing at 115; with a beginning-period deposit it rises to 110 and then grows to 115.5. End-deposit balances at periods 0 to 3 are 100, 115, 130.75 and 147.2875; beginning-deposit balances are 100, 115.5, 131.775 and 148.86375.
Original deterministic comparison. Changing the order of the two operations changes the recurrence and every subsequent closing balance.

Unroll the rule to see every deposit

A closed form computes BnB_n directly from nn, without first computing all preceding balances. Repeated substitution reveals where each contribution comes from:
Bn=100(1.05)n+10∑j=0n−1(1.05)j=100(1.05)n+10(1.05)n−10.05.B_n=100(1.05)^n+10\sum_{j=0}^{n-1}(1.05)^j =100(1.05)^n+10\frac{(1.05)^n-1}{0.05}.
The initial 100 grows for nn periods. The deposits grow for n−1,n−2,…,0n-1,n-2,\ldots,0 periods; reversing their order gives the displayed geometric series. At n=0n=0, the sum is empty and equals zero. A finite geometric sum is valid here even though the growth factor exceeds one; convergence of an infinite series is a separate question.

More generally, for xn+1=axn+bx_{n+1}=ax_n+b with constant a,ba,b,

xn={anx0+ban−1a−1,a≠1,x0+nb,a=1.x_n=\begin{cases} a^nx_0+b\dfrac{a^n-1}{a-1},&a\ne 1,\\ x_0+nb,&a=1. \end{cases}
The a=1a=1 case needs its own expression: substituting it into the fraction would divide by zero. To verify a proposed formula, check both its initial value and that substituting it into the update equation works. Mathematical induction then establishes it for every nonnegative integer index.
For the finite-sum derivation and finance applications, see Series and the Geometric Series (public preview; full lesson requires membership).

Recognise the kind of recurrence

The balance equation is first order: only one earlier balance is needed. It is linear with constant coefficients and a nonhomogeneous term: the multiplier is constant and the added 10 is an external input. Removing that input gives the homogeneous equation Bn+1=1.05BnB_{n+1}=1.05B_n.
A second-order rule can need two starting values. For example, Fn+2=Fn+1+FnF_{n+2}=F_{n+1}+F_n needs both F0F_0 and F1F_1. For homogeneous linear recurrences with constant coefficients, characteristic roots provide a systematic solution method; repeated roots require additional polynomial factors, as Western's Theorem 4.38 illustrates. A combinatorial generating function offers another route by translating shifts in the sequence into algebra, while preserving the initial terms. Shor's notes work through that translation.
Not every recurrence is linear. The Catalan numbers satisfy C0=1C_0=1 and
Cn+1=∑k=0nCkCn−k,C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k},
which combines products of earlier counts rather than a fixed linear combination. NIST records this recurrence.
A recurrence also need not be deterministic. An autoregressive model adds random innovations and assumptions about their distribution and dependence. Its probabilistic interpretation cannot be inferred from an equation's visual resemblance to the cash-balance rule. Finally, a recurrence describes a mathematical relationship; programming recursion is one way to implement such a relationship. A loop can compute the same sequence.

Sources

Last updated
  • discrete mathematics
  • sequences
  • difference equations
  • cash flows
  • combinatorics
Keep connecting the ideas
← Back to the glossaryBack to top ↑