Recurrence Relations

Imagine you are trying to describe how something grows step by step: a population, an investment, the number of moves in a puzzle, or the running time of a computer program. Very often the cleanest way to describe the value at one step is not with a direct formula, but in terms of the values that came just before it. That self-referential description is a recurrence relation, and it is one of the most powerful bridges between simple rules and complex behavior in all of discrete mathematics.

A recurrence relation is essentially a rule that says "to get the next term, do this to the previous term(s)." What makes them fascinating is that a tiny, almost trivial-looking rule can generate sequences of astonishing richness — the Fibonacci numbers, the golden ratio, exponential explosions, and the exact cost of recursive algorithms all fall out of a single line of definition.

Learning Objectives

• Define a recurrence relation and distinguish the recurrence from its initial conditions
• Compute terms of a sequence given a recurrence and starting values
• Recognize and work with the Fibonacci recurrence and its origin
• Solve linear homogeneous recurrences using the characteristic equation
• Handle repeated roots and non-homogeneous recurrences at an introductory level
• Connect recurrences to the running time of recursive algorithms

Quick Answer

A recurrence relation defines each term of a sequence as a function of one or more earlier terms, together with initial conditions that anchor the sequence. For example, $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0,\ a_1 = 1$ generates the Fibonacci numbers. "Solving" a recurrence means finding a closed-form formula for $a_n$ that needs no previous terms. Linear homogeneous recurrences with constant coefficients are solved with the characteristic equation: turn the recurrence into a polynomial, find its roots, and combine exponential terms $r^n$. Recurrences also describe how much work a recursive algorithm does, making them a core tool in computer science.

Where It Came From

The story most people know starts in 1202, when the Italian mathematician Leonardo of Pisa — later nicknamed Fibonacci ("son of Bonacci") — published Liber Abaci ("The Book of Calculation"). His broader mission was urgent and practical: he had learned the Hindu-Arabic decimal system while traveling in North Africa, and he wanted to convince European merchants to abandon clumsy Roman numerals. To make his arithmetic lessons engaging, he posed puzzles. One became immortal.

Fibonacci's rabbit problem asks: suppose you start with one newly-born pair of rabbits. Each pair takes one month to mature, and every mature pair produces a new pair every month thereafter. Rabbits never die. How many pairs are there after $n$ months? Counting carefully, the number of pairs each month is $1, 1, 2, 3, 5, 8, 13, 21, \dots$ — each new count is the sum of the previous two, because every pair alive last month survives, and every pair that was mature (alive two months ago) produces a new pair. That single observation, "the total need is last month's total plus the newborns," is the first famous recurrence relation in Western mathematics.

The deeper motivation, though, is universal and predates Fibonacci: whenever a system's next state depends on its recent history, a recurrence is the natural language to describe it. Ancient Indian scholars such as Pingala (c. 200 BCE) and later Virahanka and Hemachandra had already encountered the same numbers while counting rhythmic patterns in Sanskrit poetry — how many ways to fill a line of a given length with short and long syllables. The systematic solving of recurrences came much later, developed by mathematicians like Abraham de Moivre and Leonhard Euler in the 1700s, who introduced the characteristic-equation method that turns a recurrence into ordinary algebra. In the 20th century, recurrences became indispensable in computer science for measuring how long recursive programs take to run.

Sequences Defined by Their Own Past

A recurrence relation has two essential ingredients, and forgetting either one leads to confusion:

1. The recurrence itself — the rule linking a term to earlier terms.
2. The initial conditions — enough starting values to get the rule going.

Consider $a_n = 2a_{n-1} + 3$. This rule alone does not determine a unique sequence; you must also say where it starts. If $a_0 = 1$:

$a_1 = 2(1) + 3 = 5$ $a_2 = 2(5) + 3 = 13$ $a_3 = 2(13) + 3 = 29$

giving $1, 5, 13, 29, 61, \dots$. But if instead $a_0 = 0$, the same rule produces $0, 3, 9, 21, 45, \dots$. A recurrence that refers back $k$ terms needs $k$ initial conditions.

