A recurrence relation is an equation that specifies one (or more) known terms in a sequence and then a rule for calculating the next term in the sequence. For example:

\text{$t_{n+1}=t_{n}+d$, where $t_n=a$ and $n=0,1,2,...$}

Where a is the value of the first term, and d is some constant being added each time. The same recurrence relation can be expressed as follows:

\text{$t_n = t_{n-1}+d$, where $t_{n-1} = a$ and $n= 1,2,3,...$}

When considering a general sequence t_1, t_2, t_3, ..., t_{n-1}, t_{n}, t_{n+1}, a recurrence rule can be defined such that the nth term t_n or the n+1^{\text{th}} term t_{n+1} gives the next term in the sequence.

First order linear recurrence relations

First order linear recurrence relations are recurrence equations that have the following form:

t_{n+1} = Rt_n + d, t_0 = a where a,R, and d are given constants.

It can sometimes be expressed as t_n in terms of t_{n-1}.

t_n = rt_{n-1} + d, t_1 = a where a,r, and d are given constants.

The relation above is known as a first order recurrence relation, because the rule only requires one single previous term in the sequence to generate the next term in the sequence. It is also a linear recurrence relation, because the previous referenced sequence terms are linear with r and d are given as constants.

Note that r could be a unit fraction such as \dfrac12 to represent the previous term being divided by constant 2. Also note that d could be a negative number such as -1, to show constant 1 being subtracted from the previous term. Therefore first order linear recurrence relations can use addition, subtraction, multiplication, and division operations to create sequences, not just addition and multiplication.

Examples

Example 1

Consider the sequence defined by a_0=-8 and a_{n+1}=-\dfrac{1}{2}a_n for n\geq 0.

What is the first term of the sequence?

Worked Solution

Create a strategy

Since we are given with n\geq 0, a_0 is the first term of the sequence.

Apply the idea

a_0=-8

What is the second term of the sequence?

Worked Solution

Create a strategy

Substitute n=0 into a_{n+1}=-\dfrac{1}{2}a_n.

Apply the idea

\displaystyle a_{n+1}	\displaystyle =	\displaystyle -\dfrac{1}{2}a_n	Write the formula
\displaystyle a_{0+1}	\displaystyle =	\displaystyle -\dfrac{1}{2}a_0	Substitute n=0
\displaystyle a_{1}	\displaystyle =	\displaystyle -\dfrac{1}{2}\times-8	Evaluate the addition and substitute a_0=-8
\displaystyle a_{1}	\displaystyle =	\displaystyle 4	Evaluate

What is the third term of the sequence?

Worked Solution

Create a strategy

Substitute n=1 into a_{n+1}=-\dfrac{1}{2}a_n.

Apply the idea

\displaystyle a_{1+1}	\displaystyle =	\displaystyle -\dfrac{1}{2}a_1	Substitute n=1
\displaystyle a_{2}	\displaystyle =	\displaystyle -\dfrac{1}{2}\times4	Evaluate the addition and substitute a_1=4
\displaystyle a_{2}	\displaystyle =	\displaystyle -2	Evaluate

What is the fourth term of the sequence?

Worked Solution

Create a strategy

Substitute n=2 into a_{n+1}=-\dfrac{1}{2}a_n.

Apply the idea

\displaystyle a_{2+1}	\displaystyle =	\displaystyle -\dfrac{1}{2}a_2	Substitute n=2
\displaystyle a_{3}	\displaystyle =	\displaystyle -\dfrac{1}{2}\times-2	Evaluate the addition and substitute a_2=-2
\displaystyle a_{3}	\displaystyle =	\displaystyle 1	Evaluate

What is the fifth term of the sequence?

Worked Solution

Create a strategy

Substitute n=3 into a_{n+1}=-\dfrac{1}{2}a_n.

Apply the idea

\displaystyle a_{3+1}	\displaystyle =	\displaystyle -\dfrac{1}{2}a_3	Substitute n=3
\displaystyle a_{4}	\displaystyle =	\displaystyle -\dfrac{1}{2}\times1	Evaluate the addition and substitute a_3=1
\displaystyle a_{4}	\displaystyle =	\displaystyle -\dfrac12	Evaluate

Idea summary

First order linear recurrence relations are recurrence equations that have the following form:

\displaystyle t_{n+1} = Rt_n + d,t_0 = a

\bm{a,R,d}

are given constants

It can sometimes be expressed as t_n in terms of t_{n-1}.

\displaystyle t_n = rt_{n-1} + d,t_1 = a

\bm{a,r,d}

are given constants

Arithmetic sequences

An arithmetic sequence can be defined by recurrence relation t_{n+1}=t_{n}+d with t_0=a. The constant coefficient d represents the common difference between each term and the constant a represents the first term in the sequence.

Arithmetic sequences will be explored further in the next lesson of this chapter .

Examples

Example 2

Consider t_{n+1}=t_{n}-7, t_0=100. Describe the meaning of this rule in words.

Worked Solution

Create a strategy

Recall that t_n is the previous term, d is the common difference, and t_0=a is the first term.

Apply the idea

The rule is "next term equals previous term subtract 7, starting with 100".

