VCE General Mathematics 1&2 - 2020 Edition
6.02 First-order linear recurrence relations
Lesson

## What is a recurrence relation?

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:

$t_{n+1}=t_n+b$tn+1=tn+b , where $t_1=a$t1=a and $n=0,1,2,...$n=0,1,2,...

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

$t_n=t_{n-1}+b$tn=tn1+b, where $t_1=a$t1=a and $n=1,2,3,...$n=1,2,3,...

When considering a general sequence $t_1,t_2,t_3,...,t_{n-1},t_n,t_{n+1}$t1,t2,t3,...,tn1,tn,tn+1 , a recurrence rule can be defined such that the $n$nth term $t_n$tn or the $n+1$n+1th term $t_{n+1}$tn+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:

First order linear recurrence relation

$t_{n+1}=rt_n+d$tn+1=rtn+d, $t_1=a$t1=a where $a$a, $r$r and $d$d are given constants.

OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn1

$t_n=rt_{n-1}+d$tn=rtn1+d, $t_1=a$t1=a where $a$a, $r$r and $d$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$r & $d$d are given as constants.

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

#### Worked example

##### Example 1

State the first five terms in the sequence defined by the recurrence relation $t_{n+1}=2t_n+1,t_1=1$tn+1=2tn+1,t1=1

Think: The initial term in the sequence is number $1$1, given by $t_1=1$t1=1. The initial term can then be substituted into the rule for the recurrence relation to generate the next term in the sequence, given by $t_2$t2. The next term $t_2$t2 is equal to twice the initial term $t_1$t1 plus $1$1, which is $2\times1+1$2×1+1 which equals $3$3. The next term $t_3$t3 is equal to $2\times t_2+1=2\times3+1=7$2×t2+1=2×3+1=7  The next term $t_4=2\times7+1=15$t4=2×7+1=15

Do: The first five terms are $1$1, $3$3, $7$7, $15$15, $31$31

Reflect: This process of multiplying the previous term by $2$2 and adding $1$1 can then continue indefinitely. A simple computer spread sheet program could develop a list of terms very easily.

#### Practice question

##### Question 1

Consider the sequence defined by $a_1=3$a1=3 and $a_{n+1}=3a_n-3$an+1=3an3 for $n\ge1$n1.

1. What is the first term of the sequence?

2. What is the second term of the sequence?

3. What is the third term of the sequence?

4. What is the fourth term of the sequence?

5. What is the fifth term of the sequence?

### Arithmetic sequences

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

#### Worked example

##### example 2

Consider $t_{n+1}=t_n-7,t_1=100$tn+1=tn7,t1=100. Describe the meaning of this rule in words.
Think: Using the recurrence equation, the terms are worked out as $100,93,86,79,...$100,93,86,79,... which is an arithmetic sequence, beginning with the initial term $a=100$a=100. Each new term is found by adding a common difference of $d=-7$d=7. In other words, number $7$7 is always being subtracted from the previous term to create the next term.

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

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

Arithmetic sequence

$t_{n+1}=t_n+d$tn+1=tn+d with $t_1=a$t1=a

OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn1

$t_n=t_{n-1}+d$tn=tn1+d with $t_1=a$t1=a

#### Practice questions

##### Question 2

Consider the sequence defined by $a_1=2$a1=2 and $a_{n+1}=4a_n$an+1=4an for $n\ge1$n1.

1. What is the first term of the sequence?

2. What is the second term of the sequence?

3. What is the third term of the sequence?

4. What is the fourth term of the sequence?

5. What is the fifth term of the sequence?

##### question 3

Identify the difference equations that generate arithmetic sequences.

Select all that apply.

1. $u_n=u_{n-1}-9$un=un19

A

$t_{n+1}=t_n+5$tn+1=tn+5

B

$t_{n+1}=8t_n$tn+1=8tn

C

$G_{n+1}=6-G_n$Gn+1=6Gn

D

$t_{n+1}=2t_n+7$tn+1=2tn+7

E

$u_n=u_{n-1}-9$un=un19

A

$t_{n+1}=t_n+5$tn+1=tn+5

B

$t_{n+1}=8t_n$tn+1=8tn

C

$G_{n+1}=6-G_n$Gn+1=6Gn

D

$t_{n+1}=2t_n+7$tn+1=2tn+7

E

### Geometric sequences

A geometric sequence can defined by recurrence relation $t_{n+1}=r\times t_n$tn+1=r×tn with $t_1=a$t1=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.$r.

#### Worked example

##### Example 3

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

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

Geometric sequence

$t_{n+1}=rt_n$tn+1=rtn with $t_1=a$t1=a

OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn1

$t_n=rt_{n-1}$tn=rtn1 with $t_1=a$t1=a

#### Practice questions

##### Question 4

Consider the sequence defined by $a_1=54$a1=54 and $a_{n+1}=\frac{1}{3}a_n$an+1=13an for $n\ge1$n1.

1. What is the first term of the sequence?

2. What is the second term of the sequence?

3. What is the third term of the sequence?

4. What is the fourth term of the sequence?

5. What is the fifth term of the sequence?

##### Question 5

Identify the difference equations that generate geometric sequences.

Select all that apply.

1. $u_n=-2u_{n-1}$un=2un1

A

$t_{n+1}=0.57t_n$tn+1=0.57tn

B

$G_{n+1}=5-G_n$Gn+1=5Gn

C

$t_{n+1}=t_n+9$tn+1=tn+9

D

$t_{n+1}=6t_n$tn+1=6tn

E

$t_{n+1}=8t_n+7$tn+1=8tn+7

F

$u_n=-2u_{n-1}$un=2un1

A

$t_{n+1}=0.57t_n$tn+1=0.57tn

B

$G_{n+1}=5-G_n$Gn+1=5Gn

C

$t_{n+1}=t_n+9$tn+1=tn+9

D

$t_{n+1}=6t_n$tn+1=6tn

E

$t_{n+1}=8t_n+7$tn+1=8tn+7

F

### Neither arithmetic nor geometric

Finally a recurrence equation in the form $t_{n+1}=rt_n+d$tn+1=rtn+d with $t_1=a$t1=a, $r\ne1$r1 and $d\ne0$d0 forms a sequence that is neither geometric nor arithmetic, but a combination of both. $t_{n+1}=3t_n+1$tn+1=3tn+1, $t_1=0$t1=0 is an example of a sequence that is neither arithmetic nor geometric.

Neither geometric nor arithmetic sequence

$t_{n+1}=rt_n+d$tn+1=rtn+d with $t_1=a$t1=a, $r\ne1$r1 and $d\ne0$d0

OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn1

$t_n=rt_{n-1}+d$tn=rtn1+d with $t_1=a$t1=a

### 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$tn+2=tn+1+tn where $t_1=1$t1=1 and $t_2=1$t2=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.

### 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.

#### Worked example

##### Example 4

Consider the recurrence relation $t_{n+1}=t_n+n$tn+1=tn+n for when $t_1=1$t1=1. The previous term in the first relation has a number $n$n being added. which is not a constant, the number being added gets larger and larger for later terms. $t_2=t_1+1=1+1=2$t2=t1+1=1+1=2, then $t_3=2+2=4$t3=2+2=4, $t_4=4+3=7$t4=4+3=7 etc. Or consider $t_{n+1}=(t_n)^2$tn+1=(tn)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.

### Using CAS calculator to solve recurrence relations

As you can imagine, finding the 100th or 1000th term in a sequence would take a very long time, when only given a recurrence relation with the first number in the sequence. However, technology such as CAS calculators can be used to perform these required iterative calculations.

*CAS instruction coming soon*

## 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.

#### Worked example

##### Example 5

Consider a stockbroker's claim that  $\$200$$200 can be turned into a \1000$$1000 in $10$10 months. The stockbroker claims that they can make $30%$30% a month on the investment, for the cost of $\$35$$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=200Un+1=1.3Un35,U0=200 Note that the coefficient 1.31.3 is equivalent to 130%130%, which is a 30%30% increase on the previous month's amount as shown by the formula. The subtraction of \35$$35 represents the monthly fee. The initial balance is $\$200$$200 so we call this U_0U0 therefore U_1U1 is the amount at the end of month 11 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: 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 11 shows that the investment has grown to \225$$225, determined using the recurrence formula, so that $U_1=1.3\times200-35=225$U1=1.3×20035=225. Similarly, the end of month $2$2 is determined as $U_2=1.3\times225-35=257.50$U2=1.3×22535=257.50 which, rounded to whole dollars, becomes $\$258$$258. The sequence of 1010 months can then be graphed using a 3-dimensional histogram as follows: Note the increase in the original investment, with the rate of change in value increasing as well. Although not strictly geometric (the \35$$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\times U_n\pm k$Un+1=R×Un±k with $R>1$R>1

#### Practice question

##### question 6

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

1. Find $u_1$u1.

2. Find $u_2$u2.

3. Find $u_3$u3.

4. Find $u_4$u4.

5. Complete the table of values.

 $n$n $u_n$un​ $1$1 $2$2 $3$3 $4$4 $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
6. Graph the relation.

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

### Outcomes

#### AoS1.5

Define and explain key concepts in linear relations defined recursively and simple applications of these relations, and apply a range of related mathematical routines and procedures

#### AoS3.12

Define and explain key concepts in use of a first-order linear recurrence relation to generate the terms of a number sequence, and apply a range of related mathematical routines and procedures