The order of a recurrence is how many previous terms it uses. $a_n = 3a_{n-1}$ is first-order; the Fibonacci rule $a_n = a_{n-1} + a_{n-2}$ is second-order and therefore needs two starting values.

The Fibonacci Recurrence

The Fibonacci sequence is defined by

$F_n = F_{n-1} + F_{n-2}, \qquad F_0 = 0,\ F_1 = 1.$

Let us generate terms explicitly:

$F_2 = F_1 + F_0 = 1 + 0 = 1$ $F_3 = F_2 + F_1 = 1 + 1 = 2$ $F_4 = F_3 + F_2 = 2 + 1 = 3$ $F_5 = F_4 + F_3 = 3 + 2 = 5$ $F_6 = F_5 + F_4 = 5 + 3 = 8$

so the sequence is $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$.

A remarkable fact: the ratio of consecutive Fibonacci numbers approaches the golden ratio $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618$. For instance $\frac{34}{21} \approx 1.619$ and $\frac{55}{34} \approx 1.618$. This is not a coincidence — it emerges directly from solving the recurrence, which we do next.

Solving Linear Recurrences: The Characteristic Equation

A linear homogeneous recurrence with constant coefficients has the form

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k},$

where the $c_i$ are constants. "Homogeneous" means there is no extra term that does not involve the sequence (nothing like the $+3$ from earlier). "Solving" it means finding a closed formula for $a_n$.

The key insight, due to de Moivre and Euler, is to guess that solutions look like $a_n = r^n$ for some number $r$. Substituting $a_n = r^n$ into the recurrence and dividing by the lowest power gives a polynomial called the characteristic equation. Its roots tell you the building blocks of every solution.

Worked example: a second-order recurrence

Solve $a_n = a_{n-1} + 6a_{n-2}$ with $a_0 = 3,\ a_1 = 6$.

Step 1 — characteristic equation. Substitute $a_n = r^n$:

$r^n = r^{n-1} + 6r^{n-2}.$

Divide by $r^{n-2}$:

$r^2 = r + 6 \quad\Longrightarrow\quad r^2 - r - 6 = 0.$

Step 2 — find the roots. Factor: $(r - 3)(r + 2) = 0$, so $r = 3$ or $r = -2$.

Step 3 — general solution. With two distinct roots, the general solution is

$a_n = A\,(3)^n + B\,(-2)^n,$

for constants $A$ and $B$ determined by the initial conditions.

Step 4 — use the initial conditions.

$n=0:\quad A + B = 3$ $n=1:\quad 3A - 2B = 6$

From the first equation $A = 3 - B$. Substituting: $3(3 - B) - 2B = 6 \Rightarrow 9 - 5B = 6 \Rightarrow B = \tfrac{3}{5}$, so $A = 3 - \tfrac{3}{5} = \tfrac{12}{5}$.

Closed form:

$a_n = \frac{12}{5}\,(3)^n + \frac{3}{5}\,(-2)^n.$

Check: $a_2 = \frac{12}{5}(9) + \frac{3}{5}(4) = \frac{108}{5} + \frac{12}{5} = \frac{120}{5} = 24$. Directly from the recurrence, $a_2 = a_1 + 6a_0 = 6 + 18 = 24$. It matches.

Applying it to Fibonacci

For $F_n = F_{n-1} + F_{n-2}$ the characteristic equation is $r^2 - r - 1 = 0$, whose roots are $r = \frac{1 \pm \sqrt{5}}{2}$. Call them $\varphi = \frac{1+\sqrt5}{2}$ and $\psi = \frac{1-\sqrt5}{2}$. Fitting $F_0 = 0,\ F_1 = 1$ yields Binet's formula:

$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}.$

Because $|\psi| \approx 0.618 < 1$, the $\psi^n$ term shrinks to zero, so for large $n$ we have $F_n \approx \frac{\varphi^n}{\sqrt5}$ — this is exactly why consecutive ratios tend to $\varphi$.

Repeated roots and non-homogeneous cases

Two situations need adjustment:

