Recurrence relationship

In this section you will be looking at Recurrence Relations. A Recurrence Relation is an equation which recursively defines a Sequence. You must be able to find the Recurrence Relation for a given Sequence, find the Terms of a Sequence for a given Recurrence Relation, be able to tell if a limit exists for a Recurrence Relation, and if the limit does exist work out what that limit is.

We shall start by defining Sequences and Terms:

What is a Sequence?
A sequence is an ordered list of numbers where the difference between the successive terms is constant (called the Common Difference). For example 11, 15, 19, 23, 27 is a sequence where the difference between successive terms is 4 (i.e. the Common Difference is 4).

Terms
Each individual number in a sequence is called a term. You identify each term by it’s position within the sequence:
Definition 1
The First Term = U_1
The Second Term = U_2
…
The Nth Term = U_n

Example 1.1: In the sequence 11, 15, 19, 23, 27 you can see that
The First Term = U_1 = 11
The Second Term = U_2 = 15
The Third Term = U_3 = 19
The Fourth Term = U_4 = 23
The Fifth Term = U_5 = 27

How do we Generate Sequences?
There are two ways to generate sequences:
Method 1 – Find a formula for the nth term
You must find a formula for the nth term in the format of U_n = an – b where a is the Common Difference and b is a constant to be found.
Example 1.2: Find the formula for the nth term of the sequence 11, 15, 19, 23, 27
Answer:
Common Difference = 4 thus a = 4

Let n = 1, then we have
U_1 = 11 = 4(1) – b = 4 – b
11 = 4 – b
b = -7

Thus the formula for the nth term of the given sequence is
U_n = 4n + 7.

Explanation:
U_2 – U_1 = 15 – 11 = 4 thus the Common Difference is 4, hence a = 4.
Now you must consider U_1 = 11 and find b using U_n = an + b :
U_1 = 11 = 4(1) – b
11 = 4 – b
11 – 4 = – b
7 = – b
b = – 7
therefore b = – 7
Thus the formula for the nth term of the given sequence is
U_n = 4n + 7

You should always double check that your formula is correct, you can choose any term other than U_1 to do this, here we will use U_5:

U_5 = 27 = 4(5) + 7 = 20 + 7 = 27
Thus our nth formula is correct.

Method 2 – Use a Recurrence Relation
Each term can be generated by the previous term. U_(n+1) = cU_n + d where c and d are constants to be found.
Example 1.3: Find the Recurrence Relation for the sequence 11, 15, 19, 23, 27
Answer:
When n = 1, U_1 = 11
When n = 2, U_2 = 15 = 11 + 4 = U_1 + 4
When n = 3, U_3 = 19 = 15 + 4 = U_2 + 4

Thus the Recurrence Relation must be U_(n+1) = (1)U_n + 4

You can check this by letting n = 4:

U_(4+1) = (1)U_4 + 4 = (1)23 + 4 = 27

Thus U_(n+1) = (1)U_n + 4 is the correct Recurrence Relation

Nb the starting value will be provided. It may be written as U_1 or U_0

Example 1.4: A sequence is given by the Recurrence Relation U_n+1 = (4)U_n + 7
If U_1 = 0 find the first 5 terms.

Answer:
The first five terms are 0, 7, 35, 147, 595

Explanation:
U_1 = 0 (given)

For the next four terms you use U_n+1 = 4U_n + 7 which is given in the question.

U_2 = U_1+1 = 4U_1 + 7
= 4(0) + 7
= 7

U_3 = U_2+1 = 4U_2 + 7
= 4(7) + 7
= 35

U_4 = U_3+1 = 4U_3 + 7
= 4(35) + 7
= 147

U_5 = U_4+1 = 4U_4 + 7
= 4(147) + 7
= 595

Thus the first 5 terms are 0, 7, 35, 147, 595

Example 1.4: A sequence is defined by the recurrence relation U_n = m U_(n-1) + c
i) Find the values of m and c, if U_1 = -3, U_2 = 7 and U_ 3 = 10
ii) Find U_4 and U_0
Answer:
i) U_2 = m U_1 + c
7 = m (-3) + c => -3m + c = 7 (*)
U_3 = m U_2 + c
10 = m (7) + c => 7m + c = 10 (**)

Subtract (*) from (**):
10m = 3
m = 3/10 = 0.3

Find c by inputing m into (*):
-3(0.3) + c = 7 => c = 7.9

Thus m = 0.3, c = 7.9

ii) U_4 = 0.3 U_3 + 7.9
U_4 = 0.3 (10) + 7.9
= 10.9

U_1 = 0.3 U_0 + 7.9
– 3 = 0.3 U_0 + 7.9
-3 – 7.9 = 0.3 U_0
– 10.9 = 0.3 U_0
-10.9/ 0.3 = U_0

Explanation:
i) You are looking for the values of m and c and you find them by solving simultaneous equations.
First you take the recurrence relation and the values that you’ve been given:

Recurrence relation: U_n = m U_(n-1) + c

From this you can see:
U_2 = m U_(2-1) + c = m U_1 + c

As you have been given the values of U_2 and U_1 you input these into U_2 = m U_1 + c :
7 = m (-3) + c

which can be rearranged to:
7 = -3m + c (*)
We name this (*).

Similarly from the given recurrence relation you can see
U_3 = m U_2 + c

As you have been given the values of U_2 and U_3 you can input these into U_3 = m U_2 + c:
10 = m (7) + c

which can be rearranged to:
10 = 7m + c (**)
We name this (**).

Now you must subtract (*) from (**), which cancels out the cs:

10 – 7 = 7m + c – (-3m + c)
3 = 7m + c + 3m – c
3 = 10m
3/10 = m
0.3 = m
You must now input m back into (*) to discover c:

7 = -3 (0.3) + c
7 = -0.9 + c
7 + 0.9 = c
7.9 = c

Thus m = 0.3, c = 7.9.

ii) You now know that U_n = 0.3 U_(n-1) + 7.9
You have been told to find U_4, thus n = 4 :
U_4 = 0.3 U_(4-1) + 7.9
U_4 = 0.3 U_(3) + 7.9

You have also been told that U_3 = 10 thus:

U_4 = 0.3 (10) + 7.9
= 3 + 7.9
= 10.9

Now you must find U_0. You cannot use the above method as you do not know U_(0-1). But you do know U_1 so with simple rearranging you can find U_0:

U_1 = 0.3 U_(1-1) + 7.9
U_1 = 0.3 U_0 + 7.9
-3 = 0.3 U_0 + 7.9
-3 – 7.9 = 0.3 U_0
-10.9 = 0.3 U_0
-10.9 / 0.3 = U_0

Limits of Recurrence Relations
You may be asked whether a relation reaches a limit and what that limit is.

Definition 2
The linear recurrence relation: U_(n+1) = a Un + b (where a and b are constants) tends to a limit as n –> ∞ iff -1 < a < 1 Definition 3 If U_(n+1) = a U_n + b Then Limit = b / (1 - a) (where -1 < a < 1) Note: The limit is not dependent on the value of U_1 or U_0 Explanation: U_(n+1) = a U_n + b Limit [U_(n+1)] = Limit [a U_n + b] Limit = a Limit + b Limit - a Limit = b Limit (1 - a) = b Limit = b / (1 - a) Example 1.5: Given U_(n+1) = 8 U_n - 0.5 and U_(n+1) = 0.5 U_n + 8 find out which (if any) of these sequences approaches a limit as n --> ∞
Answer:
U_(n+1) = 8 U_n – 0.5 as 8 > 1 a limit does not exist for this sequence as n –> ∞
U_(n+1) = 0.5 U_n + 8 as -1 < 0.5 < 1 a limit does exist for this sequence as n --> ∞

Example 1.6: For U_(n+1) = 0.5 U_n + 8 find the limit as n –> ∞
Answer:
Limit = b / (1 – a)
Here a = 0.5, b = 8
Thus, limit = 8 / (1 – 0.5)
= 8 / 0.5
= 16
Hence the limit for U_(n+1) = 0.5 U_n + 8 as n –> ∞ is 16.

Example 1.6: For U_(n+1) = 8 U_n – 0.5 where U_1 = 2 find the first value of n where the sequence exceeds 6000, then find the value of this term.
Answer:
U_(n+1) = 8 U_n – 0.5
U_1 = 2 (given)
U_2 = 8(2) – 0.5 = 15.5
U_3 = 8 (15.5) – 0.5 = 123.5
U_4 = 8(123.5) – 0.5 = 987.5
U_5 = 8(987.5) – 0.5 = 7899.5

Thus you can see
U_5 > 6000 => n = 5
U_5 = 7899.5

Working with limits
In a mathematics exam you may come across more wordy questions:
Example 1.7: A pedestrian precinct has 80% of litter cleared each day by the council cleansing department. This figure is achieved with the help of the town’s tidy, responsible shoppers. However, 0.5 kg is dropped and discarded by others each day. The precinct appears tidy if no more than 0.7 kg is scattered around.
Is it likely to appear tidy for the mayor’s visit in 6 months time, or are more workers going to be drafted in?
Answer:
Recurrence Relation: U_(n+1) = 0.2 U_n + 0.5
-1 < 0.2 < 1 => a limit exists
Limit = 0.5 / (1 – 0.2) = 0.5 / 0.8 = 0.625
0.625 < 0.7 Thus the precinct will appear tidy for the mayor without the need for more workers. Explanation: You are told that 80% of the litter is cleared each day, hence 100% - 80% = 20% of the litter will remain. Furthermore, you are told that 0.5kg of litter is dropped each day. U_(n+1) tells us how much litter there will be on the (n+1)th day, given that there is U_n amount of litter on the nth day. If 20% = 0.2 of the litter from day n will remain and 0.5kg of litter will be dropped on day n+1 you can easily see that: U_(n+1) = 0.2U_n + 0.5 You are told to find out how much litter there will be in 6 months time, but as you are not told any value of U_n you must find out the limit as n --> infinity.

First you must decide if a limit exists using Definition 2 :

Definition 2
The linear recurrence relation: U_(n+1) = a Un + b tends to a limit as n –> ∞ iff -1 < a < 1 As -1 < 0.2 < 1 you know that a limit exists, now you must work out if the limit is < 0.7. To work out the limit you use Definition 3: Definition 3 If U_(n+1) = a U_n + b Then Limit = b / (1 - a) Here a = 0.2, b = 0.5, thus Limit = 0.5 / (1 - 0.2) = 0.625 As 0.625 is indeed less than 0.7 you know that the precinct will appear tidy for the mayor without the need of extra workers.