Example 3

Identify the recurrence relations that generate arithmetic sequences. Select all that apply.

u_n=u_{n-1}-6

t_{n+1}=2t_n

G_{n+1}=9-G_n

t_{n+1}=t_n+5

t_{n+1}=8t_n+4

Worked Solution

Create a strategy

Choose the options that are in the form of t_{n+1}=t_n+d and t_n=t_{n-1}+d.

Apply the idea

The answers are options A and D.

Idea summary

Arithmetic sequence can be defined by the following recurrence relation.

\displaystyle t_{n+1}=t_{n}+d, t_0=a

\bm{d}

is the common difference

\bm{a}

is the first term in the sequence

It can sometimes be expressed as t_n in terms of t_{n-1}.

\displaystyle t_n = t_{n-1} + d,t_1 = a

\bm{d}

is the common difference

\bm{a}

is the first term in the sequence

Geometric sequences

A geometric sequence can defined by recurrence relation t_{n+1}=Rt_{n} with t_0=a given as the first term and where each new term in the sequence is found by multiplying the previous term by a common ratio R.

Consider t_{n+1}=\dfrac{1}{2} t_{n}, t_0=128. Using the recurrence formula, the first few terms are 128, 64, 32, 16,... which is a geometric sequence, beginning with the first term a=128. Each new term is found by multiplying by a common ratio of R=\dfrac{1}{2}. In other words, the previous term in the sequence is divided by 2 to create the next term.

Geometric sequences will be explored further in a later lesson within this chapter .

Examples

Example 4

Identify the recurrence relations that generate geometric sequences. Select all that apply.

t_{n+1}=5t_n

t_{n+1}=0.41t_n

u_n=-8u_{n-1}

G_{n+1}=2-G_n

t_{n+1}=6t_n+7

t_{n+1}=t_n+9

Worked Solution

Create a strategy

Choose the options that are in the form of t_{n+1}=Rt_n and t_n=Rt_{n-1}.

Apply the idea

The answers are options A, B, and C.

Idea summary

Geometric sequence can be defined by the following recurrence relation.

\displaystyle t_{n+1}=Rt_{n}, t_0=a

\bm{R}

is the common ratio

\bm{a}

is the first term in the sequence

It can sometimes be expressed as t_n in terms of t_{n-1}.

\displaystyle t_n = Rt_{n-1},t_1 = a

\bm{R}

is the common ratio

\bm{a}

is the first term in the sequence

Neither arithmetic nor geometric

Finally a recurrence equation in the form t_{n+1}=Rt_{n}+d with t_0=a, R \neq 1, and d \neq 0 forms a sequence that is neither geometric nor arithmetic, but a combination of both. t_{n+1}=3t_{n}+1, t_0=0 is an example of a sequence that is neither arithmetic nor geometric.

Idea summary

A sequence is neither arithmetic nor geometric if the recurrence relation is in the following form.

\displaystyle t_{n+1}=Rt_{n}+d, t_0=a

\bm{a}

is the first term

\bm{R}

is the common ratio, R\neq 1

\bm{d}

is the common difference, d\neq 0

Higher order recurrence relations

If a recurrence relation requires two or more previous terms in the sequence to generate the next term in the sequence, then it is considered a higher order recurrence relation.

For example, t_{n+2} = t_{n+1} + t_n where t_0 = 1 and t_1 = 1 is a second order recurrence relation, as the first two terms are required for future terms in the sequence to be generated. This particular second order linear recurrence relation is famously known as the Fibonacci sequence, which will be studied in a later lesson within this chapter.

Idea summary

A higher order recurrence relation requires two or more previous terms to find the next term.

Non-linear recurrence relations

A non-linear recurrence relation can also exist. A recurrence relation is considered non-linear when the recursive formula includes operations that are no longer limited to constants being added, subtracted or multiplied to previous terms.

Consider the recurrence relation t_{n+1} = t_n + n for when t_0 = 1. The previous term in the first relation has a number n being added, which is not a constant, the number being added gets larger and larger for later terms. t_1 = t_0 +0 = 1 + 0 = 1, then t_2 = 1 + 1 = 2, t_3 = 2 + 2 = 4 and so forth. Or consider t_{n+1} = (t_n)^2. The previous term in this relation is being multiplied by itself and therefore not a constant multiplier. These are both examples of non-linear recurrence relations.

In this chapter, only specific linear recurrence relations will be explored in further depth.

Idea summary

A recurrence relation is not linear if the recursive formula does not have a constant.

Graphs of recurrence relations

The graph of a recurrence relation can provide a visual understanding of the way the sequence behaves. For instance, it may show whether the terms are always increasing or always decreasing in size. It might also show that the terms change linearly, or as a quadratic curve, or as some other known form, and this might provide a hint as to a possible explicit form of the sequence.

Consider a stockbroker's claim that \$200 can be turned into a \$1000 in 10 months. The stockbroker claims that they can make 30\% a month on the investment, for the cost of \$35 a month.

Such a claim seems incredulous, but given the percentage earnings and the monthly fee stated, a recurrence relation can be formed as:

U_{n+1}=1.3U_n-35,U_0=200

