Sequences and recurrence relations

A sequence is an ordered list of numbers. If its terms are called $u_1,u_2,u_3,\ldots$, then $u_n$ is the term in position $n$.

There are two main ways to define a sequence:

• an explicit formula, such as $u_n=n^2-3n$, gives $u_n$ directly from $n$;
• a recurrence relation, such as $u_{n+1}=2u_n-3$, gives a new term from one or more earlier terms.

A recurrence also needs enough initial conditions to start the process. Together,

$u_1=5,\qquad u_{n+1}=2u_n-3$

define one sequence. The recurrence alone defines infinitely many sequences, depending on the choice of $u_1$.

Prerequisites

You should be able to:

• substitute into formulae and generate simple sequences;
• rearrange formulae;
• solve linear and quadratic equations;
• use inequalities and exact fractions confidently.

Explicit formulae

An explicit formula is also called an nth-term formula. It is a position-to-term rule: substitute a positive integer value of $n$ to obtain the term in that position.

Worked example 1: generate selected terms

The sequence $(u_n)$ is defined by

$u_n=(-1)^n(2n+1).$

Find $u_1$, $u_2$, $u_5$ and $u_{20}$.

$$\begin{aligned} u_1&=(-1)^1(3)=-3,\\ u_2&=(-1)^2(5)=5,\\ u_5&=(-1)^5(11)=-11,\\ u_{20}&=(-1)^{20}(41)=41. \end{aligned}$$

Odd powers of $-1$ are negative and even powers are positive, so the signs alternate.

Subscripts are labels

$u_{n+1}$ means the term whose position is $n+1$. It does not mean $u_n+1$, and $u_n$ does not mean $u\times n$.

Worked example 2: test whether a value is a term

For $v_n=n^2+2n$, determine whether $48$ is a term.

Set the formula equal to $48$:

$n^2+2n=48.$

Rearrange and factorise:

$n^2+2n-48=0,$

$(n+8)(n-6)=0.$

Thus $n=-8$ or $n=6$. A term number must be a positive integer, so only $n=6$ is valid. Therefore $48=v_6$.

An algebraic solution for $n$ is not sufficient. It must belong to the sequence’s index set, normally $n=1,2,3,\ldots$.

Self-check 1

Let $a_n=3n^2-7$.

1. Find $a_1$, $a_4$ and $a_{10}$.
2. Determine whether $68$ is a term.

Answers

1. $a_1=-4$, $a_4=41$ and $a_{10}=293$.
2. Setting $3n^2-7=68$ gives $n^2=25$, so $n=\pm5$. Only the positive index is allowed, hence $68=a_5$.

Recurrence relations

A first-order recurrence uses the preceding term:

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

Starting at $u_1$, repeatedly apply the function $f$:

$u_1\longmapsto u_2=f(u_1)\longmapsto u_3=f(u_2)\longmapsto\cdots.$

This repeated substitution is called iteration.

Worked example 3: iterate exactly

Given

$u_1=10,\qquad u_{n+1}=\frac{u_n+2}{3},$

find $u_2$, $u_3$ and $u_4$.

Use the most recently found term each time:

$$\begin{aligned} u_2&=\frac{10+2}{3}=4,\\ u_3&=\frac{4+2}{3}=2,\\ u_4&=\frac{2+2}{3}=\frac43. \end{aligned}$$

Keep exact values unless the question requests decimals. Early rounding is repeatedly fed back into the rule and can accumulate error.

Worked example 4: a non-linear recurrence

The sequence is defined by

$x_1=2,\qquad x_{n+1}=x_n^2-3.$

Find the first six terms.

$$\begin{aligned} x_1&=2,\\ x_2&=2^2-3=1,\\ x_3&=1^2-3=-2,\\ x_4&=(-2)^2-3=1,\\ x_5&=1^2-3=-2,\\ x_6&=(-2)^2-3=1. \end{aligned}$$

The sequence begins

$2,1,-2,1,-2,1,\ldots$

Brackets around a negative term are essential: $(-2)^2=4$, whereas $-2^2=-4$.

More than one preceding term

The recurrence

$w_{n+2}=w_{n+1}+w_n$

uses two preceding terms, so it requires two initial values.

Worked example 5: a second-order recurrence

Given

$w_1=1,\qquad w_2=4,\qquad w_{n+2}=2w_{n+1}-w_n,$

find $w_3,w_4,w_5$.

$$\begin{aligned} w_3&=2w_2-w_1=2(4)-1=7,\\ w_4&=2w_3-w_2=2(7)-4=10,\\ w_5&=2w_4-w_3=2(10)-7=13. \end{aligned}$$

Thus the sequence begins $1,4,7,10,13,\ldots$. The recurrence uses two terms, even though this particular sequence is arithmetic.

