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 three rules:

• move only one disk at a time;
• only the top disk of a peg may be moved;
• 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

This construction is also optimal. Before the largest disk can move, all $n-1$ smaller disks must be moved to the spare peg, which takes at least $h_{n-1}$ moves. After the largest disk moves once, those same disks must be moved onto it, taking at least another $h_{n-1}$ moves. 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.

Higher-order recurrences

A recurrence has order $2$ when each term can depend on the two preceding terms. It therefore needs two base cases. The shifted Fibonacci sequence is a standard example:

$$\begin{cases} f_0=1,\\ f_1=2,\\ f_n=f_{n-1}+f_{n-2}\qquad(n\ge2). \end{cases}$$

Computing forward gives

$$1,2,3,5,8,13,21,34,\ldots,$$

and in particular

$$f_{12}=377.$$

This indexing matches a rabbit-population model that starts with one breeding pair at month zero. Each month, the pairs already alive contribute $f_{n-1}$ pairs. Every pair that was alive one month earlier is now old enough to produce one new pair, contributing $f_{n-2}$ newborn pairs. Therefore

$$f_n=f_{n-1}+f_{n-2}.$$

The recurrence computes terms efficiently in order, but a characteristic equation gives a direct formula for $f_n$.

Characteristic equations

For a homogeneous second-order recurrence with constant coefficients,

$$a_n=C_1a_{n-1}+C_2a_{n-2},$$

try an exponential solution $a_n=x^n$, motivated by the geometric solutions of first-order recurrences. Substitution gives

$$x^n=C_1x^{n-1}+C_2x^{n-2}.$$

For a genuine second-order recurrence, $C_2\ne0$. A characteristic root is then nonzero, so dividing by $x^{n-2}$ gives the characteristic equation

$$x^2-C_1x-C_2=0.$$

For the Fibonacci recurrence, this is

$$x^2-x-1=0.$$

Its roots are

$$\varphi=\frac{1+\sqrt5}{2}, \qquad \bar\varphi=\frac{1-\sqrt5}{2}.$$

The symbol $\varphi$ is the golden ratio. The second root $\bar\varphi$ is negative and has magnitude below one.

A single exponential cannot usually satisfy two independent base cases. With two distinct roots, their exponential sequences are linearly independent. A second-order recurrence is determined by two initial values, so these two independent solutions span every solution:

$$f_n=A\varphi^n+B\bar\varphi^n.$$

The base cases give the system

$$1=A+B, \qquad 2=A\varphi+B\bar\varphi.$$

Solving it yields

$$A=\frac{\sqrt5+3}{2\sqrt5}, \qquad B=\frac{\sqrt5-3}{2\sqrt5}.$$

Therefore,

$$\boxed{ f_n= \frac{\sqrt5+3}{2\sqrt5}\varphi^n + \frac{\sqrt5-3}{2\sqrt5}\bar\varphi^n }.$$

Equivalently,

$$f_n=\frac{\varphi^{n+2}-\bar\varphi^{n+2}}{\sqrt5}.$$

Since $|\bar\varphi|<1$, this is also the nearest integer to the dominant term:

$$f_n=\left\lfloor\frac{\varphi^{n+2}}{\sqrt5}+\frac12\right\rfloor.$$

Because $\varphi>1$ while $|\bar\varphi|<1$, the first term controls long-run growth and the second term shrinks in magnitude while alternating sign.

Fibonacci growth from characteristic roots

• $f_n$recurrence values
• $A{\phi }^n$dominant-root term
• $B{\bar{\phi }}^n$conjugate-root correction

A second characteristic-root example

Consider

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

The characteristic equation is

$$x^2-x-2=0,$$

with roots $r_1=-1$ and $r_2=2$. Hence

$$a_n=A(-1)^n+B2^n.$$

The base cases give

$$2=A+B, \qquad 7=-A+2B,$$

so $A=-1$ and $B=3$. The closed form is

$$\boxed{a_n=-(-1)^n+3\cdot2^n}.$$

What changes in other cases?

• Repeated root: if the characteristic polynomial has one double root $r$, the independent basis solutions are $r^n$ and $nr^n$. Thus the general form is $(A+Bn)r^n$.
• Complex roots: the same method works over the complex numbers; conjugate roots can be combined into a real sine-cosine form.
• Nonhomogeneous recurrence: solve the homogeneous recurrence, find one particular solution, and add them: $a_n=h_n+p_n$.
• Order greater than two: the method still works, but the degree of the characteristic polynomial matches the order. For example,

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

leads to

$$x^3-x^2-x+1=0.$$

The characteristic-polynomial shortcut requires a linear recurrence with constant coefficients. Variable coefficients or nonlinear terms need other methods.