Helpful context:

The Fibonacci sequence is defined by two numbers and a rule: $a_0 = 0$, $a_1 = 1$, and each subsequent term is the sum of the two before it. That rule is a recurrence relation. The sequence is determined entirely by its starting values and the rule, and there is a closed form for the $n$-th term, derivable by pure algebra. This turns out to be a completely general story: linear recurrences, homogeneous or not, have a systematic theory with exact solutions.

Recurrence relations appear wherever a quantity at step $n$ depends on earlier steps: population models, algorithm analysis, counting problems, physics. The Tower of Hanoi takes exactly $2^n - 1$ moves for $n$ disks. That formula is not guessed; it is derived from the recurrence. This post develops the full theory, from the definition through the characteristic root method, particular solutions, and applications.

What Is a Recurrence Relation

A recurrence relation is an equation that expresses $a_n$ in terms of one or more previous terms $a_{n-1}, a_{n-2}, \ldots$. Together with initial conditions specifying the first few values, a recurrence determines a unique infinite sequence.

The order of a recurrence is the difference between the highest and lowest indices appearing. A first-order recurrence involves only $a_n$ and $a_{n-1}$; a second-order recurrence involves $a_n$, $a_{n-1}$, and $a_{n-2}$.

Examples.

  • Fibonacci: $a_n = a_{n-1} + a_{n-2}$, $a_0 = 0$, $a_1 = 1$. Second order.
  • Factorial: $a_n = n \cdot a_{n-1}$, $a_0 = 1$. First order, with a non-constant coefficient.
  • Tower of Hanoi: $T_n = 2T_{n-1} + 1$, $T_0 = 0$. First order, non-homogeneous.
  • Geometric: $a_n = r \cdot a_{n-1}$, $a_0 = C$. Has the explicit solution $a_n = C r^n$.

Initial conditions are not optional. The recurrence $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 2$, $a_1 = 1$ produces the Lucas numbers, not the Fibonacci numbers. The recurrence specifies the shape of the sequence; the initial conditions pin down which specific sequence it is.

Linear Recurrences

A linear recurrence of order $k$ has the form

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

where $c_1, \ldots, c_k$ are the coefficients (constants if the recurrence has constant coefficients) and $f(n)$ is some function of $n$.

If $f(n) = 0$ for all $n$, the recurrence is homogeneous. Otherwise it is non-homogeneous and $f(n)$ is called the forcing function.

Linearity is the key: the recurrence is linear in the terms $a_{n-1}, \ldots, a_{n-k}$. This means we can apply the standard toolkit of linear algebra, and in particular the principle of superposition: the sum of two solutions to a homogeneous linear recurrence is again a solution.

Solving Linear Homogeneous Recurrences

The method is motivated by the simplest case: the first-order recurrence $a_n = r \cdot a_{n-1}$, which has solution $a_n = C r^n$. The same Ansatz (assumed form) works for higher-order recurrences.

Assume $a_n = r^n$. Substituting into the order-$k$ homogeneous recurrence $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ gives

$$r^n = c_1 r^{n-1} + c_2 r^{n-2} + \cdots + c_k r^{n-k}.$$

Dividing by $r^{n-k}$ (assuming $r \neq 0$) yields the characteristic equation:

$$r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0.$$

The roots of this polynomial determine the general solution.

Distinct Roots

For a second-order recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ with characteristic equation $r^2 - c_1 r - c_2 = 0$:

If the roots $r_1$ and $r_2$ are distinct, the general solution is

$$a_n = A r_1^n + B r_2^n$$

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

Repeated Roots

If the characteristic equation has a repeated root $r_1 = r_2 = r$ (multiplicity 2), the two independent solutions are $r^n$ and $n r^n$, giving

$$a_n = (A + Bn) r^n.$$

More generally, a root $r$ of multiplicity $m$ contributes the $m$ solutions $r^n, n r^n, n^2 r^n, \ldots, n^{m-1} r^n$.

Worked Example: Fibonacci and Binet’s Formula

The Fibonacci recurrence is $a_n = a_{n-1} + a_{n-2}$, $a_0 = 0$, $a_1 = 1$.

Characteristic equation: $r^2 - r - 1 = 0$. By the quadratic formula:

$$r = \frac{1 \pm \sqrt{5}}{2}.$$

Let $\varphi = \frac{1+\sqrt{5}}{2}$ (the golden ratio) and $\psi = \frac{1-\sqrt{5}}{2}$. These are distinct, so the general solution is

$$a_n = A \varphi^n + B \psi^n.$$

Applying initial conditions: $a_0 = A + B = 0$, so $B = -A$. Then $a_1 = A\varphi + B\psi = A(\varphi - \psi) = A\sqrt{5} = 1$, giving $A = \frac{1}{\sqrt{5}}$. This yields Binet’s formula:

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

This is an exact closed form for the $n$-th Fibonacci number, despite involving irrational numbers. The irrationals cancel perfectly for every integer $n$.

Solving Linear Non-Homogeneous Recurrences

When $f(n) \neq 0$, the approach is the same as for non-homogeneous linear ODEs: find the general homogeneous solution $a_n^{(h)}$ and any particular solution $a_n^{(p)}$; the general solution is

$$a_n = a_n^{(h)} + a_n^{(p)}.$$

The homogeneous solution handles the freedom (the initial conditions); the particular solution handles the forcing.

Method of Undetermined Coefficients

The form of the particular solution depends on $f(n)$:

  • If $f(n)$ is a polynomial of degree $d$: try $a_n^{(p)}$ as a polynomial of degree $d$. If $r = 1$ is a root of the characteristic equation with multiplicity $s$, multiply by $n^s$ and try degree $d + s$.
  • If $f(n) = \alpha^n$: try $a_n^{(p)} = A \alpha^n$. If $\alpha$ is a root of multiplicity $s$, try $A n^s \alpha^n$.
  • If $f(n) = \alpha^n p(n)$ where $p$ is a polynomial: combine the two cases above.

