Skip to main content

TL;DR

An equation that defines each term of a sequence as a function of preceding terms: \( a_n = f(a_{n-1}, a_{n-2}, \ldots) \) with initial conditions.

By Valenke Exam Prep Team·Last updated 2026-06-03

Recurrence Relation

An equation that defines each term of a sequence as a function of preceding terms: \( a_n = f(a_{n-1}, a_{n-2}, \ldots) \) with initial conditions.

Why it matters for interviews

Many interview problems reduce to setting up and solving recurrences: random walk probabilities, counting problems, dynamic programming. The ability to identify and solve recurrences is a core quant skill.

Definition and Mathematical Foundation

An equation that defines each term of a sequence as a function of preceding terms: \( a_n = f(a_{n-1}, a_{n-2}, \ldots) \) with initial conditions.

Application in Quantitative Finance

Many interview problems reduce to setting up and solving recurrences: random walk probabilities, counting problems, dynamic programming. The ability to identify and solve recurrences is a core quant skill.

Related Terms

Ready to practice for the Quant Trading Interview?

Adaptive practice powered by Item Response Theory targets your weak areas. Start with 3 free sessions.

Start free practice →

Frequently Asked Questions

How do you solve linear recurrences with constant coefficients?▼
Find the characteristic equation, compute its roots. If roots are \( r_1, r_2, \ldots \), the general solution is \( a_n = c_1 r_1^n + c_2 r_2^n + \cdots \). Repeated roots introduce polynomial factors \( n^k r^n \).
How do recurrences arise in probability?▼
Condition on the first step. For example, gambler's ruin: \( P(\text{ruin}|\text{wealth}=k) = \frac{1}{2}P(k+1) + \frac{1}{2}P(k-1) \). This second-order linear recurrence has a clean closed-form solution.
What is the connection to dynamic programming?▼
Dynamic programming solves optimization problems by breaking them into overlapping subproblems described by recurrences. The recurrence defines the value function, and memoization avoids redundant computation.