• Repeated root. If the characteristic equation has a double root $r$ (e.g. $r^2 - 4r + 4 = 0$ gives $r = 2$ twice), the general solution is $a_n = (A + Bn)\,r^n$ — you multiply the second copy by $n$. This mirrors the trick used in differential equations.
• Non-homogeneous. For a rule like $a_n = 2a_{n-1} + 3$, solve the homogeneous part ($a_n = 2a_{n-1}$, giving $A\cdot 2^n$) and add any particular solution to the full equation. Here a constant guess $a_n = c$ gives $c = 2c + 3 \Rightarrow c = -3$, so the general solution is $a_n = A\cdot 2^n - 3$. With $a_0 = 1$: $A - 3 = 1 \Rightarrow A = 4$, so $a_n = 4\cdot 2^n - 3 = 2^{n+2} - 3$. Check: $a_1 = 8 - 3 = 5$. Correct.

Recurrences and Algorithm Analysis

Every time a program calls itself, it creates a recurrence for its running time. Understanding these is how computer scientists predict whether an algorithm is fast or hopelessly slow.

Example — binary search. To search a sorted list of $n$ items, you check the middle and then search one half. The cost satisfies

$T(n) = T\!\left(\tfrac{n}{2}\right) + 1,$

with $T(1) = 1$. Unrolling: after $k$ steps the list has size $n/2^k$; it hits size 1 when $k = \log_2 n$. So $T(n) = \log_2 n + 1$, which is why binary search is $O(\log n)$ — searching a million items takes only about 20 comparisons.

Example — naive recursive Fibonacci. Computing $F_n$ by literally recursing on $F_{n-1}$ and $F_{n-2}$ costs

$T(n) = T(n-1) + T(n-2) + 1,$

which grows like $\varphi^n$ — exponential! This is the classic cautionary tale: the same recurrence that defines the numbers also exposes why the obvious recursive program is catastrophically slow, and why storing computed values (dynamic programming) reduces the cost to linear.

Real-World Applications

• Population and biology: modeling animal populations, cell division, and (as Fibonacci intended) reproduction dynamics.
• Finance: compound interest is the simplest recurrence, $A_n = (1 + r)A_{n-1}$; loan-amortization schedules are non-homogeneous recurrences.
• Computer science: analyzing recursive algorithms (mergesort, quicksort, tree traversals) and designing dynamic-programming solutions.
• Signal processing: digital filters compute each output from previous outputs and inputs — literally a recurrence.
• Combinatorics: counting tilings, binary strings without consecutive 1s, and the Tower of Hanoi ($H_n = 2H_{n-1} + 1$, giving $2^n - 1$ moves).

Common Mistakes

1. Forgetting initial conditions. Misconception: the recurrence alone defines the sequence. Why wrong: the same rule produces infinitely many sequences depending on where it starts. Correction: always state as many initial values as the order of the recurrence.

2. Wrong number of initial conditions. Misconception: one starting value is always enough. Why wrong: a second-order recurrence like Fibonacci reaches back two steps, so one value leaves $F_2$ undefined. Correction: an order-$k$ recurrence requires exactly $k$ initial conditions.

3. Mishandling repeated roots. Misconception: a double root $r$ gives solution $A r^n + B r^n$. Why wrong: $A r^n + B r^n = (A+B)r^n$ is really one constant, so you cannot match two initial conditions. Correction: use $a_n = (A + Bn)r^n$ for a repeated root.

Comparison and Connections

Recurrences are close cousins of several other tools. A recurrence relation is the discrete analogue of a differential equation: both express change in terms of current state, one in whole-number steps and one continuously — and both use the characteristic-equation method. A closed-form formula is the "solved" opposite of a recurrence: fast to evaluate but often hard to find.

Idea	Defines term by	Needs starting values?	Evaluate $a_{100}$
Recurrence relation	previous term(s)	yes	compute all prior terms
Closed form	position $n$ directly	no	plug in $n = 100$
Differential equation	rate of change	yes (initial value)	continuous analogue
Explicit sequence formula	a rule in $n$	no	direct substitution

Practice Questions

