Mastering Mathematics Smartly
by Wee Wen Shih

A unique self-help website that provides comprehensive coverage of mathematics at A-level & beyond, written in a student-friendly style.

Recurrence relations 2

Given a recurrence relation, three common questions are:

Q1: What does the sequence of numbers generated by it converge to?

A1: If it is given that the sequence converges, then as n approaches infinity, x_n approaches to a limit l and so does x_(n + 1). This will give us an equation expressed in terms of l for which we solve for l. When two possibilities for l emerge upon solving, we need to look back at the recurrence relation to decide which possibility is valid and which is invalid.

Q2. Is the sequence monotone increasing or decreasing?

A2: To determine this, we usually start by considering x_(n + 1) - x_n or x_n - x_(n + 1). By looking at the resulting expression and whatever relevant facts from the question that can be applied, we will be able to arrive a conclusion: >=0 or <=0. Now x_(n + 1) - x_n >=0 will mean that the sequence is monotone increasing; otherwise the sequence is monotone decreasing.

Q3. How is it possible to know what x_1 (i.e. the initial value that starts the sequence) is to be used to determine whether the sequence converges to some limit or diverges?

A3: This is usually investigated by means of GC. With GC, try values ..., -3, -2, -1, 0, 1, 2, 3, ... for x_1. With a table generated in GC, you will be able to see some pattern.

Worked example

We study closely a worked example that originated from a discussion on the forum.

Question: The sequence U_1, U_2, U_3, U_4, ... is such that U_{n + 1} = \frac{5U_n + 4}{U_n + 2}. Given that U_n < 4 for all positive integer n, show that U_n < U_{n + 1} for all positive integer n.

Approach: First, U_{n + 1} = \frac{5U_n + 4}{U_n + 2} = 5 - \frac{6}{U_n + 2}.

Next, we sketch the graphs of y = x and y = 5 - \frac{6}{x + 2}. It is easy to verify, by direct substitution, that they intersect at the point where x = 4.

Now, from the sketch, we see that the graph of the rectangular hyperbola is higher than the straight-line graph for x < 4.

In the same way, U_{n + 1} > U_n for U_n < 4.

Graphs are extremely helpful in allowing us to visualise/compare behaviours of sequences, so do learn graphing techniques really well!