Recurrence Relations

Sequences based on recurrence relations

In maths, a sequence is an ordered set of numbers. For example \(1,5,9,13,17\).

Finding the Un term in the sequence 1, 5, 9, 13, 17. The difference between each term is 4

For this sequence, the rule is add four.

Each number in a sequence is called a term and is identified by its position within the sequence. We write them as follows.

  • The first term \({U_1} = 1\)
  • The second term \({U_2} = 5\)
  • The third term \({U_3} = 9\)
  • The nth term \({U_n}\)

The above sequence can be generated in two ways.

Method 1

You can use a formula for the nth term. Here it would be \({U_n} = 4n - 3\). Adding the same amount (in this case \(4\)) generates each term. Each term will therefore be a multiple of \(4 \Rightarrow 4n\).

However, the first term when \(n = 1\) is \(1\).

\[4(1) + ? = 1\]

\[4(1) - 3 = 1\]

When \(n = 1\), \({U_1} = 4(1) - 3 = 1\)

When \(n = 2\), \({U_2} = 4(2) - 3 = 5\) and so on.

Method 2

The other way of generating this sequence is by using a recurrence relation, where each term is generated from the previous value.

When \(n = 1\), \({U_1} = 1\)

When \(n = 2\), \({U_2} = 1 + 4 = 5\).

When \(n = 3\), \({U_3} = 5 + 4 = 9\).

The recurrence relation would therefore be \({U_{n + 1}} = {U_n} + 4\). The starting value \({U_1}\), would have to be provided. Note that the starting value can also be \({U_0}\).

curriculum-key-fact
  • A recurrence relation is a sequence that gives you a connection between two consecutive terms. These two terms are usually \({U_{n + 1}}\) and \({U_n}\). However they could be given as \({U_n}\) and \({U_{n - 1}}\).

Example on recurrence relations

Question

A sequence is defined by the recurrence relation \({U_{n + 1}} = 3{U_n}\) and has \({U_0} = 1\).

a) Find the first five terms of the sequence.

b) Determine the formula for \({u_n}\).

a) \({U_{n + 1}} = 3{U_n}\)

\[{U_0} = 1\]

\[{U_1} = 3 \times {U_0} = 3 \times 1 = 3\]

\[{U_2} = 3 \times {U_1} = 3 \times 3 = 9\]

\[{U_3} = 3 \times {U_2} = 3 \times 9 = 27\]

\[{U_4} = 3 \times {U_3} = 3 \times 27 = 81\]

Therefore the sequence is \(1,3,9,27,81...\)

b) Note that we have powers of 3.

\(3 = {3^1}\) term 1

\(9 = {3^2}\) term 2

\(27 = {3^3}\) term 3 etc.

Therefore \({U_n} = {3^n}\)