Recurrence Relations — AHL 1.10 Further sequences and series; modelling with recurrence relations (HL) - IB Mathematics Applications and Interpretation

SECTION 1

Historical Context & Motivation

Long before modern computers, mathematicians needed a way to describe patterns where each value depends on the ones that came before it. A recurrence relation is exactly that kind of rule: instead of giving a direct formula for the nth term, you explain how to get the next term from the previous one. Think of it like a recipe that says "to make the next batch, take what you just made and add a little more." This seemingly simple idea turns out to be incredibly powerful for modelling real-world situations such as population dynamics, financial investments, and drug dosage levels in the body.

1202 • Fibonacci's Liber Abaci

Leonardo of Pisa (Fibonacci) publishes his famous rabbit problem, defining a sequence where each term is the sum of the two before it: u_n = u_n−1 + u_n−2. This is one of the earliest recorded recurrence relations.

1718 • de Moivre's Closed-Form Solutions

Abraham de Moivre develops techniques for solving linear recurrence relations, finding explicit formulas (called closed-form solutions) for sequences previously defined only recursively.

1800s • Population Modelling

Mathematicians begin using recurrence relations to model animal populations. These discrete-time models complement the continuous differential equations being developed simultaneously.

1900s • Finance and Computing

Recurrence relations become essential in compound interest calculations, amortisation schedules, and—once computers arrive—in algorithm design and computer science.

The central question that recurrence relations answer is: how can we predict the future state of a system when each new state depends on the current one? Whether you are tracking savings in a bank account or the number of fish in a lake, recurrence relations give you a structured way to step forward one period at a time.

SECTION 2

Core Principles & Definitions

Before diving into calculations, you need to understand the building blocks of every recurrence relation. A recurrence relation has two essential ingredients: an initial condition (the starting value) and a recursive rule (the instruction that produces each subsequent term). Without both pieces, the sequence is not fully defined.

Initial Condition (u₁)

The seed value that starts the sequence. For example, u₁ = 5 tells you the first term is 5. Without this, the recursive rule has nothing to work on.

Recursive Rule (uₙ₊₁ = f(uₙ))

The formula connecting each term to the previous one. It might be linear (e.g., uₙ₊₁ = 3uₙ + 2) or more complex. The IB focuses on first-order linear relations.

First-Order vs Higher-Order

A first-order relation uses only the immediately previous term (uₙ). A second-order relation like the Fibonacci sequence uses two previous terms (uₙ and uₙ₋₁).

Homogeneous vs Non-Homogeneous

If the rule is uₙ₊₁ = ruₙ (no added constant), it's homogeneous—just a geometric sequence. Adding a constant (uₙ₊₁ = ruₙ + d) makes it non-homogeneous.

Long-Run Behaviour

Some recurrence relations settle towards a steady value called a fixed point or limit. Understanding when and why this happens is a key modelling skill.

✦

KEY TAKEAWAY

Think of a recurrence relation like a set of instructions for building a tower of blocks. The initial condition is the first block you place on the ground, and the recursive rule tells you exactly how to stack each new block on top of the last one. You can build as tall as you like, one block at a time, even if you don't have a formula for 'the height of block number 100' directly.

SECTION 3

Visualising Recurrence Relations

The diagram below shows how a first-order linear recurrence relation uₙ₊₁ = 1.5uₙ − 4 generates a sequence starting from u₁ = 20. Each point on the graph represents one term, and the arrows illustrate the 'feed-forward' process: the output of one step becomes the input for the next.

Each cyan dot represents a term uₙ. Notice how the sequence grows faster and faster—this is because the multiplier 1.5 is greater than 1, so the sequence diverges (increases without bound). If the multiplier were between −1 and 1, the sequence would converge toward a fixed point instead.

Looking at the graph, you can see the characteristic shape of exponential growth. The gap between successive terms widens because each new term is 1.5 times the previous term, minus 4. In the IB, you will encounter recurrence relations where the multiplier r controls whether the sequence grows, shrinks, or oscillates, while the constant d shifts the entire sequence up or down.

SECTION 4

Mathematical Framework

