A recurrence relation defines each term of a sequence from earlier terms. It is useful when a problem naturally breaks into a smaller copy of itself.

Recursive and explicit definitions

Let $(a_n)_{n\in\mathbb N}$ be a sequence, read as “the sequence $a_n$ indexed by the natural numbers.” A first-order recurrence uses only the preceding term. It needs two parts:

1. a base case, such as $a_0=c$;
2. a recurrence rule, such as

$$a_n=F(n,a_{n-1})\qquad(n\ge1).$$

Here, $n$ is the index, $a_{n-1}$ is the preceding term, and $F$ is the rule that produces the next term.

An explicit formula, also called a closed form, gives $a_n$ directly from $n$:

$$a_n=\varphi(n).$$

The symbol $\varphi$ is the Greek letter phi, read “fee.” A recurrence tells us how to compute forward; a closed form lets us jump directly to any index.

Example: factorials

The factorial sequence has base case

$$0!=1$$

and recurrence

$$n!=n(n-1)!\qquad(n\ge1).$$

For example,

$$\begin{aligned} 4! &=4\cdot3!\\ &=4\cdot3\cdot2!\\ &=4\cdot3\cdot2\cdot1!\\ &=4\cdot3\cdot2\cdot1\cdot0!\\ &=24. \end{aligned}$$

Each substitution reduces the index until it reaches the base case.

Example: a geometric recurrence

Suppose

$$\begin{cases} a_0=c,\\ a_n=r a_{n-1}\qquad(n\ge1), \end{cases}$$

where $c$ is the initial value and $r$ is a fixed multiplier. Expanding several terms gives

$$a_1=cr, \qquad a_2=cr^2, \qquad a_3=cr^3.$$

The pattern leads to the closed form

$$\boxed{a_n=cr^n}.$$

A proposed closed form should satisfy both the base case and the recurrence. Those two checks confirm that it describes the same sequence.

Counting with a recurrence: Tower of Hanoi

The Tower of Hanoi puzzle has three pegs and $n$ disks of different sizes. All disks begin on the first peg, largest at the bottom. The goal is to move the entire stack to the third peg while following two rules:

• move only one disk at a time;
• never place a larger disk on top of a smaller one.

Let $h_n$ be the minimum number of legal moves needed for $n$ disks. The empty puzzle gives the base case

$$h_0=0.$$

To solve the puzzle for $n\ge1$:

1. move the top $n-1$ disks to the middle peg, using $h_{n-1}$ moves;
2. move the largest disk to the final peg, using one move;
3. move the $n-1$ smaller disks onto it, using another $h_{n-1}$ moves.

One legal solution for n disks

Therefore,

$$\boxed{h_n=2h_{n-1}+1}.$$

The first values are

$$h_0=0, \quad h_1=1, \quad h_2=3, \quad h_3=7, \quad h_4=15, \quad h_5=31.$$

These values are one less than successive powers of two. To derive the pattern, add $1$ to both sides of the recurrence:

$$h_n+1=2(h_{n-1}+1).$$

If $b_n=h_n+1$, then $b_0=1$ and $b_n=2b_{n-1}$. This is a geometric recurrence, so $b_n=2^n$. Hence

$$\boxed{h_n=2^n-1}.$$

For the traditional puzzle with 64 disks,

$$h_{64}=2^{64}-1 =18{,}446{,}744{,}073{,}709{,}551{,}615$$

moves. At one move per second, that is about $1.84\times10^{19}$ seconds, or $5.85\times10^{11}$ years—roughly 42 times the current age of the universe.

Linear first-order recurrences

A linear first-order recurrence has the form

$$\begin{cases} a_0=c,\\ a_n=f(n)a_{n-1}+g(n)\qquad(n\ge1), \end{cases}$$

where $f(n)$ and $g(n)$ are known functions. The term $g(n)$ is called the nonhomogeneous term or forcing term.

Consider

$$\begin{cases} a_0=3,\\ a_n=2a_{n-1}+n. \end{cases}$$

Computing forward gives the sequence

$$3,7,16,35,74,\ldots$$

To find a closed form, separate the recurrence into its homogeneous behavior and a particular response to the forcing term.

The homogeneous recurrence

Remove the forcing term $g(n)$ to get the associated homogeneous recurrence:

$$h_n=f(n)h_{n-1}.$$

For the example, this becomes

$$h_n=2h_{n-1},$$

whose general solution is

$$h_n=C\cdot2^n,$$

where $C$ is an arbitrary constant.

A particular solution is any one sequence that satisfies the full recurrence. Suppose $(p_n)$ and $(q_n)$ are two particular solutions. Subtracting their equations cancels the forcing term:

$$\begin{aligned} p_n-q_n &=f(n)p_{n-1}+g(n)-\bigl(f(n)q_{n-1}+g(n)\bigr)\\ &=f(n)(p_{n-1}-q_{n-1}). \end{aligned}$$

Thus, the difference between any two particular solutions satisfies the homogeneous recurrence. Once one particular solution $p_n$ is known, every solution has the form

$$\boxed{a_n=p_n+h_n}.$$

Finding a particular solution

For

$$a_n=2a_{n-1}+n,$$

the forcing term $g(n)=n$ is a polynomial of degree one. Guess a particular solution of the same form:

$$p_n=An+B,$$

where $A$ and $B$ are constants to determine. Substitute the guess into the recurrence:

$$\begin{aligned} An+B &=2\bigl(A(n-1)+B\bigr)+n\\ &=(2A+1)n+(-2A+2B). \end{aligned}$$

Matching the coefficients of $n$ and the constant terms gives

$$A=2A+1, \qquad B=-2A+2B.$$

Therefore,

$$A=-1, \qquad B=-2,$$

so one particular solution is

$$p_n=-n-2.$$

Add the homogeneous solution:

$$a_n=-n-2+C\cdot2^n.$$

Use the base case $a_0=3$:

$$3=-2+C, \qquad C=5.$$

The closed form is

$$\boxed{a_n=5\cdot2^n-n-2}.$$

Checking $n=0$ gives $a_0=3$, and substituting the formula into the recurrence gives $a_n=2a_{n-1}+n$.

Choosing the trial form

The trial-form shortcut below applies to a constant-coefficient recurrence

$$a_n=r a_{n-1}+g(n),$$

where $r$ is fixed. In this case, the shape of $g(n)$ suggests a useful guess for $p_n$:

For example, if

$$g(n)=2^n+n^2 3^n,$$

try

$$p_n=A2^n+(B+Cn+Dn^2)3^n.$$

There is one important exception. If the trial already has the same form as a homogeneous solution, it will cancel during substitution. Multiply the trial by $n$—and by a higher power of $n$ if necessary—until the forms no longer overlap. When $g(n)$ is a sum, adjust only the overlapping part of the trial.

For this constant-coefficient case, the complete method is:

1. solve the associated homogeneous recurrence to obtain $h_n$;
2. choose a trial $p_n$ from the form of $g(n)$;
3. substitute $p_n$ into the original recurrence and solve for its coefficients;
4. write $a_n=p_n+h_n$;
5. use the base case to determine the remaining constant.