Do not substitute the index for the term

If $u_{n+1}=3u_n-4$ and $u_1=6$, then $u_2=3(6)-4=14$. Substituting $n=1$ into the right side to get $3(1)-4$ confuses the index with the value of the term.

Self-check 2

1. Given $p_1=7$ and $p_{n+1}=2p_n-5$, find $p_2,p_3,p_4$.
2. Given $q_1=2$, $q_2=-1$ and $q_{n+2}=q_{n+1}-2q_n$, find $q_3,q_4,q_5$.

Answers

1. $p_2=9$, $p_3=13$, $p_4=21$.
2. $q_3=-1-2(2)=-5$, $q_4=-5-2(-1)=-3$, and $q_5=-3-2(-5)=7$.

Writing a recurrence relation

A valid recursive definition states both the recurrence and its initial condition. Look for how consecutive terms are connected.

Worked example 6: explicit to recursive

The sequence has explicit formula

$u_n=5\left(\frac23\right)^{n-1}.$

Write it recursively.

First find the initial term:

$u_1=5\left(\frac23\right)^0=5.$

Each term is $\frac23$ times the preceding term, so

$\boxed{u_1=5,\qquad u_{n+1}=\frac23u_n.}$

Worked example 7: infer a linear recurrence

Find a recurrence of the form $u_{n+1}=au_n+b$ for

$2,7,17,37,\ldots$

Each term is twice the preceding term plus $3$:

$2(2)+3=7,\qquad 2(7)+3=17,\qquad 2(17)+3=37.$

Therefore one suitable definition is

$\boxed{u_1=2,\qquad u_{n+1}=2u_n+3.}$

Checking several transitions supports the pattern, but a finite list alone never determines a unique continuation. A question asking for a rule assumes the intended simple pattern.

Worked example 8: verify an explicit formula

Show that

$u_n=4\cdot3^{n-1}+1$

satisfies

$u_1=5,\qquad u_{n+1}=3u_n-2.$

First check the initial value:

$u_1=4\cdot3^0+1=5.$

Next use the proposed formula for $u_n$ in the recurrence:

$$\begin{aligned} 3u_n-2 &=3\left(4\cdot3^{n-1}+1\right)-2\\ &=4\cdot3^n+1\\ &=u_{n+1}, \end{aligned}$$

because replacing $n$ by $n+1$ in the explicit formula gives

$u_{n+1}=4\cdot3^{(n+1)-1}+1=4\cdot3^n+1.$

Both checks are necessary. Satisfying the recurrence without satisfying the initial condition could describe a different sequence.

Increasing, decreasing and periodic sequences

A sequence $(u_n)$ is:

• strictly increasing if $u_{n+1}>u_n$ for every relevant $n$;
• strictly decreasing if $u_{n+1}<u_n$ for every relevant $n$;
• non-decreasing if $u_{n+1}\geq u_n$;
• non-increasing if $u_{n+1}\leq u_n$.

The word monotonic describes a sequence that consistently moves in one direction, allowing the precise convention to be stated by an inequality.

For an explicit formula, examine the sign of

$u_{n+1}-u_n.$

Worked example 9: prove that a sequence is increasing

Show that $u_n=n^2+3n$ is strictly increasing for $n\geq1$.

$$\begin{aligned} u_{n+1}-u_n &=\left((n+1)^2+3(n+1)\right)-(n^2+3n)\\ &=n^2+2n+1+3n+3-n^2-3n\\ &=2n+4. \end{aligned}$$

For every $n\geq1$, $2n+4>0$. Hence $u_{n+1}>u_n$, so $(u_n)$ is strictly increasing.

Listing the first few terms is evidence, not proof that the pattern continues for every $n$.

Worked example 10: a sequence that is not monotonic

Consider $v_n=(-1)^n/n$:

$-1,\frac12,-\frac13,\frac14,-\frac15,\ldots$

The terms alternate between negative and positive values. In particular,

$v_2>v_1\qquad\text{but}\qquad v_3<v_2.$

Therefore the sequence is neither increasing nor decreasing. Although $|v_n|$ decreases, the sequence $(v_n)$ itself does not move in one direction.

A sequence is periodic if some positive integer $k$ satisfies

$u_{n+k}=u_n$

for every relevant $n$. The least such $k$ is its period.

Worked example 11: identify a cycle

For the recurrence

$u_1=2,\qquad u_{n+1}=\frac{1}{1-u_n},$

generate terms until a pattern repeats.

$u_2=-1,\qquad u_3=\frac12,\qquad u_4=2.$

Once $u_4=u_1$, the deterministic recurrence repeats the same transitions:

$2,-1,\frac12,2,-1,\frac12,\ldots$

