Recursive Sequences & Series — AHL 2.11 Sequences and...

SECTION 1

Historical Context & Motivation

Long before calculators and computers existed, mathematicians noticed that many interesting patterns in nature and commerce could not be captured by a simple closed formula. Instead, each new value in a sequence depended on the values that came before it. This idea — that the next term is built from previous terms — is the beating heart of recursive sequences. From modelling rabbit populations to predicting financial growth, recursion turns up everywhere.

c. 200 BCE

Pingala's Binary Patterns

The Indian mathematician Pingala studied metrical patterns in Sanskrit poetry and encountered sequences whose terms depended on earlier terms, foreshadowing what we now call the Fibonacci sequence.

1202

Fibonacci's Liber Abaci

Leonardo of Pisa (Fibonacci) introduced his famous rabbit-breeding problem to Europe. Each month's population is the sum of the two previous months — a classic second-order recurrence relation.

1654

Pascal & Fermat on Probability

Pascal and Fermat exchanged letters on gambling problems. Pascal's triangle, generated recursively, became a cornerstone of combinatorics and probability theory.

1748

Euler's Analytic Methods

Leonhard Euler developed techniques for solving linear recurrence relations using characteristic equations, connecting recursion to algebra and calculus.

1936–present

Computer Science & Algorithms

Alan Turing and later computer scientists made recursion a fundamental concept in programming. Today, recursive algorithms power everything from search engines to fractal art.

At its core, the study of recursive sequences asks a deceptively simple question: if each term depends on the ones before it, can we predict where the sequence goes? In the IB HL extension, you will learn to define sequences with recurrence relations, compute their terms, sum their series, and connect them to explicit (closed-form) formulas when possible.

SECTION 2

Core Principles & Definitions

Before diving into calculations, you need to be comfortable with several foundational ideas. A sequence is an ordered list of numbers, and a series is the sum of a sequence's terms. When a sequence is defined recursively, each term is expressed as a function of one or more preceding terms, together with a starting value called an initial condition.

Recurrence Relation

A rule that relates uₙ₊₁ to previous terms such as uₙ, uₙ₋₁, etc. For example, uₙ₊₁ = 3uₙ − 2. Without this rule, the sequence is undefined.

Initial Condition(s)

The starting value(s) that anchor the sequence. A first-order recurrence needs one initial value (e.g., u₁ = 5); a second-order recurrence needs two (e.g., u₁ = 1, u₂ = 1).

Order of a Recurrence

The number of previous terms needed. First-order uses only uₙ to find uₙ₊₁; second-order uses uₙ and uₙ₋₁. Higher orders exist but are rare at HL level.

Explicit (Closed-Form) Formula

A formula that gives uₙ directly in terms of n, without needing earlier terms. Converting a recurrence to a closed form is a key goal — when it is possible.

Fixed Point / Steady State

A value L such that if the sequence converges, it approaches L. Found by setting uₙ₊₁ = uₙ = L in the recurrence and solving for L.

✦ KEY TAKEAWAY

Think of a recursive sequence like a recipe where each step says "take what you made in the last step and do this to it." You can't jump to step 50 without doing steps 1 through 49 first — unless you find a shortcut formula (the closed form). The recurrence relation is the recipe instruction, and the initial condition is the first ingredient you start with.

SECTION 3

Visual Explanation — Recursive Generation

The diagram below shows how a first-order linear recurrence relation generates its terms step by step. Each term feeds into the recurrence rule to produce the next, creating a chain of values. Notice how the initial condition (u₁) is the starting point, and the recurrence relation acts as the engine that drives everything forward.

Each coloured box represents a term in the sequence. The RULE boxes show the recurrence relation being applied. The verification panel confirms that the closed-form formula produces the same values.

As the diagram illustrates, the recursive approach computes each term one at a time — you must know u₄ before you can find u₅. The closed-form formula, on the other hand, lets you leap directly to any term. Not every recurrence has a neat closed form, which is why understanding both representations is essential at HL level.

SECTION 4

Mathematical Framework

In IB Mathematics HL, you will encounter several standard forms of recurrence relations. Understanding their structure lets you recognize which technique to apply. Below are the key equations you need to master.

FIRST-ORDER LINEAR RECURRENCE

uₙ₊₁ = a · uₙ + b

Here a is the multiplicative constant, b is the additive constant, and u₁ is given. When b = 0, this is a geometric sequence with common ratio a. When a = 1, this is an arithmetic sequence with common difference b.

CLOSED FORM FOR uₙ₊₁ = a·uₙ + b (a ≠ 1)

uₙ = aⁿ⁻¹ · u₁ + b · (aⁿ⁻¹ − 1) / (a − 1)

