Xs1–Xs3 - Recurrence models and their behaviour | OCR A-Level Further Mathematics B (MEI)

Build a recurrence from a repeated process, describe its structure and investigate its terms. Distinguish evidence for a long-run pattern from a proof, including for non-linear recurrences.

One step of the process

A water tank loses half its contents each day, then receives $3$ litres. Can its contents keep increasing forever?

A recurrence describes one step, then lets that same rule work repeatedly. The timing matters: adding the water before the loss would make a different model.

You already know

A sequence is an ordered list of terms. Subscripts label positions: $u_{n+1}$ is the term after $u_n$ . Geometric sequences multiply by a fixed ratio at each step.

State what each term measures, when it is measured and where the indexing starts. Both $u_0$ and $u_1$ are legitimate starting terms; they represent different choices of clock.

Recurrence relation

A recurrence relation, also called a difference equation, gives a term using earlier terms. Initial conditions supply the starting values needed to generate a particular sequence.

For the tank, define $u_n$ as the volume just after the daily refill, with $u_0$ the initial volume. A constant percentage loss leaves a constant fraction of the old contents.

Order of operations in a model

For a retained fraction $a$ and an added amount $b$ ,

\begin{aligned} u_{n+1}&=au_n+b && \text{retention, then addition}\\ u_{n+1}&=a(u_n+b) && \text{addition, then retention} \end{aligned}

These describe fixed operations each period, before any capacity restriction is imposed.

Not in the formula booklet: learn it.

Choose the line that follows the stated order, rather than the one with the simpler brackets.

Worked example 1: loss, then addition

Question. A tank initially contains $2$ litres. Each day half the water is lost, then $3$ litres are added. Form a recurrence and find the volumes after the first two days.

Plan. Follow the two operations in their stated order.

\begin{aligned} \text{volume after loss}&=\tfrac12u_n && \text{half remains}\\ u_{n+1}&=\tfrac12u_n+3,\quad u_0=2 && \text{then add water}\\ u_1&=\tfrac12(2)+3=4 && \text{first day}\\ u_2&=\tfrac12(4)+3=5 && \text{second day} \end{aligned}

Why this step? Only the water already present undergoes the loss. The new $3$ litres are added afterwards.

Answer. $u_{n+1}=\tfrac12u_n+3$ , with $u_0=2$ ; the next volumes are $4$ and $5$ litres.

Check. Both volumes exceed the preceding volume, but each increase is smaller. A fixed daily addition does not imply a fixed daily increase.

Now change just the order of the daily operations. The initial volume and the amounts are the same.

Worked example 2: addition, then loss

Question. A tank initially contains $2$ litres. Each day $3$ litres are added, then half of the combined water is lost. Form a recurrence and find the first two daily volumes.

Plan. Put the addition inside the expression to which the remaining fraction applies.

\begin{aligned} \text{volume before loss}&=u_n+3 && \text{addition first}\\ u_{n+1}&=\tfrac12(u_n+3),\quad u_0=2 && \text{half of the total remains}\\ u_1&=\tfrac12(2+3)=2.5 && \text{first day}\\ u_2&=\tfrac12(2.5+3)=2.75 && \text{second day} \end{aligned}

Why this step? The loss now affects the added water too; the constant contribution is $1.5$ , rather than $3$ .

Answer. $u_{n+1}=\tfrac12u_n+1.5$ , with $u_0=2$ ; the volumes are $2.5$ and $2.75$ litres.

Check. Starting from $2$ , the tank briefly holds $5$ litres on day one, then retains $2.5$ , agreeing with the model.

These models assume the same loss fraction and addition every day, with no capacity restriction. A prediction above the physical capacity would require a revised model.

Watch out

Wrong for “add $b$ , then retain fraction $a$ ”: $u_{n+1}=au_n+b$ . Right: $u_{n+1}=a(u_n+b)$ . The new amount undergoes the loss too.

Apply the operations in order in this new setting.

Describe the rule and its solutions

The structure of the rule and the behaviour of its terms are different descriptions. A linear rule can produce oscillating terms, and a non-linear rule can produce a constant sequence.

Linear and homogeneous

A recurrence is linear if, after rearranging, its sequence terms occur only to the first power, are not multiplied together and have coefficients independent of the sequence values. It is homogeneous if the remaining term independent of the sequence is zero. The order is the gap between the highest and lowest subscripts needed in the recurrence.

Thus $u_{n+1}-2u_n=0$ is first order, linear and homogeneous; $u_{n+1}-2u_n=3$ is linear but non-homogeneous. The rule $u_{n+1}=u_n^2$ is non-linear. The rule $u_{n+2}=u_{n+1}+u_n$ is second order: two starting terms are normally needed.

The coefficients may depend on $n$ in a linear recurrence, but the solution methods in the next lessons use constant coefficients. “Homogeneous” here describes the equation, not whether the terms happen to be zero.

General and particular solutions

A general solution describes a family of sequences with arbitrary constants. A particular solution selects a sequence by applying initial or other conditions.

For $u_{n+1}=2u_n$ , $u_n=C2^n$ is the general family. With $u_1=5$ , the particular solution is $u_n=5\,2^{n-1}$ , for $n\ge1$ . The starting index belongs in the formula.

Long-run language

A sequence converges to $L$ if its terms tend to the finite limit $L$ . Otherwise it diverges. A periodic sequence repeats after a fixed positive integer number of steps. An oscillating sequence repeatedly moves between sides or directions rather than approaching from just one side.

Oscillation does not settle convergence: $(-1/2)^n$ oscillates and converges to $0$ , while $(-1)^n$ is periodic and divergent. A constant sequence is convergent and also periodic, with period $1$ . “Divergent” includes unbounded growth and bounded sequences with no limit.

Key idea

Describe the rule and the selected sequence separately. Oscillation and convergence can occur together if the oscillation's size vanishes.

Separate the rule's structure from the selected sequence's behaviour.

Follow terms, then explain the pattern

A table is a useful first investigation. A short table alone cannot prove what happens for every later index, so look for an explanation as well as a pattern.

If a sequence defined by $u_{n+1}=au_n+b$ has a finite limit $L$ , taking limits gives $L=aL+b$ . A value that reproduces itself under the rule is called a fixed point. A fixed point is a possible limit; its existence does not guarantee that the sequence approaches it.

A fixed point and displacement

For $u_{n+1}=au_n+b$ , a fixed point satisfies

L=aL+b.

Subtracting this equality from the recurrence gives

u_{n+1}-L=a(u_n-L).

The displacement from $L$ is a geometric sequence. In particular, if $|a|<1$ , that displacement tends to zero.

Not in the formula booklet: learn it.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

Xs1–Xs3 - Recurrence models and their behaviour

One step of the process

Describe the rule and its solutions

Follow terms, then explain the pattern

Continue this lesson.

Learn faster with Nova