The period is $3$.

The domain still matters. For example, the same recurrence cannot generate a second term from $u_1=1$, because division by zero would be required.

Self-check 3

1. Show that $a_n=10-3n$ is strictly decreasing.
2. State the period of $b_n=\cos(n\pi/2)$ for $n=1,2,3,\ldots$.
3. Is $c_n=(-1)^n n$ monotonic? Explain briefly.

Answers

1. $a_{n+1}-a_n=[10-3(n+1)]-(10-3n)=-3<0$, so the sequence is strictly decreasing.
2. Its terms are $0,-1,0,1,0,-1,\ldots$, so the period is $4$.
3. No. Its terms $-1,2,-3,4,\ldots$ alternate in sign, so consecutive differences do not keep one sign.

Long term behaviour and limits

A sequence converges to a limit $L$ if its terms become arbitrarily close to $L$ as $n$ becomes large. We write

$\lim_{n\to\infty}u_n=L$

or $u_n\to L$.

A sequence that does not approach a finite limit diverges. Divergence includes:

• growing without bound, such as $u_n=n^2$;
• decreasing without bound, such as $u_n=-n$;
• continuing to oscillate, such as $u_n=(-1)^n$.

Fixed points of a recurrence

Suppose

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

and the sequence converges to $L$. Then both $u_n$ and $u_{n+1}$ approach the same limit. Provided $f$ behaves continuously near $L$,

$L=f(L).$

Such a value is called a fixed point of $f$.

A fixed point is only a candidate limit

Solving $L=f(L)$ finds values at which the iteration could settle. It does not prove that a sequence converges, nor that it converges to every solution. The starting value and the behaviour of the recurrence matter.

Worked example 12: find and confirm a linear limit

Let

$u_1=10,\qquad u_{n+1}=\frac12u_n+3.$

The first terms are

$10,8,7,6.5,6.25,\ldots$

They suggest a limit of $6$. If a limit $L$ exists, then

$L=\frac12L+3,$

so $L=6$.

To see why convergence really occurs, subtract the fixed point from both sides:

$$\begin{aligned} u_{n+1}-6 &=\frac12u_n+3-6\\ &=\frac12(u_n-6). \end{aligned}$$

Each step halves the distance from $6$. In fact,

$u_n-6=4\left(\frac12\right)^{n-1},$

so

$u_n=6+4\left(\frac12\right)^{n-1}\longrightarrow6.$

This argument establishes convergence, not merely the value the limit would have if it existed.

Linear recurrences and stability

For

$u_{n+1}=au_n+b,\qquad a\ne1,$

the fixed point is

$L=\frac{b}{1-a}.$

Subtracting it gives

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

Therefore

$u_n-L=a^{n-1}(u_1-L).$

This reveals the long term behaviour:

Value of $a$	Typical behaviour when $u_1\ne L$
$	a
$-1<a<0$	Converges while alternating around $L$
$a=1$	No unique fixed point; $u_n=u_1+(n-1)b$
$a=-1$	Usually alternates between two values
$	a

The exceptional start $u_1=L$ produces the constant sequence $L,L,L,\ldots$ for any $a$.

Worked example 13: alternating convergence

Given

$u_1=8,\qquad u_{n+1}=4-\frac12u_n,$

find the limit and describe the approach.

If a limit exists,

$L=4-\frac12L,$

so

$\frac32L=4\qquad\Longrightarrow\qquad L=\frac83.$

Here $a=-\frac12$, whose magnitude is less than $1$. Thus the distance from $8/3$ is multiplied by $1/2$ each time, while its sign reverses. The sequence converges to $8/3$, alternating from one side to the other:

$8,0,4,2,3,\frac52,\ldots$

Worked example 14: fixed points without convergence

Let

$x_1=3,\qquad x_{n+1}=x_n^2-2.$

Solving the fixed-point equation gives

$L=L^2-2,$

$L^2-L-2=0,$

$L=2\quad\text{or}\quad L=-1.$

However,

$x_2=7,\qquad x_3=47,\qquad x_4=2207.$

The sequence plainly moves away and does not converge to either candidate. The equation $L=f(L)$ supplied necessary candidates under an assumption of convergence. It did not supply a convergence proof.

Self-check 4

1. A sequence satisfies $u_1=1$ and $u_{n+1}=0.3u_n+7$. Find its limit and justify convergence.
2. A sequence satisfies $v_1=0$ and $v_{n+1}=5-2v_n$. Find its fixed point. Does the sequence converge?
3. Explain why $w_{n+1}=\sqrt{6+w_n}$ can have only the limit $3$ if all terms are non-negative and the sequence converges.

Answers

