Recurrence Relations

Sequences based on recurrence relations

In maths, a sequence is an ordered set of numbers. For example .

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
• The second term
• The third term
• The nth term

The above sequence can be generated in two ways.

Method 1

You can use a formula for the nth term. Here it would be . Adding the same amount (in this case ) generates each term. Each term will therefore be a multiple of .

However, the first term when is .

When ,

When , 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 ,

When , .

When , .

The recurrence relation would therefore be . The starting value , would have to be provided. Note that the starting value can also be .

• A recurrence relation is a sequence that gives you a connection between two consecutive terms. These two terms are usually and . However they could be given as and .

Example on recurrence relations

Question

A sequence is defined by the recurrence relation and has .

a) Find the first five terms of the sequence.

b) Determine the formula for .

a)

Therefore the sequence is

b) Note that we have powers of 3.

term 1

term 2

term 3 etc.

Therefore