What is index confusion?

Be careful whether the sequence starts at u_0 or u_1; the initial conditions must match the stated starting index.

SEAB Original-style practice: A sequence satisfies u_n+2 = 5u_n+1 - 6u_n with u_0 = 1 and u_1 = 0. Find u_n in terms of n.

Form the characteristic equation by trying u_n = λ^n: λ^2 = 5λ - 6, that is λ^2 - 5λ + 6 = 0. Factor: (λ - 2)(λ - 3) = 0, so λ = 2 or λ = 3 (distinct real roots). General solution: u_n = A\,2^n + B\,3^n. Apply the initial conditions. u_0 = 1: A + B = 1. u_1 = 0: 2A + 3B = 0. From the first, A = 1 - B. Substitute: 2(1-B) + 3B = 0 2 + B = 0 B = -2, so A = 3. $u_n = 3· 2^n - 2· 3^n.$ Markers reward the characteristic equation, its roots, the general solution with two constants, solving the simultaneous equations from the initial conditions, and the final closed form.

SingaporeFurther MathsSyllabus dot point

How do we solve linear recurrence relations to find a closed form for the nth term?

Solve first- and second-order linear recurrence relations with constant coefficients and find closed-form expressions for the nth term

A focused answer to the H2 Further Mathematics outcome on linear recurrence relations. First-order and second-order constant-coefficient recurrences, the characteristic equation, repeated and complex roots, and particular solutions for non-homogeneous cases.

Generated by Claude Opus 4.811 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to solve linear recurrence relations with constant coefficients, both first-order ( $u_{n+1}$ in terms of $u_n$ ) and second-order ( $u_{n+2}$ in terms of $u_{n+1}$ and $u_n$ ), and to produce a closed-form expression for $u_n$ as an explicit function of $n$ . The method mirrors the solution of linear differential equations: a homogeneous part plus a particular part, with constants fixed by initial conditions.

The answer

First-order linear recurrences

A first-order linear recurrence has the form $u_{n+1} = a\,u_n + b$ with constants $a$ and $b$ .

Homogeneous part ( $b = 0$ ): $u_{n+1} = a\,u_n$ gives the geometric solution $u_n^{(h)} = A\,a^{n}$ .
Particular part: if $a \neq 1$ , try a constant $u_n^{(p)} = c$ ; substituting gives $c = \dfrac{b}{1-a}$ . If $a = 1$ the constant fails, so try $u_n^{(p)} = cn$ .

The general solution is the sum $u_n = u_n^{(h)} + u_n^{(p)}$ , and the single constant $A$ is fixed by the initial value.

Second-order linear recurrences and the characteristic equation

A homogeneous second-order recurrence $u_{n+2} = p\,u_{n+1} + q\,u_n$ is solved by trying $u_n = \lambda^n$ . Substituting and dividing by $\lambda^n$ gives the characteristic equation

\lambda^2 = p\lambda + q \quad\Longleftrightarrow\quad \lambda^2 - p\lambda - q = 0.

The form of the general solution depends on its roots.

The three cases for the roots

Distinct real roots $\lambda_1 \neq \lambda_2$ : $\;u_n = A\,\lambda_1^{n} + B\,\lambda_2^{n}$ .
Repeated real root $\lambda$ : $\;u_n = (A + Bn)\,\lambda^{n}$ .
Complex roots $\lambda = r\mathrm{e}^{\pm i\theta}$ : $\;u_n = r^{n}\left(A\cos n\theta + B\sin n\theta\right)$ .

Two constants $A$ and $B$ are fixed by two initial conditions.

Non-homogeneous second-order recurrences

If the recurrence has an extra term, $u_{n+2} = p\,u_{n+1} + q\,u_n + f(n)$ , add a particular solution matching the form of $f(n)$ (a constant for constant $f$ , a linear $cn + d$ for linear $f$ , and so on) to the homogeneous solution, then apply the initial conditions last.

Worked example

Solve $u_{n+2} = 4u_{n+1} - 4u_n$ with $u_0 = 1$ , $u_1 = 3$ .

Step 1: Write the characteristic equation

Try $u_n = \lambda^n$ : $\lambda^2 = 4\lambda - 4$ , so $\lambda^2 - 4\lambda + 4 = 0$ .

Step 2: Solve for the roots

$(\lambda - 2)^2 = 0$ , so $\lambda = 2$ is a repeated root.

Step 3: Write the general solution for a repeated root

For a repeated root the solution is

u_n = (A + Bn)\,2^{n}.

Step 4: Apply the initial conditions

$u_0 = 1$ : $(A + 0)\,2^0 = A = 1$ .

