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}