The IB syllabus focuses on first-order linear recurrence relations of the form shown below. Understanding the variables in this equation is the foundation for every modelling problem you will face.

GENERAL FIRST-ORDER LINEAR RECURRENCE

uₙ₊₁ = r × uₙ + d

uₙ = the value of the sequence at step n; r = the constant multiplier (ratio); d = the constant added each step; u₁ = the initial condition (given starting value).

When d = 0, this simplifies to uₙ₊₁ = r × uₙ, which is a geometric sequence. When r = 1, it becomes uₙ₊₁ = uₙ + d, which is an arithmetic sequence. So arithmetic and geometric sequences are actually special cases of the general linear recurrence.

CLOSED-FORM SOLUTION (WHEN r ≠ 1)

uₙ = rⁿ⁻¹ × (u₁ − d / (1 − r)) + d / (1 − r)

This formula lets you jump directly to the nth term without computing every term in between. The expression d / (1 − r) turns out to be the long-run limit of the sequence when |r| < 1.

LONG-RUN (STEADY-STATE) VALUE

L = d / (1 − r) (exists only when |r| < 1)

If |r| < 1, the sequence converges to L. At the steady state, uₙ₊₁ = uₙ = L, so substituting into the recurrence gives L = rL + d, which solves to L = d / (1 − r).

💡

IB Exam Tip

You can always find the long-run value by setting uₙ₊₁ = uₙ = L in the recurrence relation and solving for L. This technique works for any first-order relation and is a very common IB exam question.

SECTION 5

Long-Run Behaviour & Classification

The value of the multiplier r completely determines the long-run behaviour of the sequence. The diagram below classifies the four main cases you need to know. Understanding these cases will help you interpret real-world models and predict whether a system is stable or unstable.

The four quadrants show the four possible long-run behaviours determined by r. Green (0 < r < 1) converges smoothly to the steady-state value L. Red (r > 1) diverges upward. Amber (−1 < r < 0) oscillates but still converges. Orange (r < −1) oscillates with growing swings.

Value of r	Behaviour	Steady State Exists?	Real-World Example
0 < r < 1	Monotonic convergence	Yes: L = d / (1 − r)	Drug concentration after repeated doses
r = 1	Arithmetic sequence (constant growth)	No (unless d = 0)	Fixed weekly deposits in savings
r > 1	Monotonic divergence	No	Compound interest (principal grows)
−1 < r < 0	Oscillating convergence	Yes: L = d / (1 − r)	Damped price corrections
r < −1	Oscillating divergence	No	Unstable feedback loops

Classification of first-order linear recurrence relations by the multiplier r

SECTION 6

Worked Example: Medication Dosage Model

A patient takes 200 mg of a medication every 24 hours. Each day, the body eliminates 40% of the drug present in the bloodstream. We want to model the amount of medication in the patient's body just after each dose and determine the long-run level.

Medication Dosage — Recurrence Relation Model

1
Step 1 — Define Variables

Let uₙ represent the amount of medication (in mg) in the bloodstream just after the nth dose. Since 40% is eliminated each day, 60% remains, so the retention rate is r = 0.6. The dose added each day is d = 200 mg.

uₙ = amount after dose n; r = 0.6; d = 200
2
Step 2 — Write the Recurrence Relation

Just before the next dose, the amount remaining is 0.6 × uₙ. Then 200 mg is added. So the recurrence relation is:

uₙ₊₁ = 0.6 × uₙ + 200
3
Step 3 — Set the Initial Condition

Before the first dose there is no medication in the body, so just after the first dose:

u₁ = 200 mg
4
Step 4 — Generate the First Few Terms

u₂ = 0.6 × 200 + 200 = 120 + 200 = 320. u₃ = 0.6 × 320 + 200 = 192 + 200 = 392. u₄ = 0.6 × 392 + 200 = 235.2 + 200 = 435.2. Each term is getting larger, but the increases are slowing down.

u₂ = 320, u₃ = 392, u₄ = 435.2
5
Step 5 — Find the Long-Run (Steady-State) Value

Set uₙ₊₁ = uₙ = L. Then L = 0.6L + 200, so L − 0.6L = 200, giving 0.4L = 200.

