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}\).
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}\)