1. $L=0.3L+7$, so $0.7L=7$ and $L=10$. Since $|0.3|<1$, each step multiplies the distance from $10$ by $0.3$, so the sequence converges to $10$.
2. $L=5-2L$ gives $L=5/3$. But $|a|=2>1$, and the terms are $0,5,-5,15,-25,\ldots$, so this sequence diverges.
3. If $w_n\to L$, then $L=\sqrt{6+L}$. Squaring gives $L^2-L-6=0$, hence $L=3$ or $L=-2$. Since a square root is non-negative, $L=-2$ is inadmissible. Thus the only possible limit is $3$. This identifies the limit if convergence is known; it does not by itself prove convergence.

Recurrences in models

A recurrence is natural when the next state depends on the current state. Always define the terms and their timing before calculating.

Worked example 15: repeated percentage change with an addition

A wildlife reserve contains $1200$ animals at the start of year $1$. During each year, $15\%$ of the animals present at the start of that year leave, then $90$ animals are introduced. Let $P_n$ be the population at the start of year $n$.

After the $15\%$ loss, $85\%$ remain. The recurrence is therefore

$\boxed{P_1=1200,\qquad P_{n+1}=0.85P_n+90.}$

The next two values are

$$\begin{aligned} P_2&=0.85(1200)+90=1110,\\ P_3&=0.85(1110)+90=1033.5. \end{aligned}$$

If the model permits fractional expected populations, keep the decimal during iteration. If actual whole animals are required, follow the rounding instruction in the question.

The equilibrium population satisfies

$P=0.85P+90,$

so

$0.15P=90\qquad\Longrightarrow\qquad P=600.$

Because $|0.85|<1$, the model approaches $600$ in the long term. Starting above $600$, it decreases towards that equilibrium.

Order of events changes the model

If $90$ animals were introduced first and then $15\%$ of the resulting population left, the rule would be $P_{n+1}=0.85(P_n+90)$. Read contextual timing literally.

Common misconceptions

A recurrence needs starting values

$u_{n+1}=u_n+4$ does not determine $u_1$. It describes every arithmetic sequence with common difference $4$.

An nth term and a recurrence use different inputs

In $u_n=n^2+1$, substitute the position $n$. In $u_{n+1}=u_n^2+1$, substitute the preceding term value $u_n$.

Repetition must return to the same state

Seeing two equal values is enough to force a cycle only when the recurrence depends solely on the current state in the same way each time. For a second-order recurrence, the relevant state is the ordered pair of preceding terms.

Approaching zero is not the same as reaching zero

The sequence $u_n=(1/2)^n$ has positive terms for every finite $n$, although $u_n\to0$. A limit describes long term proximity, not necessarily a term that occurs.

Solving the fixed-point equation does not prove convergence

Always separate these statements:

1. If the sequence converges, its limit must satisfy $L=f(L)$.
2. The sequence actually converges.

For linear recurrences, $|a|<1$ supplies a direct convergence test. For more complicated recurrences, a proof may require bounds and monotonicity or other analysis.

Mixed self-check

1. Given $u_n=2n^2-n$, find $u_6$ and show that $(u_n)$ is increasing for $n\geq1$.
2. Given $v_1=4$ and $v_{n+1}=3-v_n$, find $v_2,v_3,v_4,v_5$ and state the period.
3. Write $5,11,23,47,\ldots$ as a first-order recurrence with an initial condition.
4. Given $x_1=20$ and $x_{n+1}=0.4x_n+9$, find $x_2,x_3$ and the limit.
5. A student solves $L=2L+1$ for the recurrence $y_{n+1}=2y_n+1$ and concludes that every such sequence converges to $-1$. Identify the error.

Answers

1. $u_6=2(36)-6=66$. Also $u_{n+1}-u_n=[2(n+1)^2-(n+1)]-(2n^2-n)=4n+1>0,$ so the sequence is strictly increasing.
2. The terms are $4,-1,4,-1,4$, so the period is $2$.
3. $u_1=5$ and $u_{n+1}=2u_n+1$.
4. $x_2=17$ and $x_3=15.8$. The limit satisfies $L=0.4L+9$, so $L=15$. Since $|0.4|<1$, the sequence converges to this value.
5. The fixed point $-1$ is only a candidate limit. Here the multiplier has magnitude $2>1$, so starts other than $y_1=-1$ move away from the fixed point. Only the constant sequence beginning at $-1$ converges to $-1$.

Next steps

Study arithmetic sequences and series and geometric sequences and series to obtain direct term and sum formulae for the two central families. Then learn to write sums with sigma notation and apply recursive change in sequences and series modelling.

Recurrence as numerical root-finding is developed further in numerical methods, where iteration is connected to equations, convergence and cobweb diagrams.