L = 200 / 0.4 = 500 mg
6
Step 6 — Interpret the Result

Over time, the medication level in the patient's bloodstream approaches 500 mg. This is the balance point where the amount eliminated each day (40% of 500 = 200 mg) exactly equals the new dose taken. Because r = 0.6, which satisfies 0 < r < 1, the sequence converges monotonically to this steady state.

The patient's drug level stabilises at 500 mg.

SECTION 7

Strengths, Limitations & Comparisons

Recurrence relations are a powerful modelling tool, but like any model they have their strengths and weaknesses. The table below compares the recursive approach with the explicit (closed-form) approach and highlights when each is most useful.

Aspect	Recursive Form (uₙ₊₁ = ruₙ + d)	Closed-Form (uₙ = ...)
Ease of setup	Very easy — just describe what happens at each step	Requires algebraic derivation from the recurrence
Finding the 100th term	Must compute all 99 previous terms first	Plug n = 100 directly into the formula
Modelling intuition	Clearly shows the process: multiply, then add	Hides the step-by-step process behind algebra
GDC / technology	Spreadsheets and GDCs iterate easily	Useful for symbolic computation and graphing
Limitations	Assumes constant rate r and constant addition d	Only exists for linear recurrences; nonlinear relations have no simple closed form

Recursive vs Closed-Form: when to use which approach

✦

KEY TAKEAWAY

Recurrence relations shine when you want to model a process that repeats in discrete steps—monthly payments, annual population counts, daily drug doses. They struggle when the rate of change itself varies over time (for example, if the interest rate changes each month). In such cases, you would need a non-linear or variable-coefficient model, which goes beyond the IB syllabus.

SECTION 8

Connections to Advanced Theory

Recurrence relations are a gateway to several powerful areas of mathematics. At the HL level, you have focused on first-order linear relations, but the same ideas extend into university-level topics. The table below shows how the concepts you have learned connect to more advanced theory.

IB Concept	Advanced Extension	Where You'll See It
uₙ₊₁ = ruₙ + d	Linear difference equations (any order)	University algebra, signal processing
Steady-state L = d/(1 − r)	Fixed-point theory and stability analysis	Dynamical systems, economics
Discrete step-by-step modelling	Differential equations (continuous analogue)	Physics, engineering, biology
Fibonacci-type (second order)	Characteristic equation method	Combinatorics, computer science

From IB to university: how recurrence relations grow

If you continue to study mathematics, you will discover that recurrence relations are the discrete-time counterpart of differential equations. Where differential equations model continuous change (like the temperature of a cooling object at every instant), recurrence relations model change at fixed intervals (like temperature readings every minute). Both approaches share the same underlying concept: the future state of a system is determined by its current state plus some rule of change.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

A recurrence relation is defined by uₙ₊₁ = 0.8uₙ + 10 with u₁ = 100. Without computing any terms, explain whether this sequence will converge or diverge, and justify your answer using the value of r.

Show answer

Since r = 0.8, which satisfies 0 < r < 1, the sequence will converge to a steady-state value. The multiplier being less than 1 means each successive term retains only 80% of the previous term before the constant 10 is added. Over time, this 'decay' effect balances out the addition, and the sequence settles. The steady-state value is L = 10 / (1 − 0.8) = 10 / 0.2 = 50.

Question 2: BASIC CALCULATION

Given the recurrence relation uₙ₊₁ = 3uₙ − 5 with u₁ = 2, find u₂, u₃, and u₄.

Show answer

Apply the rule step by step. u₂ = 3 × 2 − 5 = 6 − 5 = 1. u₃ = 3 × 1 − 5 = 3 − 5 = −2. u₄ = 3 × (−2) − 5 = −6 − 5 = −11. Notice that because r = 3 > 1, the terms are diverging—they grow in magnitude rapidly. The negative values arise because the constant −5 pulls the sequence down while the multiplier amplifies each term.

Question 3: INTERMEDIATE

A savings account starts with $1 000 and earns 3% interest per year. At the end of each year, a further $500 is deposited. Write a recurrence relation for the balance Bₙ after the nth year, and find the balance after 3 years.

