# Recurrence Relations

### Sequences based on recurrence relations

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

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}$$.

• 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}$$