Welcome to Recurrence Relationships
Welcome to one of the most practical and elegant topics in AS 2 Section D: Discrete and Decision Mathematics! Have you ever wondered how a bank calculates the balance on a mortgage month after month, or how computer algorithms calculate the steps needed to solve complex puzzles? The answer lies in recurrence relationships.
A recurrence relation is simply a mathematical rule that generates the next term of a sequence using previous terms. If you have ever used a term-to-term rule in earlier maths classes (like "start at \(3\) and add \(4\) each time"), you have already worked with recurrence relations! In this module, we will learn how to turn these step-by-step rules into direct "closed-form" formulae, allowing us to jump straight to the \(n\)th term, \(u_n\), without calculating every single step along the way.
Don't worry if this seems tricky at first — we will break down every method into clear, repeatable steps with straightforward examples.
---1. Core Concepts and Classifications
Before solving recurrence relations, let's establish the key terminology you need to know for your CCEA examination.
What is a Recurrence Relation?
A recurrence relation is an equation that defines a sequence where each term is given as a function of preceding terms, such as \(u_n = f(u_{n-1}, u_{n-2}, \dots)\), alongside specified initial conditions (also known as boundary values) that fix the starting points of the sequence.
Order of a Recurrence Relation
The order is the difference between the highest and lowest subscripts (indices) appearing in the equation:
• First-Order: The relation connects terms differing by \(1\) index (for example, \(u_{n+1}\) and \(u_n\)).
• Second-Order: The relation connects terms differing by \(2\) indices (for example, \(u_{n+2}\), \(u_{n+1}\), and \(u_n\)).
Linear Recurrence Relations with Constant Coefficients
In this unit, we focus on linear relations where the coefficients multiplying the sequence terms are constant real numbers. The standard form is:
\(a_k u_{n+k} + a_{k-1} u_{n+k-1} + \dots + a_0 u_n = f(n)\)
where \(a_i\) are real constants and \(a_k \neq 0\).
Homogeneous vs. Non-Homogeneous
• Homogeneous: When the right-hand side is zero, so \(f(n) = 0\). For example: \(u_{n+1} - 3u_n = 0\).
• Non-Homogeneous (Inhomogeneous): When there is a separate function of \(n\) on the right-hand side, so \(f(n) \neq 0\). For example: \(u_{n+1} - 3u_n = 5\).
The Master Structure of Solutions
For any linear non-homogeneous recurrence relation, the complete General Solution consists of two distinct parts added together:
\(u_n = u_n^{(c)} + u_n^{(p)}\)
• Complementary Function \(u_n^{(c)}\): The general solution to the associated homogeneous equation (setting \(f(n) = 0\)).
• Particular Solution \(u_n^{(p)}\): A specific sequence that satisfies the complete non-homogeneous equation.
Key Takeaway: Always identify the order of the relation first, check whether it is homogeneous or non-homogeneous, and remember that full solutions are built from \(u_n = u_n^{(c)} + u_n^{(p)}\).
---2. First-Order Linear Recurrence Relations
A first-order linear recurrence relation with constant coefficients has the form:
\(u_{n+1} - a u_n = f(n)\)
A. Homogeneous First-Order Relations: \(u_{n+1} - a u_n = 0\)
To solve \(u_{n+1} - a u_n = 0\), we set up the characteristic equation: \(\lambda - a = 0 \implies \lambda = a\).
The general solution is simply:
\(u_n = A a^n\)
where \(A\) is an arbitrary constant determined by an initial condition (such as \(u_0\) or \(u_1\)).
Example: Solve \(u_{n+1} = 3u_n\) with \(u_0 = 4\).
Here \(a = 3\), so \(u_n = A (3^n)\). Using \(u_0 = 4 \implies A(3^0) = 4 \implies A = 4\).
Thus, \(u_n = 4(3^n)\).
B. Non-Homogeneous First-Order Relations: \(u_{n+1} - a u_n = f(n)\)
When \(f(n) \neq 0\), we find the Complementary Function \(u_n^{(c)} = A a^n\) and add an appropriate trial Particular Solution \(u_n^{(p)}\) using the Method of Undetermined Coefficients:
• Constant Right-Hand Side (\(f(n) = c\)):
Try \(u_n^{(p)} = k\) (a constant).
Exception (Root collision / Resonance): If \(a = 1\) (which means the constant is already part of the complementary function since \(1^n = 1\)), try \(u_n^{(p)} = k n\).
• Linear Polynomial Right-Hand Side (\(f(n) = c n + d\)):
Try \(u_n^{(p)} = p n + q\).
• Geometric/Exponential Right-Hand Side (\(f(n) = c \cdot k^n\)):
Try \(u_n^{(p)} = C \cdot k^n\).
Exception: If \(k = a\), try \(u_n^{(p)} = C n k^n\).
Step-by-Step Worked Example: First-Order Non-Homogeneous
Problem: Find the closed-form solution for \(u_{n+1} - 2u_n = 3\) with initial condition \(u_0 = 5\).
Step 1: Find the Complementary Function \(u_n^{(c)}\)
Solve the homogeneous relation \(u_{n+1} - 2u_n = 0\).
Characteristic equation: \(\lambda - 2 = 0 \implies \lambda = 2\).
So, \(u_n^{(c)} = A(2^n)\).
Step 2: Find the Particular Solution \(u_n^{(p)}\)
The right-hand side is the constant \(3\). Try \(u_n^{(p)} = k\).
Substitute \(u_n = k\) into the original recurrence relation \(u_{n+1} - 2u_n = 3\):
\(k - 2k = 3 \implies -k = 3 \implies k = -3\).
So, \(u_n^{(p)} = -3\).
Step 3: Combine to Form the General Solution
\(u_n = u_n^{(c)} + u_n^{(p)} = A(2^n) - 3\).
Step 4: Apply the Initial Condition to Find \(A\)
Substitute \(n = 0\) and \(u_0 = 5\):
\(5 = A(2^0) - 3 \implies 5 = A - 3 \implies A = 8\).
Therefore, the particular sequence is \(u_n = 8(2^n) - 3\).
Key Takeaway: Always find \(u_n^{(c)}\) and \(u_n^{(p)}\) first, combine them into \(u_n = u_n^{(c)} + u_n^{(p)}\), and only then apply the initial condition to find \(A\)!
---3. Second-Order Linear Homogeneous Recurrence Relations
A second-order linear homogeneous recurrence relation has the form:
\(a u_{n+2} + b u_{n+1} + c u_n = 0\)
where \(a \neq 0\), \(b\), and \(c\) are real constants.
The Characteristic Auxiliary Equation
We try a solution of the form \(u_n = \lambda^n\). Substituting this into the recurrence relation gives:
\(a \lambda^{n+2} + b \lambda^{n+1} + c \lambda^n = 0\)
Dividing through by \(\lambda^n\) gives the Characteristic Auxiliary Equation:
\(a \lambda^2 + b \lambda + c = 0\)
Depending on the discriminant \(\Delta = b^2 - 4ac\), three distinct cases arise:
Case 1: Two Distinct Real Roots (\(b^2 - 4ac > 0\))
If the quadratic yields two different real roots \(\lambda_1 \neq \lambda_2\), the general solution is:
\(u_n = A \lambda_1^n + B \lambda_2^n\)
where \(A\) and \(B\) are arbitrary constants determined by two initial values (e.g., \(u_0\) and \(u_1\)).
Case 2: One Repeated Real Root (\(b^2 - 4ac = 0\))
If the quadratic yields a single repeated root \(\lambda_1 = \lambda_2 = \lambda\), the general solution is:
\(u_n = (A + B n)\lambda^n\)
Case 3: Complex Conjugate Roots (\(b^2 - 4ac < 0\))
When the roots are complex conjugates, \(\lambda = p \pm i q\), we convert them to modulus-argument polar form:
Modulus: \(r = |\lambda| = \sqrt{p^2 + q^2}\)
Argument: \(\theta = \arctan\left(\frac{q}{p}\right)\) (taking careful account of the quadrant in the complex plane).
The roots are \(\lambda = r(\cos \theta \pm i \sin \theta)\). Using de Moivre's theorem, the real general solution is:
\(u_n = r^n \big(A \cos(n\theta) + B \sin(n\theta)\big)\)
Summary Table of Homogeneous Cases
Distinct Real Roots: \(u_n = A \lambda_1^n + B \lambda_2^n\)
Repeated Real Root: \(u_n = (A + B n)\lambda^n\)
Complex Conjugate Roots: \(u_n = r^n(A \cos(n\theta) + B \sin(n\theta))\)
Step-by-Step Worked Example: Distinct Real Roots
Problem: Solve \(u_{n+2} - 5u_{n+1} + 6u_n = 0\) given \(u_0 = 1\) and \(u_1 = 4\).
Step 1: Write down and solve the characteristic equation
\(\lambda^2 - 5\lambda + 6 = 0 \implies (\lambda - 2)(\lambda - 3) = 0\)
The roots are \(\lambda_1 = 2\) and \(\lambda_2 = 3\).
Step 2: State the general solution
\(u_n = A(2^n) + B(3^n)\)
Step 3: Substitute the initial conditions to find \(A\) and \(B\)
For \(n = 0\): \(u_0 = A(2^0) + B(3^0) \implies A + B = 1\)
For \(n = 1\): \(u_1 = A(2^1) + B(3^1) \implies 2A + 3B = 4\)
Step 4: Solve the simultaneous equations
From the first equation: \(A = 1 - B\).
Substitute into the second equation: \(2(1 - B) + 3B = 4 \implies 2 + B = 4 \implies B = 2\).
Then \(A = 1 - 2 = -1\).
The exact closed-form solution is: \(u_n = -(2^n) + 2(3^n)\).
Key Takeaway: For second-order equations, two initial conditions are required to determine the two constants \(A\) and \(B\).
---4. Second-Order Linear Non-Homogeneous Recurrence Relations
A second-order non-homogeneous relation has the form:
\(a u_{n+2} + b u_{n+1} + c u_n = f(n)\)
Method of Undetermined Coefficients: The 4-Step Plan
Step 1: Solve the auxiliary equation \(a \lambda^2 + b \lambda + c = 0\) to obtain the Complementary Function \(u_n^{(c)}\).
Step 2: Choose an appropriate trial form for the Particular Solution \(u_n^{(p)}\) based on \(f(n)\):
• If \(f(n) = k\) (constant), try \(u_n^{(p)} = C\). (If \(1\) is a root of the auxiliary equation, try \(u_n^{(p)} = C n\); if \(1\) is a repeated root, try \(C n^2\)).
• If \(f(n) = p n + q\) (linear), try \(u_n^{(p)} = C n + D\).
• If \(f(n) = k \cdot d^n\) (geometric), try \(u_n^{(p)} = C \cdot d^n\). (If \(d\) matches a root of the auxiliary equation, multiply by \(n\)).
Step 3: Substitute \(u_n^{(p)}\) back into the full recurrence relation to solve for the undetermined constants.
Step 4: Form the complete General Solution \(u_n = u_n^{(c)} + u_n^{(p)}\), then substitute the initial conditions to solve for the constants \(A\) and \(B\).
Key Takeaway: Never apply initial conditions until you have written down the full sum \(u_n = u_n^{(c)} + u_n^{(p)}\)!
---5. Modelling Applications
Recurrence relations are powerful tools for modelling real-world discrete processes. Here are the core models you will encounter in AS 2 Section D:
A. Financial Mathematics: Compound Interest, Savings, and Loans
When an amount is borrowed or invested, interest is added at each interval, and regular payments or withdrawals are made.
Let \(u_n\) be the loan balance after \(n\) payment periods, \(r\) be the interest rate per period, and \(D\) be the regular constant repayment.
The recurrence relation is:
\(u_{n+1} = (1 + r)u_n - D\)
• Homogeneous part: \(u_n^{(c)} = A(1 + r)^n\)
• Particular solution: Try \(u_n^{(p)} = k \implies k = (1 + r)k - D \implies r k = D \implies k = \frac{D}{r}\).
• General model: \(u_n = A(1 + r)^n + \frac{D}{r}\), where \(A\) is set by the initial loan balance \(u_0\).
B. Combinatorics and Classic Discrete Problems
• The Tower of Hanoi: To move \(n\) disks from one peg to another following the puzzle's rules, moving \(n\) disks requires moving \(n-1\) disks twice plus \(1\) move for the largest disk:
\(T_n = 2T_{n-1} + 1\) with \(T_1 = 1\)
Solving this gives the famous formula: \(T_n = 2^n - 1\).
• Fibonacci Step Counting: The number of ways to climb a staircase of \(n\) steps taking either \(1\) or \(2\) steps at a time satisfies:
\(F_n = F_{n-1} + F_{n-2}\)
Did You Know? Recurrence relationships are the discrete counterpart of differential equations! While calculus models continuous change (like fluid flowing continuously through a pipe), recurrence relations model discrete steps (like interest applied at the end of each month or turns taken in an algorithm).
---6. Pitfalls & Examiner-Reported Common Errors
Watch out for these common traps in your CCEA exams:
1. Premature Boundary Condition Application (Most Common Error!):
Students often try to find \(A\) and \(B\) in the complementary function \(u_n^{(c)}\) before finding and adding the particular solution \(u_n^{(p)}\). Always write \(u_n = u_n^{(c)} + u_n^{(p)}\) before using your initial values!
2. Index Shifting Confusion (\(n = 0\) vs. \(n = 1\)):
Check whether the initial value is given for \(u_0\) or \(u_1\). Substituting \(n = 1\) into \(A \lambda^n\) gives \(A \lambda\), not \(A\). Pay careful attention to the starting index given in the question.
3. Missing Root Collisions (Resonance):
If you try a constant trial solution \(u_n^{(p)} = C\) for the relation \(u_{n+1} - u_n = 4\), you will get \(C - C = 4 \implies 0 = 4\), which is impossible! Because \(\lambda = 1\) is already a root of the auxiliary equation, you must multiply your trial solution by \(n\), trying \(u_n^{(p)} = C n\).
4. Sign Errors in the Auxiliary Quadratic:
Make sure all terms are gathered on one side of the equation before writing down the characteristic equation. For example, \(u_{n+2} = 5u_{n+1} - 6u_n\) must be rearranged to \(u_{n+2} - 5u_{n+1} + 6u_n = 0\), which gives \(\lambda^2 - 5\lambda + 6 = 0\).
5. Modulus and Argument Errors with Complex Roots:
When finding \(\theta = \arctan\left(\frac{q}{p}\right)\), always sketch the complex number on an Argand diagram to ensure \(\theta\) is in the correct quadrant.
7. Quick Review Checklist
Before sitting your exam, make sure you can confidently:
• State the order of any recurrence relation and classify it as homogeneous or non-homogeneous.
• Solve first-order relations using \(u_n = A a^n + u_n^{(p)}\).
• Form the characteristic equation \(a \lambda^2 + b \lambda + c = 0\) for second-order relations.
• Apply the three root cases (distinct real, repeated real, complex conjugate).
• Select the correct trial particular solution for constants, polynomials, and geometric terms.
• Apply initial conditions to determine all arbitrary constants accurately.