This formula is derived by repeatedly substituting the recurrence back into itself ("unwinding" or "telescoping"). For a = 1, the closed form simplifies to uₙ = u₁ + (n − 1)b, which is the familiar arithmetic formula.

SECOND-ORDER LINEAR RECURRENCE

uₙ₊₂ = p · uₙ₊₁ + q · uₙ

Requires two initial conditions (u₁ and u₂). The Fibonacci sequence is the special case p = 1, q = 1 with u₁ = u₂ = 1. Solving involves the characteristic equation r² − p·r − q = 0.

FIXED POINT (STEADY STATE)

L = a · L + b ⟹ L = b / (1 − a) (when |a| < 1)

If a sequence converges, it approaches the fixed point L. The condition |a| < 1 ensures convergence. If |a| ≥ 1, the sequence diverges (grows without bound or oscillates).

📝 IB EXAM TIP

On the IB HL exam, you may be asked to use your GDC (graphing calculator) to generate terms of a recursive sequence. On the TI-84, enter the initial value, press ENTER, then type the recurrence formula using Ans for the previous term. Pressing ENTER repeatedly generates successive terms.

SECTION 5

Types of Recursive Sequences & Their Behaviour

Recursive sequences behave very differently depending on their parameters. The value of a in a first-order linear recurrence controls whether the sequence converges, diverges, or oscillates. The diagram below plots four representative cases to help you build intuition.

The green curve (a = 0.5) smoothly approaches the fixed point L from one side. The cyan curve (a = −0.6) oscillates above and below L but still converges. The red curve (a = 1.3) diverges monotonically, while the amber curve (a = −1.1) diverges with increasing oscillations.

Summary of convergence behaviour by value of a

Value of a	Behaviour	Converges?	Pattern
0 < a < 1	Terms approach L from one side	Yes	Monotonic convergence
−1 < a < 0	Terms alternate above and below L	Yes	Oscillating convergence
a > 1	Terms grow without bound	No	Monotonic divergence
a < −1	Terms swing wider each iteration	No	Oscillating divergence
a = 1	Arithmetic sequence (constant differences)	Only if b = 0	Linear growth or constant

SECTION 6

Worked Example

Let's work through a full IB-style problem that tests multiple skills: computing terms, finding a fixed point, and determining a series sum.

Recursive Sequence: Convergence & Series Sum

Step 1 — Read the ProblemA sequence is defined by uₙ₊₁ = 0.4uₙ + 6, with u₁ = 2. (a) Find u₂, u₃, u₄, and u₅. (b) Find the value L that the sequence approaches. (c) Find Σ from n = 1 to 5 of uₙ (the sum of the first five terms).

Step 2 — Generate Terms (Part a)Apply the recurrence relation repeatedly. Start with u₁ = 2. Then u₂ = 0.4(2) + 6 = 0.8 + 6 = 6.8. Next, u₃ = 0.4(6.8) + 6 = 2.72 + 6 = 8.72. Then u₄ = 0.4(8.72) + 6 = 3.488 + 6 = 9.488. Finally, u₅ = 0.4(9.488) + 6 = 3.7952 + 6 = 9.7952.

u₂ = 6.8, u₃ = 8.72, u₄ = 9.488, u₅ = 9.7952

Step 3 — Find the Fixed Point (Part b)If the sequence converges, then as n → ∞, both uₙ₊₁ and uₙ approach the same limit L. Set L = 0.4L + 6. Subtract 0.4L from both sides to get 0.6L = 6. Divide both sides by 0.6 to find L = 10. Since |a| = 0.4 < 1, convergence is guaranteed.

L = 10

Step 4 — Sum the First Five Terms (Part c)S₅ = u₁ + u₂ + u₃ + u₄ + u₅ = 2 + 6.8 + 8.72 + 9.488 + 9.7952. Add these values: S₅ = 36.8032.

S₅ = 36.8032

Step 5 — Reflect & VerifyNotice how the terms are increasing toward 10 and slowing down — this is classic monotonic convergence with 0 < a < 1. Each successive term is closer to L = 10 by a factor of 0.4 (the "gap" between uₙ and 10 shrinks by 60% each step). On an exam, you can use your GDC to confirm these values quickly.

SECTION 7

Recursive vs. Explicit Definitions — Strengths & Limitations

One of the most important skills in this topic is knowing when to use a recursive definition and when to convert to an explicit (closed-form) one. Each approach has its strengths and limitations, which the table below summarizes.

Comparing recursive and explicit sequence definitions

