5.01 First order recurrence relations

An ordered collection of numbers (or objects) is called a sequence or progression. It is similar to a set, but may contain repetition and the order of the numbers is important. For example -3,5,13,21... and 1,10,100,1000... are two interesting mathematical progressions.

If the sequence ends, it is known as a finite sequence. If the sequence continues indefinitely it is said to be infinite.

The elements of a sequence are called terms. For the sequence 2,3,5,7,11,... (the sequence of prime numbers) the first term is 2, the second term is 3 and term 3 is 5. We can show this with the following notation t_0=2, t_1=3, t_2=5, and so on. Term 6 of this sequence is 13, t_5=13.

To refer generally to the nth term we use the notation t_{n+1}. The n is a variable which represents the position of a term in the sequence. If we let n=0 then t_n is t_0, if we let n=6 then t_n is t_6. For any term using this notation t_n, we can then see that the term before would have to be t_{n-1} and the term after t_n is t_{n+1}.

Sequences do not necessarily have to have a pattern or simple rule for generating terms in the sequence. We could create the sequence 3,1,4,1,5,9,... by separating the digits of \pi, we could use a dice to generate a sequence of of rolls 2,1,1,3,4,... or we could write down the prime numbers in order. However, many sequences have a generating rule that can be expressed as a formula, let's look at a couple of different ways of describing such sequences.

Examples

We can express a sequence using a recurrence relation when each new term is generated by some function of a previous term or terms. Take for example, the sequence described by:t_{n+1}=2t_{n}+5,t_0=3

Note that t_{n+1} is the next term after t_n. We can describe the rule in words as 'the next term is two times the previous term plus the term number; with the first term t_0 being 3. Therefore the second term t_1 is equal to twice the first term t_0 plus 5, which is 2\times 3+2 or 11.

The third term is: t_2=2\times t_1+5=27.

The fourth term is: t_3=2\times t_2+5=59. This process of deducing the next termnth term from the \left(n-1\right)th term can continue indefinitely. And our sequence can be listed as 3,11,27,59,....

A recursive rule always consists of two parts. Firstly how the sequence recurs (how the next term is made) and secondly a term in which to start with, usually term 1.

As a prime concern for this chapter is applications to finance lets use the notation V_n to denote the sequence of values, for example the balance in a savings account growing with interest. What about the initial term?

When we describe a recursive rule we know that it requires two parts. Firstly the rule describing how the sequence recurs and secondly, the initial condition, describing where to start. In previous chapters we have mainly used V_1 for the initial condition, referring to the first term of the sequence. However, sometimes it can be useful to use V_0 meaning the initial term. V_0 is particularly useful in financial questions and population questions where we start with an initial amount and then look for the amount in the days/weeks/month after that starting point. For example, consider a situation where we start with \$100 and each week this amount increases by \$20. If we want to know how much we have after 5 weeks and we use the initial condition of V_0 = 100 then 5 weeks later is t_5 where as if we used the initial condition of V_1 = 100 then 5 weeks later is t_6, which can be a bit confusing. Both would give the same answer but using V_0 in this case makes the term number we are looking for match the number of weeks.

Examples

The recursive rule is limited in that it relies on the previous term in order to find the next term. Consider the sequence 3,5,7,9... The recursive rule for this sequence is t_{n+1}=t_n+2,t_1=3. We can continue the sequence and find later terms by following this recursive rule however if we wanted to know a much later term, t_{43}, for example, it would be helpful to have a rule which allows us to find any term and does not rely on knowing the term before to find it.

This rule is called the explicit rule or the general rule and it is written in terms of n. For this sequence the explicit rule would be t_n=2n+1. We can see if we wanted to find the 5th term we can substitute 5 into the place of n, t_5=2\times 5+1=11. By continuing the pattern seen in the sequence 3,5,7,9... we can see that the 5th term is 11. We can use this rule to jump to a later term like t_{43}:t_{43}=2\times 43+1=87.

Examples

A CAS calculator can be used to generate the terms of a sequence given a recursive or explicit rule. When problem solving involving sequences we can make effective use of our calculator to:

• List the terms of the sequence

• Find a particular term in a sequence

• Calculate the sum of a given set of terms from a sequence

• Graph the sequence to observe patterns in the behaviour of the sequence

Examples