Show answer

The balance earns 3% interest, so each year it is multiplied by 1.03. Then $500 is added. The recurrence relation is Bₙ₊₁ = 1.03 × Bₙ + 500, with B₁ = 1000. Computing: B₂ = 1.03 × 1000 + 500 = 1030 + 500 = 1530. B₃ = 1.03 × 1530 + 500 = 1575.90 + 500 = 2075.90. B₄ = 1.03 × 2075.90 + 500 = 2138.18 + 500 = 2638.18. After the third year-end (which is B₃ if we count the initial deposit as year 1), the balance is $2 075.90. Note that r = 1.03 > 1, so this sequence diverges—the balance grows without bound, which makes sense for savings with positive deposits.

Question 4: APPLIED

A lake contains 5 000 fish. Each year, 20% of the fish die, and 600 new fish are introduced by a conservation program. Model the fish population Pₙ with a recurrence relation, find the steady-state population, and determine how many years it takes for the population to come within 50 fish of the steady state.

Show answer

With 20% dying, 80% survive, so r = 0.8 and d = 600 (fish added). The recurrence is Pₙ₊₁ = 0.8Pₙ + 600 with P₁ = 5000. The steady-state value is L = 600 / (1 − 0.8) = 600 / 0.2 = 3000 fish. Since P₁ = 5000 > 3000, the population will decrease toward 3000. Computing terms: P₂ = 4600, P₃ = 4280, P₄ = 4024, P₅ = 3819.2, P₆ = 3655.4, P₇ = 3524.3, P₈ = 3419.4, P₉ = 3335.5, P₁₀ = 3268.4, P₁₁ = 3214.7, P₁₂ = 3171.8, P₁₃ = 3137.4, P₁₄ = 3109.9, P₁₅ = 3088.0, P₁₆ = 3070.4, P₁₇ = 3056.3, P₁₈ = 3045.0. Since |P₁₈ − 3000| = 45 < 50, the population comes within 50 fish of the steady state after approximately 18 years.

Question 5: CRITICAL THINKING

Consider the recurrence relation uₙ₊₁ = ruₙ + d with u₁ = 80 and a steady-state value of L = 50. If u₂ = 68, determine the values of r and d. Then explain why the sequence reaches the same steady state regardless of the initial condition u₁ (as long as |r| < 1).

Show answer

From the steady-state condition, L = d / (1 − r) gives 50 = d / (1 − r), so d = 50(1 − r). From u₂ = ru₁ + d: 68 = 80r + d. Substituting d = 50(1 − r): 68 = 80r + 50 − 50r = 30r + 50. Solving: 30r = 18, so r = 0.6. Then d = 50(1 − 0.6) = 50 × 0.4 = 20. To understand why the steady state is independent of u₁, consider the closed form: uₙ = rⁿ⁻¹(u₁ − L) + L. As n → ∞, the term rⁿ⁻¹ → 0 (because |r| < 1), so regardless of u₁, the term rⁿ⁻¹(u₁ − L) vanishes and uₙ → L. The initial condition only affects how quickly the sequence reaches L, not the value it approaches.

SUMMARY

Lesson Summary

Summary

A recurrence relation defines each term of a sequence using the previous term. The standard first-order linear form is uₙ₊₁ = r × uₙ + d, where r is the multiplier and d is the constant. When d = 0, you get a geometric sequence; when r = 1, you get an arithmetic sequence. The value of r determines the long-run behaviour: if |r| < 1, the sequence converges to a steady-state value L = d / (1 − r); if |r| ≥ 1, it diverges.

To find the steady-state value, set uₙ₊₁ = uₙ = L and solve for L—a technique frequently tested on IB exams. Modelling with recurrence relations involves identifying the multiplier r (often a retention or growth rate), the constant d (a regular addition like a deposit or dose), and the initial condition u₁. These models are ideal for discrete processes such as annual interest, daily medication, and seasonal population changes. The closed-form solution uₙ = rⁿ⁻¹(u₁ − L) + L allows you to jump directly to any term without iterating through every previous one.