Worked Example

Solve $a_n = a_{n-1} + 2^n$, $a_0 = 1$.

Homogeneous solution. The associated homogeneous recurrence is $a_n = a_{n-1}$, with characteristic equation $r - 1 = 0$, root $r = 1$. So $a_n^{(h)} = A \cdot 1^n = A$.

Particular solution. Here $f(n) = 2^n$ and $\alpha = 2$. Since $2$ is not a root of the characteristic equation ($r = 1 \neq 2$), try $a_n^{(p)} = C \cdot 2^n$. Substitute:

$$C \cdot 2^n = C \cdot 2^{n-1} + 2^n.$$

Divide by $2^{n-1}$: $2C = C + 2$, so $C = 2$. The particular solution is $a_n^{(p)} = 2 \cdot 2^n = 2^{n+1}$.

General solution. $a_n = A + 2^{n+1}$.

Apply initial condition. $a_0 = A + 2 = 1$, so $A = -1$. Therefore:

$$a_n = 2^{n+1} - 1.$$

Verification: $a_1 = 4 - 1 = 3$; from the recurrence, $a_1 = a_0 + 2^1 = 1 + 2 = 3$. Correct.

General Theorem

Theorem. The set of all solutions to a $k$-th order linear homogeneous recurrence with constant coefficients over $\mathbb{R}$ forms a $k$-dimensional vector space.

The proof sketch: any solution is completely determined by its $k$ initial values $(a_0, a_1, \ldots, a_{k-1}) \in \mathbb{R}^k$, and the map from initial values to solutions is a linear bijection. So the solution space has the same dimension as $\mathbb{R}^k$, namely $k$.

Concretely, this means: find $k$ linearly independent solutions $s_1(n), s_2(n), \ldots, s_k(n)$, and every solution is a linear combination $A_1 s_1(n) + \cdots + A_k s_k(n)$. The characteristic roots (with multiplicity) provide exactly $k$ such independent solutions.

Corollary. The general solution to the non-homogeneous recurrence is any particular solution plus the general homogeneous solution. This follows directly from linearity: if $a_n^{(p)}$ is any particular solution and $a_n^{(h)}$ is the general homogeneous solution, then $a_n^{(p)} + a_n^{(h)}$ satisfies the non-homogeneous recurrence, and every solution has this form.

Applications

Tower of Hanoi

The Tower of Hanoi with $n$ disks requires $T_n$ moves, where $T_0 = 0$ and

$$T_n = 2T_{n-1} + 1.$$

The homogeneous recurrence $T_n = 2T_{n-1}$ has solution $T_n^{(h)} = A \cdot 2^n$. For the particular solution, $f(n) = 1$ is a degree-$0$ polynomial. Since $r = 1$ is not a root of the characteristic equation $r - 2 = 0$, try $T_n^{(p)} = C$. Substituting: $C = 2C + 1$, so $C = -1$.

General solution: $T_n = A \cdot 2^n - 1$. Applying $T_0 = 0$: $A - 1 = 0$, so $A = 1$. Therefore:

$$T_n = 2^n - 1.$$

The minimum number of moves grows exponentially. With $64$ disks (the mythological version), $2^{64} - 1$ moves are required.

Divide and Conquer and the Master Theorem

Divide-and-conquer algorithms often satisfy recurrences of the form $T(n) = a \cdot T(n/b) + f(n)$, where $a$ is the number of subproblems, $b$ is the branching factor, and $f(n)$ is the work done outside the recursive calls. The Master Theorem gives asymptotic solutions to this family of recurrences without solving them exactly. It is, in essence, a lookup table for the characteristic-root analysis of divide-and-conquer recurrences.

For example, merge sort satisfies $T(n) = 2T(n/2) + O(n)$. By the Master Theorem, $T(n) = O(n \log n)$.

Counting with Recurrences

Problem. How many binary strings of length $n$ contain no two consecutive $1$s?

Let $a_n$ be the count. Consider the first character:

  • If the string starts with $0$: any valid string of length $n-1$ can follow, contributing $a_{n-1}$ strings.
  • If the string starts with $1$: the next character must be $0$, and then any valid string of length $n-2$ can follow, contributing $a_{n-2}$ strings.

So $a_n = a_{n-1} + a_{n-2}$, $a_1 = 2$ (the strings “0” and “1”), $a_2 = 3$ (the strings “00”, “01”, “10”). This is the Fibonacci recurrence shifted by two: $a_n = F_{n+2}$, where $F_k$ is the $k$-th Fibonacci number.

Summary

Concept Key idea
Recurrence relation $a_n$ expressed in terms of $a_{n-1}, \ldots, a_{n-k}$; initial conditions determine the sequence
Order Highest minus lowest index in the relation
Homogeneous $f(n) = 0$; forcing function absent
Characteristic equation Obtained by substituting $a_n = r^n$; roots determine solutions
Distinct roots $r_1, r_2$ General solution $a_n = A r_1^n + B r_2^n$
Repeated root $r$ General solution $a_n = (A + Bn) r^n$
Non-homogeneous General solution = homogeneous + particular
Undetermined coefficients Match form of $f(n)$ to guess particular solution
Solution space $k$-dimensional for order-$k$ homogeneous recurrences

The power of the method is its uniformity: every linear recurrence with constant coefficients, regardless of order or forcing function, is handled by the same two steps. Find the characteristic roots, build the homogeneous solution; match the forcing function, build the particular solution. The initial conditions determine the constants. The result is an exact closed form.

Read next: