The sequence 10,\,15,\,20,\,25,\,30,\, \ldots is an arithmetic progression as the sequence recurs by a constant addition. It can be defined using the recursive rule: T_{n+1}=T_n+5,\,T_1=10 or T_n=T_{n-1}+5,\,T_1=10.

The sequence 2,\,6,\,18,\,54,\,162,\, \ldots is a geometric progression as the sequence recurs by a constant multiplication. It can be defined using the recursive rule: T_{n+1}=3T_n,T_1=2 or T_n=3T_{n-1},T_1=2.

Now consider the progression, 3,\,10,\,31,\,94,\,283,\,\ldots. This sequence recurs by multiplying the previous term by 3 and then adding 1 to the result.

A sequence where the next term is multiplied by 3 and then added by 1. Ask your teacher for more information.

Ideas

First order linear recurrence

First order linear recurrence

The first order linear recurrence equation for the sequence mentioned above is T_{n+1}=3T_n+1 with T_1=3. This progression is neither geometric nor arithmetic, but a combination of both.

First order linear recurrence form: T_{n+1}=kT_n+d with T_1=a or alternatively T_n=kT_{n-1}+d with T_1=a.

For recurrence relations of the form t_{n+1}=kt_n+d, the long term behaviour of the sequence is dependent on the value of k. Let's consider two different sequences and use our calculator to observe the long term behaviour using a graph.

We say that a recurrence relation t_{n+1}=kt_n+d converges to a steady state when k is strictly between -1 and 1. Otherwise, we say the recurrence relation diverges.

Sequence 1: t_{n+1}=0.5t_n-2,\ t_1=12. In this example k is between -1 and 1.

-4

-2

t_n

Using the sequence function in your calculator you can generate this graph of the sequence.

We can see that the values of t_n are approaching 4 as n increases.

The recurrence relation converges to a steady state of 4.

Sequence 2: t_{n+1}=1.5t_n-2,\ t_1=12. In this example k is greater than 1.

100

200

300

400

500

600

t_n

Using the sequence function in your calculator you can generate this graph of the sequence.

We can see that the values of t_n are increasing to infinity as n increases.

The recurrence relation diverges, because the terms are not approaching a finite value, but just getting bigger and bigger.

A steady state is reached when T_{n+1}=T_n, that is successive terms are not changing. We can solve algebraically for the steady state by assuming the terms on both sides of the recurrence formula are equal to a constant value, say x, and then solve for x.

Examples

Example 1

Consider the following sequence4,\,-28,\,224,\,-1372,\, \ldots

Is the sequence arithmetic, geometric or neither?

Arithmetic

Neither

Geometric

Worked Solution

Create a strategy

Test the sequence for a common difference or a common ratio.

Apply the idea

The difference between the consecutive terms is not the same and the terms of sequence have alternating signs. This means that the sequence is not arithmetic.

It also does not have a common ratio since the ratio between -28 and 4 is \dfrac{-28}{4}=-7, which is not the same as the ratio between 224 and -28 which is \dfrac{224}{-28}=-8. This means that the sequence is not geometric.

So, the sequence is a neither and the correct answer is Option B.

Example 2

Consider the sequence defined by a_1=5 and a_n=-2a_{n-1}-3 for n\geq 2.

What is the first term of the sequence?

Worked Solution

Apply the idea

The first term of the sequence is when n=1, and we are given that:a_1=5

What is the second term of the sequence?

Worked Solution

Create a strategy

Substitute the value of a_1 from part (a) into a_n=-2a_{n-1}-3 to find a_2.

Apply the idea

\displaystyle a_2	\displaystyle =	\displaystyle -2\times a_1-3	Write the equation
	\displaystyle =	\displaystyle -2\times 5-3	Substitute a_1
	\displaystyle =	\displaystyle -13	Evaluate

What is the third term of the sequence?

Worked Solution

Create a strategy

Substitute the value of a_2 from part (b) into a_n=-2a_{n-1}-3 to find a_3.

Apply the idea

\displaystyle a_3	\displaystyle =	\displaystyle -2 \times a_2-3	Write the equation
	\displaystyle =	\displaystyle -2\times (-13)-3	Substitute a_2
	\displaystyle =	\displaystyle 26-3	Evaluate the multiplication
	\displaystyle =	\displaystyle 23	Evaluate

Example 3

Consider the recurrence relation t_{n+1}=0.1t_n-9 where t_1=-3.

Which of the following best describes the long term behaviour of the sequence?

The terms of sequence have alternating signs.

The sequence is decreasing.

The sequence has a steady state.

None of the others

Worked Solution

Create a strategy

Check the value of k.

Apply the idea

The recurrence relation is of the form t_{n+1}=kt_n+d where k=0.1 and d=-9. Since -1 \lt k \lt 1 the sequence will converge to a steady state.

The correct answer is Option C.

Which of the following statements about the steady-state is always true?

At the steady-state, t_{n+1}=t_n

At the steady-state, the value of the terms reach a stationary point and then begin to decrease.

At the steady-state, n+1=n

At the steady-state, the value of each term is zero.

Worked Solution

Create a strategy

Use the fact that a steady state is reached when successive terms are not changing.

Apply the idea

Since a steady state is reached when successive terms are not changing, then this means that t_{n+1}=t_n.

So, the correct answer is Option A.

Find the steady state solution by setting both t_{n+1} and t_n to be x.

Worked Solution

Create a strategy

Equate t_{n+1} and t_n and solve the equation created by the rule t_{n+1}=0.1t_n-9.

Apply the idea

We will let t_{n+1}=t_n=x to solve the equation.

\displaystyle t_{n+1}	\displaystyle =	\displaystyle 0.1t_n-9	Write the rule
\displaystyle x	\displaystyle =	\displaystyle 0.1x-9	Substitute x for t_{n+1} and t_n
\displaystyle x-0.1x	\displaystyle =	\displaystyle 0.1x-9-0.1x	Subtract 0.1x from both sides
\displaystyle 0.9x	\displaystyle =	\displaystyle -9	Combine like terms
\displaystyle \dfrac{0.9x}{0.9}	\displaystyle =	\displaystyle \dfrac{-9}{0.9}	Divide both sides by 0.9
\displaystyle x	\displaystyle =	\displaystyle -10	Evaluate

Idea summary

First order linear recurrence general term:

\displaystyle T_n=kT_{n-1}+d, \,T_1=a

\bm{n}

is the position of the term

\bm{a}

is the first term in the sequence

\bm{k, \,d}

are constants

If -1 \lt k \lt 1: the sequence converges to a steady state.
If k \gt 1 \text{ or } k \lt -1: the sequence diverges.

Outcomes

ACMGM075

use a general first-order linear recurrence relation to generate the terms of a sequence and to display it in both tabular and graphical form

ACMGM076

recognise that a sequence generated by a first-order linear recurrence relation can have a long term increasing, decreasing or steady-state solution

ACMGM077

use first-order linear recurrence relations to model and analyse (numerically or graphically only) practical problems; for example, investigating the growth of a trout population in a lake recorded at the end of each year and where limited recreational fishing is permitted, or the amount owing on a reducing balance loan after each payment is made

3.06 First order linear recurrence

Introduction

Ideas

First order linear recurrence

Examples

Example 1

Example 2

Example 3

Outcomes

ACMGM075

ACMGM076

ACMGM077

What is Mathspace

About Mathspace