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+d$tn+1=tn+d , where $t_n=a$tn=a and $n=0,1,2,...$n=0,1,2,...
Where $a$a is the value of the first term, and $d$d is some constant being added each time. The same recurrence relation can be expressed as follows:
$t_n=t_{n-1}+d$tn=tn−1+d, where $t_{n-1}=a$tn−1=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,...,tn−1,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:
$t_{n+1}=Rt_n+d$tn+1=Rtn+d, $t_0=a$t0=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}$tn−1
$t_n=rt_{n-1}+d$tn=rtn−1+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_0=1$tn+1=2tn+1,t0=1
Think: The initial term in the sequence is number $1$1, given by $t_0=1$t0=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_1$t1. The next term $t_1$t1 is equal to twice the initial term $t_0$t0 plus $1$1, which is $2\times1+1$2×1+1 which equals $3$3. The next term $t_2$t2 is equal to $2\times t_1+1=2\times3+1=7$2×t1+1=2×3+1=7 The next term $t_3=2\times7+1=15$t3=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_0=-8$a0=−8 and $a_{n+1}=-\frac{1}{2}a_n$an+1=−12an for $n\ge0$n≥0.
What is the first term of the sequence?
What is the second term of the sequence?
What is the third term of the sequence?
What is the fourth term of the sequence?
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_0=a$t0=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_0=100$tn+1=tn−7,t0=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.
$t_{n+1}=t_n+d$tn+1=tn+d with $t_0=a$t0=a
OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn−1
$t_n=t_{n-1}+d$tn=tn−1+d with $t_1=a$t1=a
Practice questions
Question 2
Identify the recurrence relations that generate arithmetic sequences.
Select all that apply.
$u_n=u_{n-1}-6$un=un−1−6
A$t_{n+1}=2t_n$tn+1=2tn
B$G_{n+1}=9-G_n$Gn+1=9−Gn
C$t_{n+1}=t_n+5$tn+1=tn+5
D$t_{n+1}=8t_n+4$tn+1=8tn+4
E
Geometric sequences
A geometric sequence can defined by recurrence relation $t_{n+1}=Rt_n$tn+1=Rtn with $t_0=a$t0=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_0=128$tn+1=12tn,t0=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.
$t_{n+1}=Rt_n$tn+1=Rtn with $t_0=a$t0=a
OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn−1
$t_n=Rt_{n-1}$tn=Rtn−1 with $t_1=a$t1=a
Practice questions
Question 3
Identify the recurrence relations that generate geometric sequences.
Select all that apply.
$t_{n+1}=5t_n$tn+1=5tn
A$t_{n+1}=0.41t_n$tn+1=0.41tn
B$u_n=-8u_{n-1}$un=−8un−1
C$G_{n+1}=2-G_n$Gn+1=2−Gn
D$t_{n+1}=6t_n+7$tn+1=6tn+7
E$t_{n+1}=t_n+9$tn+1=tn+9
F
Neither arithmetic nor geometric
Finally a recurrence equation in the form $t_{n+1}=Rt_n+d$tn+1=Rtn+d with $t_0=a$t0=a, $R\ne1$R≠1 and $d\ne0$d≠0 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_0=0$t0=0 is an example of a sequence that is neither arithmetic nor geometric.
$t_{n+1}=Rt_n+d$tn+1=Rtn+d with $t_0=a$t0=a, $R\ne1$R≠1 and $d\ne0$d≠0
OR it can sometimes be expressed as $t_n$tn in terms of $t_{n-1}$tn−1
$t_n=Rt_{n-1}+d$tn=Rtn−1+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_0=1$t0=1 and $t_1=1$t1=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_0=1$t0=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_1=t_0+0=1+0=1$t1=t0+0=1+0=1, then $t_2=1+1=2$t2=1+1=2, $t_3=2+2=4$t3=2+2=4 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.
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=200$Un+1=1.3Un−35,U0=200
Note that the coefficient $1.3$1.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_0$U0 therefore $U_1$U1 is the amount at the end of month $1$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:
| 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$1 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×200−35=225. Similarly, the end of month $2$2 is determined as $U_2=1.3\times225-35=257.50$U2=1.3×225−35=257.50 which, rounded to whole dollars, becomes $\$258$$258.
The sequence of $10$10 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}=RU_n\pm k$Un+1=RUn±k with $R>1$R>1.
Practice question
question 4
Consider the recurrence relation $u_{n+1}=2u_n+2$un+1=2un+2, $u_0=2$u0=2.
Find $u_1$u1.
Find $u_2$u2.
Find $u_3$u3.
Find $u_4$u4.
Complete the table of values.
$n$n $1$1 $2$2 $3$3 $4$4 $u_n$un $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ Graph the relation.
Loading Graph...Find the largest value of $n$n for which $u_n$un $<$< $22$22.