Note that the coefficient 1.3 is equivalent to 130\%, which is a 30\% increase on the previous month's amount as shown by the formula. The subtraction of \$35 represents the monthly fee. The initial balance is \$200 so we call this U_0 therefore U_1 is the amount at the end of month 1.

The recurrence relation can be used to create a table of values, stating the size of the investment at the beginning of the month for the first 10 months as follows, using month numbers (with the first month referred to as month 0) and rounded whole dollars:

\text{M}	0	1	2	3	4	5	6	7	8	9
\$	200	225	258	300	355	426	519	640	796	1000

The end of month 1 shows that the investment has grown to \$225, determined using the recurrence formula, so that U_1=1.3\times 200-35=225. Similarly, the end of month 2 is determined as U_2=1.3\times 225-35=257.50 which rounded to whole dollars becomes \$258.

A 3 dimensional histogram of investments during 10 months. Ask your teacher for more information.

Note the increase in the original investment, with the rate of change in value increasing as well. Although not strictly geometric (the \$35 deduction affects the ratio between successive terms), the trend is certainly apparent - the higher the amount, the faster it grows. This type of growth is typical of recurrence relationships that have the form U_{n+1}=R U_n\pm k with R>1.

Examples

Example 5

Consider the recurrence relation u_{n+1}=2u_n+2, u_0=2.

Find u_1.

Worked Solution

Create a strategy

Substitute n=0 into u_{n+1}=2u_n+2.

Apply the idea

\displaystyle u_{n+1}	\displaystyle =	\displaystyle 2u_n+2	Write the formula
\displaystyle u_{0+1}	\displaystyle =	\displaystyle 2u_0+2	Substitute n=0
\displaystyle u_{1}	\displaystyle =	\displaystyle 2\times2+2	Evaluate the addition and substitute u_0=2
\displaystyle u_{1}	\displaystyle =	\displaystyle 4+2	Evaluate the multiplication
\displaystyle u_{1}	\displaystyle =	\displaystyle 6	Evaluate

Find u_2.

Worked Solution

Create a strategy

Substitute n=1 into u_{n+1}=2u_n+2.

Apply the idea

\displaystyle u_{1+1}	\displaystyle =	\displaystyle 2u_1+2	Substitute n=1
\displaystyle u_{2}	\displaystyle =	\displaystyle 2\times6+2	Evaluate the addition and substitute u_1=6
\displaystyle u_{1}	\displaystyle =	\displaystyle 12+2	Evaluate the multiplication
\displaystyle u_{2}	\displaystyle =	\displaystyle 14	Evaluate

Find u_3.

Worked Solution

Create a strategy

Substitute n=2 into u_{n+1}=2u_n+2.

Apply the idea

\displaystyle u_{2+1}	\displaystyle =	\displaystyle 2u_2+2	Substitute n=2
\displaystyle u_{3}	\displaystyle =	\displaystyle 2\times14+2	Evaluate the addition and substitute u_2=14
\displaystyle u_{1}	\displaystyle =	\displaystyle 28+2	Evaluate the multiplication
\displaystyle u_{3}	\displaystyle =	\displaystyle 30	Evaluate

Find u_4.

Worked Solution

Create a strategy

Substitute n=3 into u_{n+1}=2u_n+2.

Apply the idea

\displaystyle u_{3+1}	\displaystyle =	\displaystyle 2u_3+2	Substitute n=3
\displaystyle u_{4}	\displaystyle =	\displaystyle 2\times30+2	Evaluate the addition and substitute u_3=30
\displaystyle u_{1}	\displaystyle =	\displaystyle 60+2	Evaluate the multiplication
\displaystyle u_{4}	\displaystyle =	\displaystyle 62	Evaluate

Complete the table of values.

n	1	2	3	4
u_n

Worked Solution

Create a strategy

Put the values found from parts (a) to (d).

Apply the idea

n	1	2	3	4
u_n	6	14	30	62

Graph the relation.

Worked Solution

Create a strategy

Plot the values in the table from part (e) into the graph.

Apply the idea

u_n

The graph shows points at (1,6),(2,14),(3,20), and (4,62).

Find the largest value of n for which u_n<22.

Worked Solution

Create a strategy

Use the graph from part (f) to compare the values of n below u_n=22.

Apply the idea

The graph shows that the values of n below u_n=22 are 2 and 1.

So largest value is n=2.

Idea summary

By using a graph, we can understand the behaviour of a recurrence relation whether the values are increasing or decreasing or whether the relation is linear or not.

Outcomes

U1.AoS2.7

use a given recurrence relation to generate a sequence, deduce the explicit rule, n u from the recursion relation, tabulate, graph and evaluate the sequence

5.02 First-order linear recurrence relations

Introduction

Ideas

First order linear recurrence relations

Examples

Example 1

Arithmetic sequences

Examples

Example 2

Example 3

Geometric sequences

Examples

Example 4

Neither arithmetic nor geometric

Higher order recurrence relations

Non-linear recurrence relations

Graphs of recurrence relations

Examples

Example 5

Outcomes

U1.AoS2.7

What is Mathspace

About Mathspace