Recurrence Relations

A recurrence relation defines later terms using earlier ones. It is useful when a process naturally develops in stages: a new arrangement is built from smaller arrangements, or a current total is updated by a fixed rule.

The recurrence and its initial conditions work together. The instruction “double the previous value and add one” does not specify a sequence until a starting value is supplied.

On this page

State the rule, starting values and index range

Consider

a_0=2,\qquad a_{n+1}=3a_n+4\quad(n\ge0)

The first values are

a_1=3(2)+4=10,\quad a_2=3(10)+4=34,\quad a_3=3(34)+4=106

The rule determines each next value uniquely from the preceding one. Changing $a_0$ would change the sequence, even though the update formula stayed the same.

A first-order recurrence uses the immediately preceding term. A second-order recurrence may use the preceding two, so two suitable starting values are normally required. The rule must also be defined wherever it is used: division by a previous term, for example, requires checking that the term is not zero.

Unfold a recurrence before guessing a formula

For the same example, substitute earlier updates into later ones:

a_2=3(3a_0+4)+4=3^2a_0+4(3+1)

a_3=3^3a_0+4(3^2+3+1)

Continuing this structure suggests

a_n=3^na_0+4\sum_{j=0}^{n-1}3^j

For $n\ge1$ , the finite geometric sum is $(3^n-1)/2$ . With $a_0=2$ ,

a_n=2\cdot3^n+2(3^n-1)=4\cdot3^n-2

The formula also gives $a_0=2$ . At index four it gives $a_4=4(81)-2=322$ , agreeing with $3(106)+4$ .

Initial conditions are part of a recurrence

Indices start at zero. The same update applies at each transition.

Diagram explanation and exact data

The successive calculations are 3×2+4=10, 3×10+4=34, 3×34+4=106 and 3×106+4=322. The explicit formula 4·3^n−2 matches both the starting value and the symbolic update.

Initial conditions are part of a recurrence: exact reference data
Index n	a_n	a_n + 2
0	2	4
1	10	12
2	34	36
3	106	108
4	322	324

Unfolding exposes a repeated structure, but the ellipsis is not the final justification. Verify the resulting formula against the initial condition and recurrence.

Remove a constant term by changing variables

There is a shorter route for this example. Add two to both sides of the recurrence:

a_{n+1}+2=3a_n+6=3(a_n+2)

Define $b_n=a_n+2$ . Then $b_0=4$ and $b_{n+1}=3b_n$ , so $b_n=4\cdot3^n$ . Subtract two to recover $a_n=4\cdot3^n-2$ .

Why two? The constant solution of $L=3L+4$ is $L=-2$ . Subtracting this fixed value from $a_n$ turns the affine recurrence into a multiplicative one. This method applies to a rule $a_{n+1}=r a_n+c$ when $r\ne1$ : the fixed value is $L=c/(1-r)$ .

When $r=1$ , do not divide by $1-r$ . The recurrence is instead $a_{n+1}=a_n+c$ , an arithmetic sequence.

Verify an explicit formula

Let $f_n=4\cdot3^n-2$ . First, $f_0=4-2=2$ . Next,

3f_n+4=3(4\cdot3^n-2)+4=4\cdot3^{n+1}-2=f_{n+1}

The candidate has the required start and produces the required next value at every step. Because the forward rule determines each term uniquely, induction shows it is the defined sequence.

Checking only $f_0$ , $f_1$ and $f_2$ would not establish the general statement. The symbolic recurrence check supplies the missing link.

Count tilings using two earlier terms

Let $T_n$ count the ways to tile a row of length n using tiles of lengths one and two. Tiles of the same length are indistinguishable, and their left-to-right order determines an arrangement.

There is one empty tiling, so $T_0=1$ . There is one tiling of length one, so $T_1=1$ . For $n\ge2$ , split the tilings according to their final tile.

If the final tile has length one, the preceding part is a tiling of length $n-1$ . If it has length two, the preceding part has length $n-2$ . The two cases are disjoint and include every tiling. Therefore

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

The values are $1,1,2,3,5,8,13$ for indices zero through six. A length-four row has five tilings: $1111$ , $112$ , $121$ , $211$ and $22$ , where each digit denotes a tile length.

Split arrangements by the last tile

Tile widths are proportional to their lengths. Order from left to right matters.

Diagram explanation and exact data

Three arrangements end in a unit tile and correspond to tilings of length three. Two end in a double tile and correspond to tilings of length two. Thus T4=T3+T2=3+2=5.

Split arrangements by the last tile: exact reference data
Arrangement	Last tile	Remaining length
1111	1	3
112	2	2
121	1	3
211	1	3
22	2	2

The starting value $T_0=1$ counts a completed empty arrangement. It is not a claim that an empty row contains one physical tile. This convention allows a final length-two tile to follow the empty arrangement when calculating $T_2$ .

Solve a simple second-order linear recurrence

Consider

h_0=2,\quad h_1=5,\quad h_n=5h_{n-1}-6h_{n-2}\quad(n\ge2)

Try a non-zero exponential form $h_n=r^n$ . Substitution reduces the condition to

r^2-5r+6=(r-2)(r-3)=0

Both $2^n$ and $3^n$ satisfy the recurrence. Because the recurrence is linear and homogeneous, any expression $A2^n+B3^n$ also satisfies it. The starting values require

A+B=2,\qquad 2A+3B=5

Subtract twice the first equation from the second to obtain $B=1$ , then $A=1$ . Thus

h_n=2^n+3^n

It gives $h_2=13$ and $h_3=35$ . Direct substitution verifies the rule for every $n\ge2$ , and the two initial conditions determine the sequence uniquely. We do not need to assume that trying exponentials solves every possible recurrence. Repeated characteristic roots and nonlinear recurrences require different treatment.

Distinguish modelling from calculation

A recurrence used in an application must define what its terms count or measure, and why the update rule applies. The tiling recurrence follows from an exhaustive split of arrangements. An update such as $a_{n+1}=3a_n+4$ is a stipulated mathematical process unless a context independently justifies tripling and adding four.

For computation, store the previous two values when generating a second-order sequence in order. Recursively recalculating both branches of the tiling formula from scratch repeats the same subproblems many times. Reusing already calculated terms gives the same mathematical result with far less work.

An explicit formula is useful for distant terms and proof, but a recurrence is not an inferior answer. It may express the construction more clearly and avoid complicated formulas that are harder to interpret.

Practice questions

With $a_0=2$ and $a_{n+1}=3a_n+4$ , calculate $a_4$ by one update from $a_3=106$ and by the explicit formula.
How many length-five tilings use tiles of lengths one and two under the lesson’s rules?
For $h_n=5h_{n-1}-6h_{n-2}$ with $h_0=2,h_1=5$ , calculate $h_4$ in two ways.

Check your answers

The update gives $3(106)+4=322$ . The explicit rule gives $4\cdot3^4-2=4(81)-2=322$ .
$T_5=T_4+T_3=5+3=8$ . The five cases ending in a unit tile and three ending in a length-two tile are disjoint.
Using $h_2=13$ and $h_3=35$ , the recurrence gives $5(35)-6(13)=97$ . The formula gives $2^4+3^4=16+81=97$ .