Recurrence Relations

A recurrence relation is an equation that specifies one (or more) known terms in a sequence and then a rule for calculating the next term in the sequence.

If the initial value in a recurrence relation changes, then the whole sequence changes. If we are not given an initial value, we cannot determine any terms in the sequence.

First order recurrence relation – finding the next term

The process for finding a term is to identify what the recurrence relation means and then use the recurrence relation to determine the next value in the sequence.

Worked Example

Determine the first three terms of the sequence represented by the recurrence relation
\(u_{n + 1} = 2u_n + 5\), given that \(u_0 = 8\).

Each term of the sequence is given by multiplying the previous term of the sequence by \(2\) and adding \(5\) to the result.

To find the second number sequence, \(u_1\):

\[u_1 = 2u_0 + 5\]

Substitute \(u_0\)

\[\begin{align}u_1 &= 2 \times 8 + 5 \\ u_1 &= 21\end{align}\]

To find \(u_2\):

\[\begin{align}u_2 &= 2u_1 +5 \\ u_2 &= 2 \times 21 + 5 \\ u_2 &= 47\end{align}\]

So, the first three terms of the sequence represented by \(u_{n + 1} = 2u_n + 5\) are \(8\), \(21\) and \(47\).

Recurrence Relations generating arithmetic sequences

If the values of \(a\) and \(d\) in an arithmetic sequence are known, a recurrence can be set up to generate the sequence.

A recurrence relation representing an arithmetic sequence will be of the form:

\[u_{n + 1} =  u_n + d, \quad u_0 = a\]

Where

  • \(d\) is the common difference
  • \(a\) is the first term in the sequence
  • \(n\) represents the position in the sequence

To determine the recurrence relation when given the start of an arithmetic sequence,

  1. calculate the common difference by subtracting the first term from the second
  2. the first term is \(a (u_0)\).

Worked Example

Set up a recurrence relation to represent the sequence \(−9, − 5, − 1, 3, 7, ...\)

\[\begin{align} d &= -5 - (-9) \\ d &= 4 \\ a &= -9\end{align}\]

Hence the recurrence relation is given by:

\[u_{n + 1} = u_n + 4, \quad u_0 = -9\]

Recurrence Relations generating geometric sequences

If the values of \(a\) and \(r\) in a geometric sequence are known, a recurrence relation can be set up to generate the sequence.

A recurrence relation representing a geometric sequence will be of the form:

\[u_{n + 1} = ru_n, u_0 = a\]

Where

  • \(r\) is the common ratio
  • \(n\) is the term's position in the sequence
  • \(a\) is the first term in the sequence

The process for finding the rule for a geometric sequence is as follows:

  1. Determine the common ratio \(r\) by dividing the second term by the first term.
  2. \(a\) is equal to the first term of the sequence.

Worked Example

Set up a recurrence relation to represent the sequence \(10, 5, 2.5, 1.25, 0.625, …\)

\[r= \frac{u_{1}}{u_{0}} = \frac{5}{10} = \frac{1}{2}\]

\(u_0 = 10\). Hence the recurrence relation is given by:

\[u_{n + 1} = \frac{1}{2} u_{n}, \quad u_{0} = 10\]

This can be verified by looking at two subsequent terms, such as \(u_1 = 5\) and \(u_2 = 2.5\).

\[\begin{align}u_{2} &= \frac{1}{2}u_1 \\ u_{2} &= \frac{1}{2} \times 5 \\ u_{2} &= 2.5\end{align}\]