$u_1 = 3$ : $(A + B)\,2^1 = 2(1 + B) = 3$ , so $1 + B = \tfrac{3}{2}$ , giving $B = \tfrac{1}{2}$ .

Step 5: State the closed form

u_n = \left(1 + \tfrac{1}{2}n\right)2^{n} = (2 + n)\,2^{\,n-1}.

Common traps

Using one constant for a second-order recurrence: A second-order recurrence needs two arbitrary constants and two initial conditions; one constant cannot match both.
Missing the $n$ factor for a repeated root: A repeated root $\lambda$ gives $(A + Bn)\lambda^n$ , not $A\lambda^n$ ; without the $Bn$ term the solution space is too small.
Trying a constant particular solution when $a = 1$: If the first-order coefficient is $1$ , a constant trial fails (it solves the homogeneous equation); use $cn$ instead.
Fitting constants before adding the particular part: Always combine homogeneous and particular solutions first, then apply initial values.
Index confusion: Be careful whether the sequence starts at $u_0$ or $u_1$ ; the initial conditions must match the stated starting index.

Examples in context

Example 1. Compound interest with regular deposits. A savings balance that grows by a fixed rate and receives a fixed annual deposit satisfies $u_{n+1} = a\,u_n + b$ . Its closed form $u_n = A a^n + \tfrac{b}{1-a}$ separates the compounding growth from the steady-state level the deposits sustain.

Example 2. The Fibonacci connection. The Fibonacci recurrence $u_{n+2} = u_{n+1} + u_n$ has characteristic equation $\lambda^2 - \lambda - 1 = 0$ , whose roots are the golden ratio and its conjugate; this gives Binet's closed form, a classic demonstration of the characteristic-equation method.

Try this

Q1. Write the characteristic equation of $u_{n+2} = u_{n+1} + 6u_n$ and find its roots. [2 marks]

Cue. $\lambda^2 - \lambda - 6 = 0$ , factoring to $(\lambda - 3)(\lambda + 2) = 0$ , so $\lambda = 3$ or $\lambda = -2$ .

Q2. Give the general solution of a second-order recurrence whose characteristic equation has a repeated root $\lambda = 5$ . [1 mark]

Cue. $u_n = (A + Bn)\,5^{n}$ .

Q3. For $u_{n+1} = 2u_n + 6$ , find the constant particular solution. [2 marks]

Cue. Try $u_n = c$ : $c = 2c + 6 \Rightarrow c = -6$ .

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original6 marksA sequence is defined by

u_{n+1} = 3u_n + 4

with

u_1 = 2

. Find a closed-form expression for

u_n

in terms of

n

Show worked answer →

This is a first-order linear recurrence. Solve the homogeneous part $u_{n+1} = 3u_n$ , which gives $u_n^{(h)} = A\,3^{n}$ for a constant $A$ .

For a particular solution, try a constant $u_n^{(p)} = c$ . Then $c = 3c + 4$ , so $-2c = 4$ , $c = -2$ .

General solution: $u_n = A\,3^{n} - 2$ .

Apply $u_1 = 2$ : $2 = 3A - 2$ , so $3A = 4$ , $A = \tfrac{4}{3}$ . Hence

u_n = \tfrac{4}{3}\cdot 3^{n} - 2 = 4\cdot 3^{n-1} - 2.

Markers reward the homogeneous solution $A\,3^n$ , a correct constant particular solution, applying the initial condition, and a simplified closed form.

Original7 marksA sequence satisfies

u_{n+2} = 5u_{n+1} - 6u_n

with

u_0 = 1

and

u_1 = 0

. Find

u_n

in terms of

n

Show worked answer →

Form the characteristic equation by trying $u_n = \lambda^n$ : $\lambda^2 = 5\lambda - 6$ , that is $\lambda^2 - 5\lambda + 6 = 0$ .

Factor: $(\lambda - 2)(\lambda - 3) = 0$ , so $\lambda = 2$ or $\lambda = 3$ (distinct real roots).

General solution: $u_n = A\,2^{n} + B\,3^{n}$ .

Apply the initial conditions. $u_0 = 1$ : $A + B = 1$ . $u_1 = 0$ : $2A + 3B = 0$ .

From the first, $A = 1 - B$ . Substitute: $2(1-B) + 3B = 0 \Rightarrow 2 + B = 0 \Rightarrow B = -2$ , so $A = 3$ .

u_n = 3\cdot 2^{n} - 2\cdot 3^{n}.

Markers reward the characteristic equation, its roots, the general solution with two constants, solving the simultaneous equations from the initial conditions, and the final closed form.