Recall

State the Fibonacci recurrence together with its standard initial conditions. Answer: $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$.

Understanding

Explain why a second-order recurrence needs two initial conditions but a first-order one needs only one. Guidance: the rule for $a_n$ reaches back to $a_{n-1}$ and $a_{n-2}$; to compute the first term the rule applies to, both predecessors must already be known, so two anchors are required. A first-order rule reaches back only one term.

Application

Solve $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 2,\ a_1 = 5$. Answer: Characteristic equation $r^2 - 5r + 6 = 0 \Rightarrow (r-2)(r-3)=0$, roots $2, 3$. General solution $a_n = A\cdot 2^n + B\cdot 3^n$. From $A + B = 2$ and $2A + 3B = 5$: subtracting twice the first from the second gives $B = 1$, so $A = 1$. Thus $a_n = 2^n + 3^n$. Check: $a_2 = 4 + 9 = 13$, and $5(5) - 6(2) = 25 - 12 = 13$. Correct.

Analysis

The naive recursive Fibonacci algorithm satisfies $T(n) = T(n-1) + T(n-2) + 1$. Explain what this reveals about its efficiency and how to fix it. Guidance: the recurrence grows exponentially (like $\varphi^n$) because the same subproblems are recomputed many times. Storing already-computed values (memoization / dynamic programming) makes each $F_k$ computed once, reducing the cost to linear, $O(n)$.

FAQ

Is a recurrence relation the same as a recursive function in programming? They are deeply related: a recursive function often implements a recurrence directly. But a recurrence is a mathematical statement about a sequence, while a recursive function is code — and the naive code can be far slower than the math suggests is necessary.

Why bother solving for a closed form if I can just compute term by term? A closed form lets you jump straight to $a_{1,000,000}$ without computing everything before it, reveals the growth rate (linear? exponential?), and often exposes hidden structure like the golden ratio in Fibonacci.

What does "linear" mean in "linear recurrence"? Each previous term appears only to the first power and is multiplied by a constant — no squares, products of terms, or other functions of the sequence. $a_n = a_{n-1}^2$ is not linear.

Why does the characteristic-equation trick work? Exponential functions $r^n$ are the natural solutions because plugging $r^n$ into a linear recurrence turns every shifted term into a power of $r$, so the whole thing collapses to a polynomial in $r$. It is the same reason $e^{rx}$ solves linear differential equations.

Do all recurrences have nice closed-form solutions? No. The clean characteristic-equation method applies to linear recurrences with constant coefficients. Nonlinear recurrences (like the logistic map $x_{n+1} = r x_n(1 - x_n)$) can be chaotic and have no simple formula at all.

Quick Revision

• A recurrence defines each term from earlier terms; initial conditions anchor it. Order $k$ needs $k$ starting values.
• Fibonacci: $F_n = F_{n-1} + F_{n-2}$, $F_0 = 0,\ F_1 = 1 \Rightarrow 0,1,1,2,3,5,8,\dots$; ratios approach $\varphi = \frac{1+\sqrt5}{2}$.
• Characteristic equation: substitute $a_n = r^n$, solve the polynomial. Distinct roots $\Rightarrow a_n = A r_1^n + B r_2^n$.
• Repeated root $r$: $a_n = (A + Bn)r^n$.
• Non-homogeneous: general = homogeneous solution + particular solution.
• Binet: $F_n = \dfrac{\varphi^n - \psi^n}{\sqrt5}$.
• Algorithms: binary search $T(n) = T(n/2) + 1 \Rightarrow O(\log n)$; naive Fibonacci is exponential — use dynamic programming.

Related Topics

Prerequisites

• Discrete Mathematics overview
• Sequences and series (algebraic foundations)
• Solving quadratic equations (needed for characteristic equations)

Related Topics

• Mathematical induction (used to prove closed-form solutions correct)
• Combinatorics and counting
• Differential equations (the continuous analogue) — see Differential Equations

Next Topics

• Generating functions (a powerful alternative method for solving recurrences)
• Algorithm analysis and Big-O notation
• Dynamic programming