Recurrence Relations

We often refer to sequences defined by recurrence relations as term-to-term sequences. Recall that u_n is the nth term in a given sequence.  A recurrence relation is defined as follows:

u_{n+1}=f(u_n).

As you can see, the next term in a sequence is a function of the previous term. In order to generate a sequence like this, the first term must be stated. For example, consider the sequence generated by:

u_{n+1}=u_n\left(7-\frac{1}{2}u_n\right), \hspace{15pt}u_1=2

We find u_2 by setting n=1 and substituting u_1. We find u_3 by setting n=2 and substituted u_2 and so on. Hence why it is called a ‘recurrence relation’. This sequence is nonlinear and the terms are given by

u_2=u_1\left(7-\frac{1}{2}u_1\right)=2(7-\frac{1}{2}\times 2)=12,

u_3=u_2\left(7-\frac{1}{2}u_2\right)=12(7-\frac{1}{2}\times 12)=12,…

… and so on. After the first term, the terms in this sequence will always be 12. See Example 1 for another recurrence relation.

nth term sequences

We often refer to nth term sequences as position-to-term sequences. This is where the sequences are defined as follows:

u_n=f(n)

This is also known as closed form. In this case, each term in the sequence if a function of its position. Unlike for recurrence relations, we do not need a first term to generate a sequence like this. This is because, when given in closed form, each term of a sequence is defined by its position number. For example, consider the sequence generated by the closed form u_{n}=4^n-1. We find u_1 by setting n=1, u_2 by setting n=2 etc:

u_1=4^1-1=3,

u_2=4^2-1=15,

u_3=4^3-1=63, …

 and so on. This sequence is also nonlinear and will diverge (what does diverge mean?). See Example 2 for more.

Increasing, Decreasing and Periodic Sequences

  • Increasing sequences satisfy u_{n+1}>u_n. For example, the sequence generated by the recurrence relation u_{n+1}=u_n^2+1 with u_1=0 is given by 0, 1, 2, 5, 26, 677,... This is an increasing sequence. 
  • Decreasing sequences satisfy u_{n+1}<u_n. For example, the sequence generated by the nth term rule u_n=5-2n is given by 3, 1, -1, -3, -5,.... This is a decreasing sequence.
  • Periodic sequences are those that repeat after a fixed number of terms. We can write this as u_{n+k}=u_n for some fixed value of k. k is known as the order or period of the sequence. For example, the sequence 4, -1, 7, 4, -1, 7, ... is periodic with period 3. 

See Examples 1 and 2.

Examples

Recurrence relation example.


The recurrence relation of a sequence is defined by x_{k+1}=ax_k(x_k+1) where a is a constant with x_1=\frac{1}{2}. 

  1. Given that x_2=\frac{1}{4},  find the value of a.
  2. Generate the first 4 terms of the sequence.
  3. State whether or not the sequence is increasing, decreasing or periodic.

Solution

  1. Using the recurrence relation with k=1, x_2=ax_1(x_1+1)=\frac{1}{2}a(\frac{1}{2}+1)=\frac{3}{4}a. It follows that \frac{3}{4}a=\frac{1}{4} and so a=\frac{1}{3}.
  2. We already have the first two terms so we need x_3=\frac{1}{3}x_2(x_2+1)=\frac{1}{12}\left(\frac{1}{4}+1\right)=\frac{5}{48} and x_4=\frac{1}{3}x_3(x_3+1)=\frac{5}{144}\left(\frac{5}{48}+1\right)=\frac{265}{6912}. Hence, the first 4 terms of the sequence are \frac{1}{2}, \frac{1}{4}, \frac{5}{48}, \frac{265}{6912},…
  3. The sequence is not increasing nor periodic but it is decreasing.

nth term example

The nth term of a sequence is given by u_n=\cos\left(\frac{1}{4}\pi n\right). 

  1. State the period of the sequence.
  2. Calculate \sum_{i=1}^{80} u_n.

Solution:

  1. The period of the sequence is 8.
  2. The first 8 terms of the sequence are \frac{\sqrt{2}}{2}, 0,-\frac{\sqrt{2}}{2}, -1, -\frac{\sqrt{2}}{2}, 0, \frac{\sqrt{2}}{2}, 1. Summing these gives a result of zero and since the sequence repeats with period 8, every 8 terms has a sum of 0. It follows that \sum_{i=1}^{80} u_n=0. See more on sigma notation.

AS Maths Sequence & Series

A2 Maths Sequence & Series