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

Typically, a recurrence relation is an equation that connects a current term (Un) with a previous term (Un-1), together with the value of the first term (U1 = 1/2) as shown in this example: Un = 3Un-1, U1 = 1/2. All the terms in the sequence are obtained by using this relation repeatedly (hence the name "recurrence"):

  • U2 = 3(1/2) = 3/2
  • U3 = 3(3/2) = 9/2
  • U4 = 3(9/2) = 27/2, etc.

Thus, U4 is obtained through 3 computations, which is not desirable. In general, we will need n-1 calculations to get us the value of Un.

Point to ponder: Do you realise that the recurrence relation will produce terms that follow a geometric progression?

Often, a question is asked for the student to provide a formula for Un, that is independent of Un-1. This formula (we call it a "closed form") is much more meaningful, since it only requires the value of n to compute any term in the sequence in a single computation.

The approach to obtain the "closed form" formula is systematic and intuitive to follow. We begin with Un or Un+1, then we carry out these steps in order:

  • S1: Use the recurrence relation.
  • S2: Simplify the expression.
  • S3: Look for a pattern.

These 3 steps are repeated until we reach the first term.

See a worked example of the approach.

Entering recurrence relations in GC

We will consider the TI-GC for this example: U_{n+1} = 2U_n - 1, U_1 = \frac{1}{3}.

Step 1: Rewrite the recurrence relation as U_n = 2U_{n - 1} - 1, since the GC makes U_n the subject on the LHS.

Step 2: On your GC, press "MODE" and select "Seq".

Step 3: Press "Y=" to enter the recurrence relation. 
(a) To type in "u", press "2ND" followed by "7".

(b) To type in "n", press "X, T, \theta, n".

(c) Do note that "u(nMin)" refers to the first value in the sequence.

(d) Always remember to express the value of u(nMin) within braces, via the keys "2ND", "(" and "2ND", ")".

Step 4: Press "2ND" followed by "GRAPH" to produce a table of sequence values. This is helpful to visualise convergence or divergence as n becomes large.