Feature	Recursive Definition	Explicit (Closed-Form)
What it looks like	uₙ₊₁ = f(uₙ), u₁ given	uₙ = g(n)
Ease of finding u₁₀₀	Must compute u₂ through u₉₉ first (slow)	Substitute n = 100 directly (fast)
Ease of definition	Often simpler and more natural for modelling	Can be hard or impossible to derive
Summing a series	Must generate each term then add them	May use sigma notation or known formulas
Real-world use	Population models, drug dosage, algorithms	Interest calculations, physics formulas
Always exists?	Yes — any sequence can be defined recursively	No — many recursions have no simple closed form

✦ KEY TAKEAWAY

Think of the recursive form as giving driving directions ("turn left, go 2 blocks, turn right…") — they get you there step by step. The explicit form is like giving a GPS coordinate — you jump directly to the destination. Both describe the same location, but each is better suited to different situations.

SECTION 8

Connection to Advanced Theory

The recursive sequences you learn at HL level are the gateway to several powerful areas of university mathematics and computer science. Understanding where these ideas lead can motivate deeper engagement with the material right now.

From IB HL to university-level extensions

IB HL Concept	University Extension	Application
First-order linear recurrence uₙ₊₁ = auₙ + b	Discrete dynamical systems & iteration theory	Chaos theory, fractals, weather modelling
Second-order recurrence (Fibonacci type)	Characteristic equations & eigenvalue methods	Algorithm analysis, structural engineering
Fixed points and convergence	Fixed-point theorems (Banach, Brouwer)	Numerical methods for solving equations
Summing recursive series	Generating functions & Z-transforms	Signal processing, combinatorics

If you pursue mathematics, physics, computer science, or economics at university, you will encounter recurrence relations in increasingly sophisticated forms. The logistic map uₙ₊₁ = r·uₙ(1 − uₙ), for instance, is a simple-looking recurrence that produces stunningly complex behaviour — including chaos — depending on the value of r. Mastering the HL fundamentals now gives you a head start on these fascinating topics.

🔭 LOOKING AHEAD

In the IB exam, recurrence questions often appear in Paper 1 (no calculator) for symbolic manipulation and Paper 2 (GDC allowed) for numerical term generation and series sums. Being fluent in both approaches — algebraic and computational — is the key to full marks.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain, in your own words, why a recursive sequence defined by uₙ₊₁ = auₙ + b requires an initial condition u₁ to be fully determined. What would happen if u₁ were changed while keeping a and b the same?

PROBLEM 2 — BASIC CALCULATION

A sequence is defined by uₙ₊₁ = 3uₙ − 4, with u₁ = 5. Calculate u₂, u₃, and u₄. Then find the sum S₃ = u₁ + u₂ + u₃.

PROBLEM 3 — INTERMEDIATE

Consider the recurrence uₙ₊₁ = −0.5uₙ + 9, with u₁ = 3. (a) Find the fixed point L. (b) Calculate u₂ through u₆. (c) Describe the long-term behaviour of the sequence and explain why it behaves this way.

PROBLEM 4 — APPLIED

A patient takes 200 mg of a medication every 24 hours. Each day, the body eliminates 70% of the drug present at the start of the day, retaining 30%. Let uₙ represent the total amount of medication in the body just after taking the nth dose. (a) Write a recurrence relation for uₙ₊₁ in terms of uₙ. (b) Find the long-run (steady-state) drug level. (c) What percentage of the steady state is reached after 5 doses?

PROBLEM 5 — CRITICAL THINKING

A second-order recurrence is defined by uₙ₊₂ = uₙ₊₁ + uₙ, with u₁ = 1, u₂ = 1 (the Fibonacci sequence). (a) Show that the ratio uₙ₊₁/uₙ appears to approach a limit φ. Calculate this ratio for n = 2 through n = 8. (b) If the ratio converges to φ, explain why φ must satisfy φ = 1 + 1/φ. Solve this equation to find the exact value of φ.

SUMMARY

Lesson Summary

A recursive sequence defines each term as a function of previous terms using a recurrence relation (such as uₙ₊₁ = auₙ + b) together with one or more initial conditions. The parameter a controls the sequence's long-term behaviour: when |a| < 1 the sequence converges to a fixed point L = b/(1 − a), and when |a| ≥ 1 it diverges. A negative value of a produces oscillating behaviour, while a positive a gives monotonic behaviour.

When possible, converting a recursive definition to an explicit (closed-form) formula allows you to compute any term directly. Second-order recurrences (like the Fibonacci sequence) require two initial conditions and lead to the study of characteristic equations. In applied contexts — from drug dosing to population modelling — recursive sequences are indispensable tools for representing systems where each state depends on the previous one. Master both the algebraic and computational approaches to be fully prepared for the IB HL exam.